Problema D - Regular a Temperatura

O Henrique está a tomar banho em casa dos avós. A temperatura da água é regulada por uma torneira com números inteiros de 1 a N, por ordem crescente de calor. O Henrique lembra-se que que um destes inteiros corresponde à temperatura perfeita, mas não se lembra qual. O Henrique muda a temperatura da água uma vez por segundo, e o Henrique sabe dizer se a água está demasiado fria, quente, ou ideal. No entanto, a temperatura demora K segundos a atualizar, pelo que ele só sabe a qualidade da temperatura selecionada no segundo t depois do segundo t+K.

O Henrique não pode ficar o tempo todo no banho, pelo que só tem Q segundos para encontrar a temperatura ideal. Como antigo concorrente das ONI, ele suspeita que deve haver um bom algoritmo para encontrar a temperatura ideal o mais depressa possível. Consegues ajuda-lo?

Ficheiros para Download

Podes começar por descarregar os ficheiros correspondentes à tua linguagem (ou um arquivo zip contendo tudo):

Implementação

Deves submeter um único ficheiro que implementa uma função:

• A função resolver(N, K, Q), que recebe um inteiro N, que representa o número de temperaturas, um inteiro K, que representa o atraso na atualização de uma temperatura, e um inteiro Q, o número de segundos disponíveis. A função deve devolver um inteiro representando a temperatura ideal.

Nota: No avaliador oficial a função resolver será chamada várias vezes na mesma execução (até um máximo de 10,000 vezes). Se alguma das chamadas devolver o valor errado ou usar mais perguntas do que as permitidas, a resposta será considerada incorreta.

Para isso deves usar o ficheiro resolver.cpp que descarregaste, colocando no interior das funções o teu código. Podes acrescentar outras funções, mas devem ficar todas neste ficheiro que é o único que deves submeter.

Funções a implementar:

C++:	int resolver(int N, int K, int Q);

A tua função deve invocar as seguinte função:

• A função pergunta(temp), que recebe um inteiro entre 1 e N representando uma temperatura e devolve um inteiro. O valor de retorno é a resposta atrasada, ou seja, será a resposta à K-ésima pergunta anterior. Para as primeiras K perguntas é devolvido o valor -2, indicando que não há ainda nenhum resultado. A partir dai, a função devolve a resposta da K-ésima pergunta anterior no seguinte formato:
  • 1 se a temperatura perguntada for menor que a temperatura ideal;
  • -1 se a temperatura perguntada for maior que a temperatura ideal;
  • 0 se a temperatura perguntada for a temperatura ideal;

Nota que é importante que temp esteja entre 1 e N. Também é importante notar que se excederes o número de perguntas permitidas (ver limites) o programa será interrompido e a resposta será considerada incorreta.

Funções do avaliador:

C++:	int pergunta(int temp);

A vossa função não deve ler nem escrever para os canais de entrada/saída padrão.

Exemplo

Considera N = 10, K = 2 e Q = 12. A função resolver que deves implementar será chamada como resolver(10, 2, 12).

Uma possível execução seria a seguinte (com a ordem das chamadas a ser de cima para baixo):

Restrições

Avaliação e Casos de Teste

Os casos de teste deste problema estarão agrupados em conjuntos de testes. Ao contrário dos restantes problemas, para obter pontuação é necessário acertar todos os casos de teste de um grupo de casos, nesse caso terão a pontuação completa relativa a esse grupo. Se falharem um ou mais casos de um grupo, a pontuação atribuída relativa a esse grupo será nula.

Cada grupo tem um número de pontos associado e um conjunto de restrições adicionais. Os grupos são os seguintes:

Testes no vosso computador

É disponibilizado um avaliador exemplo (avaliador.cpp) que pode ser utilizado para testar a vossa submissão. Está ainda disponível um ficheiro auxiliar (avaliador.h). Este avaliador não corresponde ao utilizado pelo sistema de avaliação.

Este avaliador receber como input quatro inteiros: N, K, Q e a temperatura ideal.

O avaliador irá automaticamente invocar a função resolver(N, K, Q) por vocês implementada e indicará se a resposta foi correta. O avaliador indicará ainda o número de perguntas efetuadas.

Disponibilizamos um ficheiro input.txt que contém o caso de exemplo referido acima.

Um exemplo de teste na tua máquina (supondo que tens os compiladores oficiais instalados) seria o seguinte: