Uma das atrações mais conhecidas nas feiras populares é a máquina de teste de força, onde jovens que querem impressionar as namoradas tentam fazer subir um peso e tocar um sino com a batida de um martelo.
Esta semana, a empresa ONI (Obras Nada Inteligentes) foi contratada para um serviço muito peculiar. O seu cliente queixa-se que ultimamente, além de fazer tocar o sino, os concorrentes estão a conseguir parti-lo! As despesas com a sua reparação são incomportáveis e a ONI foi contratada para descobrir qual a força necessária para o sino partir. O problema é que o cliente tem um número muito limitado de sinos disponíveis e exige que o teste seja feito rapidamente para não perder clientela. Consegues ajudar a ONI?
Podes começar por descarregar os ficheiros correspondentes à tua linguagem (ou um arquivo zip contendo tudo):
Linguagem | Ficheiro a implementar | Ficheiro com avaliador exemplo | Ficheiros auxiliares | Input para avaliador exemplo |
C | resolver.c | avaliador.c | martelada.h | input.txt |
C++ | resolver.cpp | avaliador.cpp | ||
Java | resolver.java | avaliador.java | ------ | |
Pascal | resolver.pas | avaliador.pas | ------ |
Deves submeter um único ficheiro que implementa a
função resolver(N, K)
, que recebe dois números inteiros
(a força máxima N e o número de sinos K) e devolve a
menor força necessária para partir o sino. Para isso deves usar o
ficheiro resolver.{c,cpp,java,pas} que descarregaste,
colocando no interior da função o teu código. Podes acrescentar
outras funções, mas devem ficar todas neste ficheiro que é o único
que deves submeter.
Função a implementar:
C/C++/Java: | int resolver(int N, int
K); |
Pascal: | function resolver(N, K : longint): longint; |
A tua função deve invocar a função martelada(f)
implementada pelo avaliador, que recebe um inteiro f com a força da martelada que pretendes testar e devolve 1 caso o sino seja partido e 0 caso o sino não seja partido.
Função do avaliador:
C/C++/Java: | int martelada(int f); |
Pascal: | function martelada(f : longint): longint; |
O teu objectivo é descobrir o menor número inteiro f que permite partir o sino, mas lembra-te que só existem K sinos disponíveis. O programa será abortado caso a função seja invocada e não existirem mais sinos disponíveis. A vossa função não deve ler nem escrever para os canais de entrada/saída padrão.
resolver(10, 2)
. Vamos supor que o sino parte sempre
que a força efetuada é igual ou superior a 4. Uma possível execução
seria a seguinte (com a ordem das chamadas a ser de cima para baixo):
Invocação | Resultado | Descrição |
martelada(7) | 1 | O sino partiu com a força 7, só existe mais um sino disponível. |
martelada(1) | 0 | O sino não partiu com a força 1. |
martelada(2) | 0 | O sino não partiu com a força 2. |
martelada(3) | 0 | O sino não partiu com a força 3. |
martelada(4) | 1 | O último sino partiu com a força 4. |
A função resolver(N,K)
deve retornar a resposta correta, que neste caso corresponde ao número inteiro 4.
1 ≤ N ≤ 100 000 | Força máxima a considerar. | |
1 ≤ K ≤ 3 | Número de sinos a considerar. |
Um caso de teste consiste em várias invocações da função resolver(N,K)
com os mesmos parâmetros N e K, variando unicamente a força necessária para partir o sino. A função deve retornar o valor correto em todas as invocações para uma pontuação ser atribuída nesse caso de teste.
A pontuação do caso de teste será dada pelo maior número de marteladas que foram necessárias para descobrir a resposta após variar a força necessária. Quanto menor o número de marteladas necessário, maior a pontuação no caso de teste.
É disponibilizado um avaliador exemplo em cada linguagem (avaliador.{c,cpp,java,pas}) que pode ser utilizado para testar a vossa submissão. Este avaliador não corresponde ao utilizado pelo sistema de avaliação.
Este avaliador começa por receber como input três números N, K e C correspondendo, respetivamente, à força máxima, ao número de sinos e ao número de casos de teste. Seguem-se C linhas, cada uma contendo 1 número inteiro fi que indica a força mínima necessária para partir o sino.
O avaliador irá automaticamente invocar a
função resolver(N,K)
por vocês implementada e indicará
se a resposta foi correta. Em caso afirmativo, também indicará o
número de marteladas que foram necessárias para a descobrir.
Disponibilizamos um ficheiro input.txt que pode ser usado para testar todas as forças mínimas possíveis para o caso em que N=10 e K=2.
Um exemplo de teste na tua máquina (supondo que tens os compiladores oficiais instalados) seria o seguinte:
Linguagem | Compilar | Executar com o exemplo |
C | gcc -Wall avaliador.c resolver.c | ./a.out < input.txt |
C++ | g++ -Wall avaliador.cpp resolver.cpp | ./a.out < input.txt |
Java | javac avaliador.java resolver.java | java avaliador < input.txt |
Pascal | fpc avaliador.pas | ./avaliador < input.txt |
O output deve mostrar em que casos acertaram.