(2) Foi organizado um contest de programação onde programadores de diversas instituições podem se inscrever. A lista de inscrições já está disponível, e deseja-se saber quantos participantes de cada instituição já se inscreveram. Dada a lista de inscritos e suas instituições, determine quantos participantes há por instituição. A lista de inscritos deverá ser inserida, e o programa para quando o número de inscrições for zero. Use map na resolução da questão.
Exemplo de entrada:
Entre com o numero de inscricoes: 5
Entre com os alunos inscritos:
Bruno UFPR
Mateus UFCG
Christian UTFPR
Ricardo UFPR
William UTFPR
Entre com o numero de inscricoes: 4
Entre com os alunos inscritos:
Joao OBI
Maria UFCN
Alice OBI
Bob PUC
Entre com o numero de inscricoes: 0
Exemplo de saída:
UFPR 2
UFCG 1
UTFPR 2
OBI 2
UFCN 1
PUC 1
Entre com os alunos inscritos:
Bruno UFPR
Mateus UFCG
Christian UTFPR
Ricardo UFPR
William UTFPR
Entre com o numero de inscricoes: 4
Entre com os alunos inscritos:
Joao OBI
Maria UFCN
Alice OBI
Bob PUC
Entre com o numero de inscricoes: 0
UFCG 1
UTFPR 2
OBI 2
UFCN 1
PUC 1
Passo 1
Beleza, vamos lá: o enunciado pede pra gente ler várias “rodadas” de inscrições (cada uma começa com um número N e termina quando N=0), e em cada rodada temos N linhas com “Nome Instituição”. O objetivo é contar quantos inscritos há em cada instituição naquela rodada e imprimir, na ordem em que cada instituição apareceu pela primeira vez, o nome da instituição seguido do total de inscritos.
Conteúdo: uso de map (ou dicionário) para contar, e uma lista ou vetor para manter a ordem de aparição. Não precisa saber nada de teoria avançada, só map e lista!
Conteúdo: uso de map (ou dicionário) para contar, e uma lista ou vetor para manter a ordem de aparição. Não precisa saber nada de teoria avançada, só map e lista!
Passo 2
A lógica geral é:
- Enquanto N for diferente de zero, faça:
a) Crie um map vaziocontagem
de string para inteiro.
b) Crie um vetor vazioordem
de string.
c) Para i de 1 até N:- Leia a linha “Nome Instituição”.
- Pegue só a parte da instituição (a gente pode ignorar o nome).
- Se
contagem[instituição]
ainda não existir (i.e., for zero), faz:
· adicionainstituição
no final deordem
. - Incrementa
contagem[instituição]
em 1.
d) Depois de ler os N, percorreordem
na ordem original e para cada inst emordem
imprime:
inst contagem[inst]
.
- Lê um novo N. Se N=0, encerra.
Passo 3
Explicando a teoria usada:
- Map/Dicionário (em C++ seria
map<string,int>
, em Pythondict
) guarda pares (chave, valor). Aqui a chave é o nome da instituição, e o valor é quantos inscritos já vimos. - Vetor/List mantém a ordem de primeiro aparecimento. Sem isso, se você só usar o map, não sabe em que ordem imprimir.
- Cada vez que vemos uma instituição nova, jogamos ela nesse vetor. Depois usamos o vetor pra imprimir na mesma ordem.
Resposta
Pseudo-código completo:
enquanto verdadeiro:
lê N
se N == 0:
sai do loop
cria map<string,int> contagem vazio
cria lista<string> ordem vazia
para i de 1 até N:
lê linha “Nome Instituição”
extrai só "Instituição"
se contagem[Instituição] == 0:
adiciona Instituição em ordem
contagem[Instituição] += 1
para cada inst em ordem:
imprime inst, contagem[inst]