27a Olimpíada Brasileira de Informática
Falta uma
Carolina tem um jogo de tabuleiro que possui 24 cartas contendo, cada uma, uma permutação dos quatro primeiros números naturais. (Cartas distintas contêm permutações distintas.) Lembre-se de que a quantidade de permutações de quatro números é 4!, que é igual a 24. Só que ela contou e encontrou apenas 23 cartas. Está faltando uma! Dê uma olhada nessa lista embaralhada de 23 cartas. Qual está faltando?4 1 2 3 | 1 2 3 4 | 1 3 4 2 | 4 3 2 1 | 2 1 3 4 | 3 1 2 4 |
2 1 4 3 | ? | 4 3 1 2 | 1 2 4 3 | 1 4 3 2 | 3 2 4 1 |
4 1 3 2 | 3 4 1 2 | 2 3 4 1 | 1 3 2 4 | 3 4 2 1 | 4 2 1 3 |
1 4 2 3 | 2 4 3 1 | 4 2 3 1 | 3 2 1 4 | 2 3 1 4 | 2 4 1 3 |
Agora suponha que o jogo tenha um baralho de N! cartas, com todas as permutações possíveis dos N primeiros naturais. Neste problema, dado N e uma lista com N!-1 cartas, seu programa deve imprimir a carta que está faltando.
Entrada
A primeira linha da entrada contém um inteiro N. As N!-1 linhas seguintes contêm, cada uma, N naturais. Cada linha representa uma permutação distinta dos N primeiros naturais.Saída
Seu programa deve imprimir uma única linha, contendo N naturais representando a permutação que está faltando na entrada.Restrições
- 2 ≤ N ≤ 8.
Exemplos
Entrada
3 3 2 1 2 1 3 1 3 2 3 1 2 1 2 3 |
Saída
2 3 1 |
Entrada
2 2 1 |
Saída
1 2 |