Na quinta das ONI há N cabras, numeradas de 1 a N. Para guardar as cabras, há N estábulos dispostos em linha, também numerados de 1 a N. Cada estábulo contem exatamente uma cabra.
Inicialmente as cabras estão distribuidas pelos estábulos de acordo com uma sequência P: o estábulo i contém a cabra Pi. Infelizmente, esta sequência não é conhecida.
Para obter informação sobre P podemos fazer observações. Uma observação consiste em escolher um estábulo i verificar que cabra se encontra nesse estábulo, ou seja, o valor de Pi. Porém, após fazermos uma observação as cabras decidem revoltar-se e potencialmente mudar de estábulo.
As cabras seguem sempre a mesma receita quando mudam de estábulo, de acordo com uma sequência S: a cabra no estábulo i muda-se para o estábulo Si.
Dados N e um inteiro Q, determina o valor de P e S fazendo no máximo Q observações.
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.cpp | avaliador.cpp | avaliador.h | input.txt |
Nota que a implementação do avaliador a usar nos testes oficiais será diferente, mas podes esperar o mesmo comportamento.
Deves submeter um único ficheiro que implementa uma função:
cabras(N, Q), que recebe um
inteiro N, que representa o número de cabras e
estábulos, e um inteiro Q, que representa o número
máximo de observações. Para isso deves usar o ficheiro resolver.cpp 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++: | void cabras(int N, int Q); |
A tua função deve invocar as seguintes funções:
observacao(i), que recebe um
inteiro i e devolve o número da cabra no
estábulo i. Após executar esta função, as cabras movem-se
de acordo com S.
resposta(P, S), que recebe dois vetores
P e S. Devem usar esta função para indicar
os valores de P e S que determinaram, ou seja, a
vossa resposta.
Nota o seguinte:
observacao), o vosso código
terá o resultado de Wrong Answer.Funções do avaliador:
| C++: | int observacao(int i); |
| C++: | void resposta(vector<int> P, vector<int> S); |
Nota o seguinte:
A vossa função não deve ler nem escrever para os canais de entrada/saída padrão.
Vamos supor que há N = 4 cabras/estábulos, Q = 100 e que P=[4 3 2 1], S=[2 1 4 3].
Uma possível execução seria a seguinte (com a ordem das chamadas a ser de cima para baixo):
| Invocação | Resultado | Descrição |
| observacao(1) | 4 | Após movimento o estado das cabras é: [3 4 1 2] |
| observacao(1) | 3 | Após movimento o estado das cabras é: [4 3 2 1] |
| observacao(3) | 2 | Após movimento o estado das cabras é: [3 4 1 2] |
| observacao(4) | 2 | Após movimento o estado das cabras é: [4 3 2 1] |
| resposta([4, 3, 2, 1], [2, 1, 4, 3]) | - | Indicamos a resposta correta. |
| 4 ≤ N ≤ 100 | Número de cabras/estábulos. | |
| 1 ≤ Q ≤ 30 000 | Número de observações. |
Os valores de Q, máximo número de observações por intervalo, são dados na secção seguinte.
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 = 4, Q = 100 |
| 2 | 25 | Q = 30 000 |
| 3 | 20 | Q = 1 000 e Si = i para todo o i |
| 4 | 25 | Q = 1 000 |
| 5 | 20 | Q = 200 |
É disponibilizado um avaliador exemplo em cada linguagem (avaliador.cpp) que pode ser utilizado para testar a vossa submissão. Está ainda disponível um ficheiro auxiliar (avaliador.h). 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 cabras/estábulos e ao número máximo de observações. Segue-se uma linha com N inteiros distintos entre 1 e N, representando os valores de Pi. Segue-se uma outra linha com N inteiros distintos entre 1 e N, representando os valores de Si.
O avaliador irá automaticamente invocar a
função cabras(N,Q), por vocês implementada. O
avaliador indicará se a resposta é considerada correta ou não
quando chamarem a função resposta.
Disponibilizamos um ficheiro de teste:
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++ | g++ -Wall -std=gnu++14 avaliador.cpp resolver.cpp | ./a.out < input.txt |