Um novo jogo para dois jogadores está a fazer furor! O jogo disputa-se num tabuleiro quadriculado de L linhas por C colunas. Um dos jogadores, o criador, é responsável por preencher o tabuleiro com números todos diferentes, obedecendo à restrição de na mesma linha ou na mesma coluna os números virem por ordem estritamente decrescente. Por exemplo, o seguinte tabuleiro seria válido:
| 50 | 46 | 32 | 28 |
| 43 | 35 | 29 | 22 |
| 39 | 25 | 15 | 12 |
O tabuleiro é preenchido "às escondidas" e o outro jogador, o adivinho, não sabe inicialmente nada sobre o tabuleiro, excepto que obedece às restrições de ordem atrás indicadas. O criador diz então em voz alta um número N existente no tabuleiro e o adivinho tem de tentar descobrir em que posição é que esse número aparece, fazendo o mínimo número possível de perguntas ao criador. As perguntas só podem ser da forma: "qual é o número que está na posição (x,y)?".
Dadas as dimensões L e C do tabuleiro de jogo (do qual não conheces o conteúdo) e um número N, a tua tarefa é descobrir em que posição está o número usando o mínimo número possível de perguntas.
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 | procura.h | input.txt |
| C++ | resolver.cpp | avaliador.cpp |
Deves submeter um único ficheiro que implementa o
função resolver(L, C, N), que recebe três números
inteiros: as dimensões do tabuleiro L e C e o
número N a descobrir no tabuleiro. Para isso deves usar o
ficheiro resolver.{c,cpp} 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++: | void resolver(int L, int C, int N); |
A tua função deve invocar a função pergunta(y,x)
implementada pelo avaliador, que recebe dois inteiros y
e x com uma posição do tabuleiro e devolve o número que se
encontra nessa posição. Nota que as coordenadas do tabuleiro começam
em zero e vão de cima para baixo e da esquerda para a direita.
Função do avaliador para fazer uma pergunta:
| C/C++/Java: | int pergunta(int y, int x); |
O teu objectivo é descobrir a posição (y,x) do
número N. Quando tal acontecer, deves invocar uma única vez a
função resposta(y,x) implementada pelo avaliador.
Função do avaliador para indicar a posição de um número:
| C/C++/Java: | void resposta(int y, int x); |
resolver(3, 4,
22). Uma possível execução seria a seguinte (com a
ordem das chamadas a ser de cima para baixo):
| Invocação | Resultado | Descrição |
| pergunta(0,0) | 50 | Na posição (0,0) está o número 50. |
| pergunta(2,3) | 12 | Na posição (2,3) está o número 12. |
| pergunta(0,2) | 32 | Na posição (0,2) está o número 32. |
| pergunta(1,3) | 22 | Na posição (1,3) está o número 22. |
| resposta(1,3) | 1 | A posição do número 22 foi descoberta e é (1,3) |
A tua função não deve invocar mais nenhuma função do avaliador depois de ter feito a resposta.
| 1 ≤ L ≤ 50 | Número de linhas do tabuleiro | |
| 1 ≤ C ≤ 50 | Número de colunas do tabuleiro | |
| 1 ≤ N ≤ 109 | Número do qual queremos descobrir a posição. |
É também garantido que todos os outros números do tabuleiro são inferiores ou iguais a 109.
Um caso de teste consiste em várias invocações da
função resolver(L,C,N) com os mesmos
parâmetros L e C, mas onde a cada invocação
corresponde uma nova matriz e um novo número N. A função deve
retornar a posição correta 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 perguntas que foram necessárias para descobrir a resposta após variar o conteúdo da matriz e o número a descobrir. Quanto menor for o número de perguntas necessário, maior a pontuação no caso de teste. Se falhares a posição de algum número terás zero pontos nesse caso de teste.
É disponibilizado um avaliador exemplo em cada linguagem (avaliador.{c,cpp}) 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 três números T, L e C indicando respetivamente número de jogos a considerar e o número de linhas e colunas do tabuleiro.
Seguem-se T jogos, cada iniciado por um número N, o número a procurar, seguido de L linhas, cada uma com C números indicando o conteúdo do tabuleiro secreto preenchido pelo criador.
O avaliador irá automaticamente invocar a
função resolver(L,C,N) por vocês implementada e indicará
se a resposta foi correta. Em caso afirmativo, também indicará o
número de perguntas que foram necessárias para descobrir a posição do número.
Disponibilizamos um ficheiro input.txt que pode ser usado para testar todas os números possíveis do tabuleiro de exemplo dado anteriormente.
Um exemplo de teste na tua máquina 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 |
O output deve mostrar em que casos acertaram.