[obm-l] =?UTF-8?Q?N=C3=BAmero_de_Erdos?=

["Paulo Santa Rita" <paulo.santarita@xxxxxxxxx>]

Ola Pessoal,
O objetivo desta mensagem é duplo : explicar o que e NUMERO DE ERDOS epropor um problema  que caiu em uma Olimpiada de Programacao. O textodo problema é o seguinte :

INICIO DO TEXTO ***

1) INTRODUCAO
O matemático húngaro Paul Erdos (1913-1996), um dos mais brilhantes doséculo XX, é considerado o mais prolífico matemático da história.Erdos publicou mais de 1500 artigos, em colaboração com cerca deoutros 450 matemáticos. Em homenagem a este gênio húngaro, osmatemáticos criaram um número, denominado "número de Erdos". Todapessoa que escreveu um artigo com Erdos tem o número 1. Todos que nãopossuem número 1, mas escreveram algum artigo juntamente com alguémque possui número 1, possuem número 2. E assim por diante. Quandonenhuma ligacão pode ser estabelecida entre Erdos e uma pessoa, diz-seque esta possui número de Erdos infinito. Por exemplo, o número deErdos de Albert Einstein é 2. E, talvez surpreendentemente, o númerode Erdos de Bill Gates é 4.
2) O PROBLEMA
Sua tarefa é escrever um programa que, a partir de uma lista deautores de artigos, determine o número de Erdos dos autores.
3) AS ENTRADAS
Seu programa deve ler vários conjuntos de testes. A primeira linha deum conjunto de teste contém um número inteiro A (1 ≤ A ≤ 100), queindica o número de artigos. Cada uma das A linhas seguintes contém alista de autores de um artigo. Cada autor é identificado pela inicialde seu nome (em maiúscula) seguida pelo seu último sobrenome (`P.Erdos', por exemplo). O sobrenome de um autor possui, no máximo, 15letras, e apenas a letra inicial aparece em maiúscula. Os autores sãoseparados por vírgulas, e a lista de autores de um artigo termina comum ponto (veja os exemplos abaixo). Um único espaço em branco separa aabreviatura do nome do sobrenome, bem como o nome de um autor doanterior. Espaços em branco não são usados em outros locais. Um artigopossui, no máximo, 10 autores, e o total de autores não excede 100. Ofinal da entrada é indicado por A = 0.
Exemplo de Entrada
5P. Erdos, A. Selberg.P. Erdos, J. Silva, M. Souza.M. Souza, A. Selberg, A. Oliveira.J. Ninguem, M. Ninguem.P. Duarte, A Oliveira.
2Z. Silva, P. Erdos.Z. Souza.
0
4) AS SAIDAS
Para cada conjunto de teste da entrada seu programa deve produzir umconjunto de linhas na saída. A primeira linha deve conter umidentificador do conjunto de teste, no formato "Teste n", onde n énumerado seqüencialmente a partir de 1. A seguir devem aparecer umalinha para cada autor do conjunto de testes (exceto o próprio P.Erdos). Cada linha deve conter o nome do autor seguido pelo caractere`:', um espaço em branco e o seu número de Erdos. Caso o número deErdos de um determinado autor seja infinito, escreva `infinito'. Asaída deve ser ordenada pelo sobrenome do autor (em caso de mesmosobrenome, o desempate deve ser feito pela inicial do primeiro nome).Imprima uma linha em branco ao final de cada conjunto de teste. Agrafia mostrada no Exemplo de Saída, abaixo, deve ser seguidarigorosamente.
Exemplo de Saída
Teste 1P. Duarte: 3J. Ninguem: infinitoM. Ninguem: infinitoA. Oliveira: 2A. Selberg: 1J. Silva: 1M. Souza: 1
Teste 2Z. Silva: 1Z. Souza: infinito
(esta saída corresponde ao exemplo de entrada acima)
5) RESTRICOES
0 ≤ A ≤ 100 (número de artigos de um caso de teste; A = 0 apenas paraindicar final da entrada)1 ≤ K ≤ 15 (número de letras do sobrenome de um autor)1 ≤ N ≤ 10 (número de artigos de um conjunto de teste)1 ≤ T ≤ 10 (número total de autores em um conjunto de teste)

FIM DO TEXTO ***
Os programs podem ser feitos em Pascal, C ou Java.
Um Abraco a todosPaulo Santa Rita3,1004,150507
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================