| Submeter | Todas submissőes | Melhores | Voltar |
NOME - Dando nome aos times |
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: | 1s |
| Tamanho do fonte: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Linguagem permitida: | Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL |
| Origem: | Segunda Seletiva para Maratona de Programacao IME-USP - 2008 |
hide comments
|
2011-09-30 20:44:10 Fernando Fonseca [ITA]
Tá meio aberto mesmo, vou tentar formalizar o que eu supus: uma soluçăo S é a que "segue melhor a preferęncia de Da Silva" se năo existe uma soluçăo T tal que, para todos os nomes, ou os nomes estejam com o mesmo time que em S ou com um time para o qual Da Silva preferiria dar o nome. |
|
|
2010-08-01 17:07:27 Gabriel Luís Mello Dalalio [ITA]
Acho que o enunciado năo explicou direito o que fazer quando há mais de uma possibilidade, o que é exatamente seguir melhor a lista de preferęncia de Da Silva? |