Problema D - Teste de Força

Este é um problema de interação.
Ao contrário dos outros problemas em que deves fazer leitura de dados e escrita do output, neste problema deves interagir com o avaliador através da implementação de uma função e da interação com as funções fornecidas.

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?

O Problema

Dado o limite máximo de força N que a ONI consegue exercer e o número de sinos K que a ONI tem disponíveis (no máximo 3), a tua tarefa é descobrir a força mínima (um inteiro entre 1 e N) que faz partir o sino usando o menor número de pancadas possíveis.

Ficheiros para Download

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 ------

Implementação

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.

Exemplo

Imagina que a força máxima é 10 e existem 2 sinos disponíveis. A função resolver que deves implementar será chamada como 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çãoResultadoDescrição
martelada(7)1O sino partiu com a força 7, só existe mais um sino disponível.
martelada(1)0O sino não partiu com a força 1.
martelada(2)0O sino não partiu com a força 2.
martelada(3)0O sino não partiu com a força 3.
martelada(4)1O ú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.

Restrições

São garantidos os seguintes limites em todos os casos de teste:
1 ≤ N ≤ 100 000     Força máxima a considerar.
1 ≤ K ≤ 3     Número de sinos a considerar.
É também garantido que o sino sempre partirá com a força máxima e nunca partirá com força 0.

Avaliação e Casos de Teste

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.

Testes no vosso computador

É 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:

LinguagemCompilarExecutar 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.javajava avaliador < input.txt
Pascalfpc avaliador.pas./avaliador < input.txt

O output deve mostrar em que casos acertaram.


Qualificação para a final das ONI'2015
(15/03 a 17/03 de 2015)