| Submeter | Todas submissőes | Melhores | Voltar |
GENEAL - Árvore Genealógica |
A empresa Genesis faz vários serviços dedicados a famílias, principalmente para descobrir parentes e parentescos perdidos. Para mostrar a eficiência de seus serviços, a Genesis quer, para cada árvore genealógica que ela tem, achar o par de parentes com parentesco mais distante. Para isso, eles definiram uma "função-parentesco" definida da seguinte forma:
grau(A, B) = 0, seA = Bgrau(A, B) = 1 + min{grau(pai(A), B), grau(A, pai(B))}, seA != B
Você deve fazer um programa que, dado uma árvore genealógica, imprime o nome dos dois parentes com maior grau de parentesco.
Entrada
A entrada é composta de um único caso de teste. A primeira linha contém um número inteiro positivo N, que indica o número de relações pai-filho que serão descritas. As N linhas seguintes contêm duas strings cada, P e F, indicando que P é pai de F.
Saída
Seu programa deve imprimir uma única linha contendo os nomes do par de parentes com maior grau de parentesco, e esse grau. Essas duas strings devem estar em ordem alfabética; em caso de empate, você pode imprimir qualquer par com essa característica.
Restrições
2 ≤ N ≤ 1000- Todos os nomes tem tamanho máximo 50.
Exemplo
Entrada 11 arnaldo daniel alfredo rafael alfredo deborah angela marcelo julio arnaldo angela elaine angela guilherme arnaldo renato marcelo beatriz julio angela julio alfredo Saída beatriz daniel 5 Entrada 5 a b b c a d d e e f Saída c f 5
| Adicionado por: | Wanderley Guimarăes |
| Data: | 2009-01-27 |
| Tempo limite: | 1s |
| Tamanho do fonte: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Linguagem permitida: | Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO OBJC PERL6 PY_NBC SCALA SQLITE TCL |
| Origem: | Treino para OBI de 2006 - Fábio Moreira & Daniel Fleischman |
hide comments
|
2016-04-23 06:32:13
Caro Elsio [UFABC] , conforme você mesmo já observou em outros problemas: Floyd-Warshall neles. Esquece esse negócio de pais, trate como arestas bidirecionais que dá certo. |
|
|
2016-04-21 14:46:00 Elsio [UFABC]
Que acontece se não encontrarmos o pai de A ou o pai de B? |
|
|
2015-04-11 18:17:47 Thalyson Nepomuceno [UECE]
fui confiando nessa linha em branco a mais... tomei 2 WA xD parece q năo ta mais precisando disso. |
|
|
2014-08-14 22:41:14 Alessandro Ferreira - UFMS
Como o Diego Buchinger [UDESC] disse, o enunciado está incorreto, a saída deve conter 2 linhas, uma com a resposta e uma em branco no final ( '\n' ). |
|
|
2014-07-23 20:03:13 Tiago Nápoli
Ordem alfabética != ordem lexicográfica |
|
|
2011-09-18 23:53:02 thiagojobson [UERN]
Se liguem tbm que o número de pessoas na árvore pode ser != N mas respeitam o limite de 1000 :D Last edit: 2011-09-19 00:06:47 |
|
|
2011-02-05 15:54:52 Diego Buchinger [UDESC]
Detalhe: as respostas devem ter no final um '\n' (thanks to unioeste) |