(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

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!

Passo 2

A lógica geral é:
  1. Enquanto N for diferente de zero, faça:
    a) Crie um map vazio contagem de string para inteiro.
    b) Crie um vetor vazio ordem 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:
      · adiciona instituição no final de ordem.
    • Incrementa contagem[instituição] em 1.
      d) Depois de ler os N, percorre ordem na ordem original e para cada inst em ordem imprime:
      inst contagem[inst].
  2. Lê um novo N. Se N=0, encerra.

Passo 3

Explicando a teoria usada:
  • Map/Dicionário (em C++ seria map<string,int>, em Python dict) 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]

Exercícios relacionados