Mais um
ano de olimpíadas e mais uma vez a comitiva portuguesa vai
viajar para participar em mais uma olímpiada
internacional. Depois de uma jornada cansativa num grande avião,
já se encontram todos prontos para sair do aeroporto e juntar-se
aos concorrentes dos outros países.
Infelizmente parece haver um problema com o passaporte de um dos concorrentes, o Luís. O número de série não está a ser aceite pela máquina automática! Para ser aceite no país, é necessário introduzir o número de série na máquina automática para validar a identidade do Luís...
O número de série de um passaporte é uma sequência de N caracteres 0 ou 1 (ou seja, uma string binária), onde N é um número par positivo. A máquina automática lê um número de série e posteriormente reporta se está correto ou não. Para ajudar a corrigir potenciais erros, ao introduzir um número de série qualquer que esteja incorreto, a máquina retorna um inteiro que representa quão diferentes são os números. Se P for o número de série do passaporte e G o número de série introduzido, a máquina retorna k se existirem exatamente k caracteres diferentes entre os dois números de série.
Seja, por exemplo, P = 101101 e G = 100010, então (os caracteres '=' representam posições iguais e '!' diferentes):
P -> 101101
G -> 100010
==!!!!
Logo a máquina retorna 4, visto que os últimos 4 caracteres são diferentes.
A equipa portuguesa só poderá continuar quando conseguirem obter o número de série correto, para tal, decidiram tentar adivinhar o número correto usando a máquina automática para ir sabendo quão próximos da solução estão. Infelizmente, a máquina tem um limite de 2050 operações, mais que isso e a máquina bloqueará e o Luís não poderá entrar no país nem participar na IOI... Consegues ajudar o Luís adivinhando o seu número de série?
Enquanto se tratava do problema do Luís, aparentemente o número de série de outro concorrente, o Vitor, também não está a ser aceite! Parece que vai ser preciso adivinhar o número de série do passaporte do Vitor. Infelizmente, a máquina automática parece estar avariada e o seu funcionamento está ligeiramente diferente.
Se P for o número de série do passaporte (com N dígitos) e G o número de série introduzido, a máquina retorna: 0 se o G for igual a P (o número foi adivinhado corretamente); N/2 se G e P forem diferentes em exatamente N/2 posições; N em qualquer outra situação.
Para este modelo, se N = 6 e P = 101101 o resultado:
Dada a condição da máquina automática a usar para o Vitor, consegues ajudá-lo também a saber o seu número de série?
Dado o tamanho dos números de série de passaportes N e um dos concorrentes (o Luís ou o Vitor), adivinhar o número de série do seu passaporte em menos de 2050 tentativas.
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 | avaliador.h | input.txt |
| C++ | resolver.cpp | avaliador.cpp | ||
| Java | resolver.java | avaliador.java | ------ | |
| Pascal | resolver.pas | avaliador.pas | avaliadorlib.pas |
Nota que a implementação do avaliador a usar nos testes oficiais será diferente, mas podes esperar o mesmo comportamento. Além disso, é garantido que a máquina automática demora menos de 0.1 segundos a responder a 2050 adivinhas.
Deves submeter um único ficheiro que implementa a
função resolver(N, C), que recebe um
inteiro N, que representa o número de dígitos do número
de série (que será sempre par), e um carácter C, que
representa o concorrente a ajudar (que será apenas ou 'L' para o
Luís, ou 'V' para o Vitor). 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: | void resolver(int N, char C); |
| Pascal: | procedure resolver(N : Longint, C : char); |
A tua função deve invocar a seguinte função:
adivinhar(g) implementada pelo avaliador, que
recebe uma string g e devolve a resposta da máquina
automática para esse número de série.
Nota que é importante que a string g tenha exatamente N caracteres e que todos eles sejam ou '0' ou '1', caso contrário as funções chamadas irão terminar o programa e a resposta será considerada incorreta. Também é importante notar que se excederes as 2050 perguntas o programa será interrompido e a resposta será considerada incorreta.
Funções do avaliador:
| C: | int adivinhar(char g[MAXN]); |
| C++/Java: | int adivinhar(string g); |
| Pascal: | function adivinhar(g : array of char): Longint; |
avaliador.adivinhar(g).
O teu objetivo é descobrir o número de série correto para o Luís
ou para o Vitor. Para tal, deves chamar a
função adivinhar(g) com o número de série correto,
ao qual esta irá retornar 0 não deverás chamar mais nenhuma vez
a função adivinhar(g).
A vossa função não deve ler nem escrever para os canais de entrada/saída padrão.
Imagina que estás a ajudar o Luís que N = 6. A
função resolver que deves implementar será chamada
como resolver(6, 'L').
Uma possível execução seria a seguinte (com a ordem das chamadas a ser de cima para baixo):
| Invocação | Resultado | Descrição |
| adivinhar(000000) | 4 | 4 dos dígitos do que adivinhámos estão incorretos. |
| adivinhar(101000) | 2 | 2 dos dígitos do que adivinhámos estão incorretos. |
| adivinhar(101001) | 1 | 1 dos dígitos do que adivinhámos estão incorretos. |
| adivinhar(101101) | 0 | Acertámos! |
Para este exemplo o número de série correto era 101101.
| 1 ≤ N ≤ 1 000 | Número de dígitos. |
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:
| Grupo | Número de Pontos | Restrições adicionais |
|---|---|---|
| 1 | 25 | N ≤ 10, C = 'L' |
| 2 | 25 | C = 'L' |
| 3 | 25 | N ≤ 50, C = 'V' |
| 4 | 25 | C = 'V' |
É disponibilizado um avaliador exemplo em cada linguagem (avaliador.{c,cpp,java,pas}) que pode ser utilizado para testar a vossa submissão. Para C/C++/Pascal está ainda disponível um ficheiro auxiliar (para C/C++ o avaliador.h e para Pascal o avaliadorlib.pas). Este avaliador não corresponde ao utilizado pelo sistema de avaliação.
Este avaliador começa por receber como input um inteiro N e um carácter C correspondendo, respetivamente, ao número de dígitos do número de série, e ao concorrente a ajudar ('L' para o Luís e 'V' para o Vitor). Segue-se uma linha com N dígitos 0 ou 1, que representa o número de série a adivinhar.
O avaliador irá automaticamente invocar a
função resolver(N,C) por vocês implementada e
indicará se a resposta foi correta. Em caso afirmativo, também
indicará o número de adivinhas que foram efetuadas.
Disponibilizamos um ficheiro input.txt que contém o caso de exemplo referido a cima.
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 |