O Rodrigo tem uma coleção de N moedas numeradas de 1 a N, cada uma com um peso diferente, que é infelizmente desconhecido. O Rodrigo que avaliar o valor da sua coleção, para isso precisa de saber qual é a sua moeda mais pesada e a mais leve. Para isso, vai usar uma balança muito precisa. Esta balança consegue determinar qual a moeda mais pesada dado um par de moedas (não é possível comparar grupos de moedas, apenas um par de moedas). Visto que a balança é muito delicada, ele quer minimizar o número de vezes que a usa, mas quer descobrir qual a moeda mais leve e a mais pesada na mesma, consegues descobri-lo no menor número de comparações?
Dado o número de moedas N do Rodrigo, descobrir a mais pesada e a mais leve.
Podes começar por descarregar os ficheiros correspondentes à tua linguagem (ou um arquivo zip contendo tudo):
Nota: este problema foi criado quando ainda era permitida a linguagem Pascal e ainda não era permitida a linguagem Python. Iremos atualizar quando for possível, mas de momento, neste problema, o nosso servidor apenas irá permitir submissões em C, C++ ou Java.
| 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 é possível efetuar 100.000 comparações em menos de 0.1 segundos.
Deves submeter um único ficheiro que implementa a
função resolver(N), que recebe um inteiro N,
que representa o número de moedas do Rodrigo. 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); |
| Pascal: | procedure resolver(N : Longint); |
A tua função deve invocar as seguintes funções:
comparar(m1, m2) implementada pelo avaliador, que
recebe dois inteiros que representam indíces de moedas e retorna
0 caso o peso da moeda de índice m1 for a mais leve
ou 1 caso a moeda de índice m2 for a mais leve.
resposta(l, p) implementada pelo avaliador, que
deves usar para indicar a tua resposta, o valor da
variável l deve ser a moeda mais leve
e p a mais pesada.
Nota que é importante que tanto m1 como m2 sejam entre 1 e N. Também é importante notar que se excederes 200.000 comparações o programa será interrompido e a resposta será considerada incorreta.
Funções do avaliador:
| C/C++/Java: | int comparar(int m1, int m2); |
| Pascal: | function comparar(m1 : Longint, m2 : Longint): Longint; |
| C/C++/Java: | void resposta(int l, int p); |
| Pascal: | procedure resposta(l : Longint, p : Longint); |
avaliador.comparar(m1, m2)
e avaliador.resposta(l, p).
A vossa função não deve ler nem escrever para os canais de entrada/saída padrão.
Vamos supor que N=4 e que a ordem relativa dos pesos das moedas é: 1 4 3 2, ou seja, a moeda 1 é a mais leve, a 4 a segunda mais leve, a 3 a terceira mais leve e a 2 a mais pesada. Claro que o nosso programa não terá acesso a esta informação, apenas ao valor de N e à função de comparação. O nosso programa poderia fazer o seguinte:
| Invocação | Resultado | Descrição |
| comparar(1, 2) | 0 | Sabemos que a moeda 1 é mais leve que a 2 |
| comparar(2, 3) | 1 | Sabemos que a moeda 3 é mais leve que a 2 |
| comparar(3, 4) | 1 | Sabemos que a moeda 4 é mais leve que a 3 |
| resposta(1, 2) | Respondemos que a moeda 1 é a mais leve e a 2 a mais pesada |
| 1 ≤ N ≤ 100 000 | Número de moedas. |
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 | 40 | Máximo de 200 000 comparações |
| 2 | 60 | Máximo de 150 000 comparações |
É 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 correspondendo ao número de moedas. Segue-se uma linha com N inteiros entre 1 e N, separados por espaços, que representam a ordem relativa dos pesos, que não devem conter valores repetidos.
O avaliador irá automaticamente invocar a
função resolver(N) por vocês implementada e
indicará se a resposta foi correta (devem invocar a
função resposta(l, p) para isso). Em caso
afirmativo, também indicará o número de comparações que foram
efetuadas.
Disponibilizamos um ficheiro input.txt que contém um caso de teste exemplo.
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 |