SPOJ Problem Set (seletivas)
4744. Dando nome aos times
Problema: NOME
|
O grande coach de maratona Da Silva percebeu que um dos maiores problemas para os times que competem é a escolha do nome. Os times perdem muito tempo pensando em um bom nome e esquecem de treinar. Para resolver esse problema Da Silva resolveu que ele próprio escolheria os nomes dos times. No entanto, para evitar uma revolta ele pretende considerar (um pouco) a opinião de cada time.
Da Silva propôs N nomes para os N times e pediu que cada um fizesse uma lista de preferência, ordenando os nomes de acordo com suas preferências. É claro que para cada nome Da Silva já tinha sua lista de preferência dos times a receber o nome.
A escolha dos nomes será feita de forma que no final não exista um time t1 com nome n1 e um time t2 com nome n2, sendo que t1 preferia o nome n2 ao n1 e Da Silva preferia dar o nome n2 para t1 ao invés de t2. Caso exista mais de uma possibilidade satisfazendo esse critério, será escolhida a que melhor segue a lista de preferência de Da Silva.
Sendo um coach muito ocupado, com viagens pelo mundo, Da Silva quer que você escreva um programa para a escolha dos nomes dos times.
Entrada
A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias.
A primeira linha de cada instância contém um inteiro N indicando o número de times. Os times são identificados por números de 1 a N.
Cada uma das próximas N linhas possui um nome de time proposto por Da Silva, um espaço e a lista de preferência de Da Silva para o nome. A lista de preferência para um nome é dada por uma permutação de 1,...,N representando os times, com um espaço entre cada número, sendo o time mais a esquerda o de maior preferência.
Cada uma das N linhas seguintes possui a lista de preferência de cada time. A i-ésima dessas N linhas corresponde à lista do timei. A lista de preferência da cada time consiste nos N nomes de times ordenados de acordo com a preferência e separados por um espaço.
Restrições
1 <= N <= 300
Um nome de time não tem mais que 15 caracteres e não contém espaços.
Saída
Para cada instância imprima N linhas, sendo que a i-ésima linha deve conter apenas o nome de time que Da Silva escolherá para o time i.
Imprima uma linha em branco após a saída de cada instância.
Exemplo de entrada
2
2
cai_cai_balao 1 2
code_rupper 1 2
cai_cai_balao code_rupper
code_rupper cai_cai_balao
3
2towers.bin 1 2 3
cai_cai_balao 2 3 1
code_rupper 3 1 2
cai_cai_balao code_rupper 2towers.bin
code_rupper cai_cai_balao 2towers.bin
2towers.bin code_rupper cai_cai_balao
Saída para o exemplo de entrada
cai_cai_balao
code_rupper
2towers.bin
cai_cai_balao
code_rupper
Comentários
Na segunda instância do exemplo existem 3 soluções possíveis:
M1 = {(1, 2towers.bin), (2, cai_cai_balao), (3, code_rupper)}
M2 = {(1, cai_cai_balao), (2, code_rupper), (3, 2towers.bin)}
M3 = {(1, code_rupper), (2, cai_cai_balao), (3, 2towers.bin)}
M1 foi a escolhida, pois entre as 3 é a que melhor segue as preferências do coach.
| Adicionado por: | Wanderley Guimarães |
| Data: | 2009-08-31 |
| Tempo limite: | 4s
|
| Tamanho do fonte: | 50000B |
| Linguagem permitida: | Todas exceto: AWK CLOJ ERL F# GO JS PERL 6 SCALA SED TCL |
| Origem: | Segunda Seletiva para Maratona de Programacao IME-USP - 2008 |