O
laboratório nacional de robótica tem ao seu dispor N
robots de salvamento, sendo que N é um número inteiro
impar. Cada um destes robots tem um certo valor de força que é
um inteiro entre 1 e N, que depende das características
internas de cada um. Sabe-se ainda que nenhum par de robots têm
a mesma força.
A tarefa de salvamento que cada robot tem de desempenhar requer bastante força, mas é também muito delicada. Como tal, a equipa responsável pelos robots quer escolher um robot que tenha um valor de força ponderada para poder usar para uma demonstração pública. Foi decidido que o robot com as seguintes características será usado:
Devido a um problema informático, a base de dados que continha a informação sobre a força de cada robot foi perdida. Como tal, parece impossível encontrar o robot com as características descritas. Felizmente, a equipa pode executar um teste que pode tornar esta procura possível:
A demonstração pública é daqui a poucos dias, por isso a equipa só tem tempo de executar no máximo Q testes como o acima. Consegues ajudar a equipa a determinar o robot escolhido usando no máximo Q testes?
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 |
Deves submeter um único ficheiro que implementa uma função:
escolher(N), que recebe um
inteiro N, que representa o número de robots. Esta função deve retornar o índice do robot
escolhido.
Para isso deves usar o ficheiro resolver.{c,cpp,java,pas} 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/C++/Java: | int escolher(int N); |
| Pascal: | function escolher(N : Longint) : Longint; |
A tua função deve invocar a seguinte função:
testar(p1, p2), que recebe dois
inteiros que representam índices de dois robots, e retorna 1
caso o robot de índice p1 tiver uma força superior ao
de índice p2 e retorna 0 caso contrário.
Nota que é importante que tanto p1 como p2 estejam entre 1 e N. Também é importante notar que se excederes os Q testes o programa será interrompido e a resposta será considerada incorreta.
Funções do avaliador:
| C/C++/Java: | int testar(int p1, int p2); |
| Pascal: | function testar(p1 : Longint, p2 : Longint) : Longint; |
A vossa função não deve ler nem escrever para os canais de entrada/saída padrão.
Imagina que há N = 5 robots e podemos fazer Q = 30
testes, e que os robots têm forças [5, 1, 3, 2, 4]. A
função escolher que deves implementar será chamada
como escolher(5).
Uma possível execução seria a seguinte (com a ordem das chamadas a ser de cima para baixo):
| Invocação | Resultado | Descrição |
| testar(1, 2) | 1 | O primeiro robot tem força 5 e o segundo tem força 1, logo o primeiro tem mais força. |
| testar(2, 3) | 0 | O segundo robot tem menos força (1) que o terceiro robot (3). |
| testar(3, 4) | 1 | O terceiro robot tem mais força (3) que o quarto robot (2). |
| testar(4, 5) | 0 | O quarto robot tem menos força (2) que o quinto robot (4). |
| retornar 3 | - | O terceiro robot tem mais força que os robots 2 e 4 e menos que os 1 e 5. |
| 1 ≤ N ≤ 10 000 | Número de robots. | |
| 1 ≤ Q ≤ 200 000 | Número de testes. |
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 | 10 | N ≤ 100, Q = 200 000 |
| 2 | 25 | N ≤ 10 000, Q = 200 000 |
| 3 | 25 | N ≤ 10 000, Q = 110 000 |
| 4 | 25 | N ≤ 10 000, Q = 70 000 |
| 5 | 15 | N ≤ 10 000, Q = 40 000 |
É 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 inteiro Q, correspondendo, respetivamente, ao número de robots e ao número de comparações permitidas. Seguem-se uma linha com N inteiros entre 1 e N, separados por espaços, que representam as forças dos robots, por ordem.
O avaliador irá automaticamente invocar a
função escolher(N) por vocês implementada e
indicará se a resposta foi correta. O avaliador indicará ainda o
número de comparações 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:
| Linguagem | Compilar | Executar com o exemplo |
| C | gcc -Wall avaliador.c resolver.c | ./a.out < input.txt |
| C++ | g++ -Wall -std=gnu++14 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 |