Problema D - Equipa de Salvamento

Este é problema usa o novo formato de problemas.
Consulta a página de instruções para informações detalhadas sobre como funciona este novo formato.
Este é um problema de interação.
Ao contrário dos outros problemas em que deves fazer leitura de dados e escrita do output, neste problema deves interagir com o avaliador através da implementação de uma função e da interação com as funções fornecidas.

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?

Ficheiros para Download

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

Implementação

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

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:

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.

Exemplo

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çãoResultadoDescrição
testar(1, 2)1O primeiro robot tem força 5 e o segundo tem força 1, logo o primeiro tem mais força.
testar(2, 3)0O segundo robot tem menos força (1) que o terceiro robot (3).
testar(3, 4)1O terceiro robot tem mais força (3) que o quarto robot (2).
testar(4, 5)0O 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.

Restrições

São garantidos os seguintes limites em todos os casos de teste:
1 ≤ N ≤ 10 000Número de robots.
1 ≤ Q ≤ 200 000Número de testes.

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:

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

Testes no vosso computador

É 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:

LinguagemCompilarExecutar com o exemplo
Cgcc -Wall avaliador.c resolver.c./a.out < input.txt
C++g++ -Wall -std=gnu++14 avaliador.cpp resolver.cpp./a.out < input.txt
Javajavac avaliador.java resolver.javajava avaliador < input.txt
Pascalfpc avaliador.pas./avaliador < input.txt

Qualificação para a final das ONI'2020
(23/04 a 25/04 de 2020)