[ED234] Avaliações Cinematográficas

Neste problema deverá submeter uma classe ED234 contendo um programa completo para resolver o problema (ou seja, com o método main).
Pode assumir que no Mooshak terá acesso a todas as classes base dadas nas aulas, incluindo as de árvores binárias BTree, BSTree e BSTMap (não precisa de as incluir na submissão).
Pode fazer download de todas as classes num arquivo zip ou ver as classes uma a uma.

Suponha que tem disponível uma lista de avaliações de filmes. Uma avaliação é caracterizada por um par (filme,nota) onde o filme é uma palavra sem espaços e a nota é um inteiro entre 1 e 10.

A sua tarefa é fazer algumas estatísticas sobre estas avaliações. Nomeadamente, deve calcular:

• [flag 1] a quantidade de filmes diferentes que tiveram pelo menos uma avaliação. (34% da cotação deste problema)
• [flag 2] qual o filme que foi avaliado mais vezes (sendo garantido que existe um único filme que foi avaliado mais vezes que os outros). (33% da cotação deste problema)
• [flag 3] quais os filmes com uma nota média positiva, ou seja, maior ou igual a 5, imprimidos por ordem alfabética. (33% da cotação deste problema)

Imagine por exemplo que tinha a seguinte lista de 10 avaliações:

Para esta lista de avaliações as estatísticas eram as seguintes:

• [flag 1] o número de diferentes filmes com pelo menos uma avaliação é 5 (StarWarsVIII, BladeRunner2049, ShapeOfWater, Solo, GetOut).
• [flag 2] o filme com mais avaliações é o BladeRunner2049 (3 avaliações)
• [flag 3] os filmes com média positiva (≥5), por ordem alfabetica, são o BladeRunner2049, GetOut e Solo. As notas médias são as seguintes:
  • StarWarsVIII: média = (5+2)/2 = 3.5
  • BladeRunner2049: média = (8+4+6)/3 = 6.0
  • ShapeOfWater: média = (4+1)/2 = 2.5
  • Solo: média = (6+4)/2 = 5.0
  • GetOut: média = 9/1 = 9.0

Input

A primeira linha de input contém um inteiro F, a flag (1, 2 ou 3) indicando qual estatística deve calcular, de acordo com o atrás descrito.

A segunda linha contém um inteiro N, a quantidade de avaliações (1≤N≤50). Seguem-se N linhas descrevendo as avaliações em si, cada uma no formato FILME NOTA, onde FILME é uma palavra sem espaços e NOTA é um inteiro entre 1 e 10.

Output

O output do seu programa depende da flag dada:

• Se a flag for 1, o output deve ser uma linha contendo um único inteiro, a quantidade de filmes diferentes que tiveram pelo menos uma avaliação.
• Se a flag for 2, o output deve ser uma linha contendo uma palavra e um inteiro (separados por um espaço): o nome do filme que foi avaliado mais vezes, e o número de vezes que foi avaliado (é garantido que existe um único filme que foi avaliado mais vezes que todos os outros).
• Se a flag for 3, o output deve conter os nomes dos filmes com nota média positiva, um por linha, por ordem alfabética. Note que para estabelecer a ordem alfabética pode usar a ordem natural das Strings, não tendo de se preocupar com o facto das letras serem maiúsculas ou minúsculas.

Dicas

É livre para fazer fazer como quiser, mas é sugerido fazer da seguinte maneira:

• [flag 1] use uma árvore binária de pesquisa (BSTree). Se inserir todos os filmes na árvore (de que tipo devem ser os nós da árvore?), saber quantos existem é saber quantos nós tem a árvore... (também pode usar um dicionário para o mesmo efeito).
• [flag 2] use um TAD dicionário (BSTMap) para guardar o número de ocorrências de cada filme (de que tipos devem ser as chaves e os valores deste dicionário?). De dada vez que lê uma avaliação, é só ir ao dicionário e incrementar a frequência do respectivo filme. No final basta percorrer todos os filmes e encontrar o que teve mais ocorrências (ou pode optar por cada vez que incrementa, verificar se passou a ter um novo máximo).
• [flag 3] use um outro TAD dicionário (BSTMap) para guardar a soma das notas de cada filme (de que tipos devem ser a chave e o valor?). No final percorra todas as chaves (os filmes) e imprima aqueles cuja média seja positiva (é só dividir pelo quantidade de avaliações... que está guardada no dicionário que criou para a flag anterior). Em relação à ordem alfabética, como o dicionário está numa árvore de pesquisa, e o método que as devolve percorre a árvore em inorder, logo estas já são obtidas precisamente por ordem alfabética!

Exemplo de Input/Output para a Flag 1

1
10
StarWarsVIII 5
BladeRunner2049 8
ShapeOfWater 4
Solo 6
StarWarsVIII 2
Solo 4
BladeRunner2049 4
ShapeOfWater 1
GetOut 9
BladeRunner2049 6

5

Exemplo de Input/Output para a Flag 2

2
10
StarWarsVIII 5
BladeRunner2049 8
ShapeOfWater 4
Solo 6
StarWarsVIII 2
Solo 4
BladeRunner2049 4
ShapeOfWater 1
GetOut 9
BladeRunner2049 6

BladeRunner2049 3

Exemplo de Input/Output para a Flag 3

3
10
StarWarsVIII 5
BladeRunner2049 8
ShapeOfWater 4
Solo 6
StarWarsVIII 2
Solo 4
BladeRunner2049 4
ShapeOfWater 1
GetOut 9
BladeRunner2049 6

BladeRunner2049
GetOut
Solo

Estruturas de Dados (CC1007)
DCC/FCUP - Faculdade de Ciências da Universidade do Porto