Na
Fábrica Automóvel Nacional fabricam-se e reparam-se todo o tipo
de automóveis. Um dos modelos mais difíceis de reparar é o
Besla, que tem um complexo sistema de parafusos.
Na
Fábrica Automóvel Nacional fabricam-se e reparam-se todo o tipo
de automóveis. Um dos modelos mais difíceis de reparar é o
Besla, que tem um complexo sistema de parafusos.
Um típico Besla tem N parafusos distintos que são representados por uma permutação P de N inteiros entre 1 e N. Esta permutação é desconhecida, mas para que seja possível reparar um Besla é necessário descobri-la.
Para esse efeito, um engenheiro conhece o número de inversões da permutação, isto é, o número de pares de posições trocadas, ou mais formalmente o número de índices i < j tais que Pi > Pj.
Por exemplo, para um Besla com N = 5 podemos ter a seguinte permutação: 4 5 3 1 2. Esta permutação tem 8 inversões, por exemplo, os índices 1 e 3, 1 e 4, 2 e 3, etc estão trocados.
Esta informação não é suficiente para descobrir a permutação dos parafusos, por isso um engenheiro pode ainda efetuar um conjunto de operações que alteram a permutação e saber o número de inversões da permutação resultante. Cada operação é dada por dois índices, a e b, e consiste em trocar os índices correspondentes na permutação. Nota que as operações são permanentes, ou seja, cada uma das trocas é mantida (ver exemplo).
Para o exemplo anterior, vamos supor que o engenheiro efetua a operação com os índices 2 e 5, então a permutação resultante seria 4 2 3 1 5, que tem 5 inversões. Se de seguida efetuar a operação 1 e 2, então o resultado será 2 4 3 1 5, que tem 4 inversões.
A fábrica quer automatizar este processo minimizando o número de operações que são efetuadas (ver os limites do problema para mais informação sobre isto) e para isso precisam da tua ajuda.
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 |
Deves submeter um único ficheiro que implementa uma função:
resolver(N, I), que recebe um
inteiro N, que representa o tamanho da permutação, e um
inteiro I, que representa o número de inversões da
permutação inicial.
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 resolver(int N, int I); |
A tua função deve invocar as seguintes funções:
pergunta(a, b), que recebe dois inteiros
que representam índices, e retorna o número de inversões da
permutação resultante de trocar os dois.
resposta(p), que recebe uma array de
inteiros que representam uma permutação. Devem chamar esta
função com a permutação escondida para indicarem a resposta.
Nota que é importante que tanto a como b estejam entre 1 e N. Se uma das perguntas não obedecer a esta formato ou se excederes o número de operações permitidas (ver limites) o programa será interrompido e a resposta será considerada incorreta e terá 0 pontos para esse caso de teste.
Funções do avaliador:
| C++: | int pergunta(int a, int b); |
| C++: | void resposta(int p[]); |
A vossa função não deve ler nem escrever para os canais de entrada/saída padrão.
Considera N = 5 e a permutação inicial 4 5 3 1 2, que tem
8 inversões. A função resolver que deves
implementar será chamada como resolver(5, 8).
Uma possível execução seria a seguinte (com a ordem das chamadas a ser de cima para baixo):
| Invocação | Resultado | Descrição |
| pergunta(2, 5) | 5 | Resulta em 4 2 3 1 5 com 5 inversões. |
| pergunta(1, 2) | 4 | Resulta em 2 4 3 1 5 com 4 inversões |
| resposta([4, 5, 3, 1, 2]) | - |
| 1 ≤ N ≤ 1 000 | Tamanho da permutação. |
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 caso de teste terá um valor de α associado. Este valor representa o rácio de operações que é permitido fazer, ou seja, é permitido fazer αN operações.
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, α = 100 |
| 2 | 20 | N ≤ 1 000, α = 50 |
| 3 | 40 | N ≤ 1 000, α = 5 |
| 4 | 30 | N ≤ 1 000, α = 1 |
É disponibilizado um avaliador exemplo (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 α, correspondendo, respetivamente, ao tamanho da permutação e ao rácio de operações permitidas. Segue-se uma linha com N inteiros entre 1 e N, separados por espaços, que representam a permutação.
O avaliador irá automaticamente invocar a
função resolver(N, I) por vocês implementada e
indicará se a resposta foi correta. O avaliador indicará ainda o
número de operaçõ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++ | g++ -Wall -std=gnu++14 avaliador.cpp resolver.cpp | ./a.out < input.txt |