Problema A - Eleições Olímpicas

As Olimpíadas Nacionais de Informática vão a votos para eleger um novo conselho de administração! Este ano há N votantes e K listas candidatas ao lugar.

Parte I

São dadas as intenções de voto de cada um dos N votantes, isto é, para cada um dos votantes é dado um número de 1 a K que indica a sua lista preferida. A lista vencedora é a que obtiver uma pluralidade de votos, isto é, quem tiver mais votos que qualquer outra lista. Caso não exista uma lista com uma pluralidade de votos, então considera-se que houve um empate.

Determina se houve um empate e caso contrário qual a lista vencedora. Caso uma lista vença as eleições então o output do teu programa deve ser o número da lista vencedora. Caso o resultado seja um empate o output do teu programa deve ser 0.

Exemplo

Se N = 7, K = 3 e tivermos as seguintes intenções de voto:

Ou seja, o primeiro votante escolheu a lista 1, o segundo votante também, ... Neste caso a lista 1 tem 3 votos, a lista 2 tem 2 votos e a lista 3 tem 2 votos. Logo a lista vencedora é a lista 1.

Mas se tivermos as seguintes intenções de voto:

Então temos um empate entre a lista 1 e a lista 2.

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados num grupo:

Parte II

Novamente, são dadas as intenções de voto de cada um dos N votantes, isto é, para cada um dos votantes é dado um número de 1 a K que indica a sua lista preferida. Para ter uma visão melhor do resultado das eleições, queremos calcular um histograma que sumariza as eleições. Mais especificamente, queremos uma sequência ordenada por lista com o número de votos que obteve.

Exemplo

Se N = 7, K = 3 e tivermos as seguintes intenções de voto:

Então o resultado deverá ser:

• 1 4 2

Visto que a lista 1 obteve 1 voto, a lista 2 obteve 4 votos e a lista 3 obteve 2 votos.

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados num grupo:

Parte III

Vamos agora considerar uma eleição especial. Em vez de indicar uma lista preferida, cada um dos N votantes especifica uma sequência de K listas, ordenada por preferência. Isto é, a primeira lista da sequência representa a lista favorita do votante, a segunda lista a segunda favorita, etc.

Para um par de listas a e b dizemos que a lista a é preferida em relação à lista b se a maioria dos votantes (ou seja, mais de metade) coloca a lista a à frente da b na sua sequência de preferências. Um vencedor das eleições é uma lista que é preferida em relação a todas as restantes listas. Se não houver nenhuma lista com esta propriedade, então considera-se que houve um empate.

Determina se houve um empate e caso contrário qual a lista vencedora. Caso uma lista vença as eleições então o output do teu programa deve ser o número da lista vencedora. Caso o resultado seja um empate o output do teu programa deve ser 0.

Exemplo

Se N = 5, K = 3 e tivermos as seguintes intenções de voto:

Ou seja, o primeiro votante prefere primeiro a lista 1, depois a lista 3 e finalmente a lista 2. O segundo votante prefere primeiro a lista 2, depois a 1 e finalmente a 3, etc. A lista 1 é preferida em relação à lista 2 visto que os votantes 1, 3 e 5 a colocam primeiro na sequência de preferências. A lista 1 é preferida em relação à lista 3 visto que os votantes 1, 2 e 5 a colocam primeiro na sequência de preferências. Logo a lista 1 é a vencedora.

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados num grupo:

Sumário de subtarefas

Os casos de teste do problema estão organizados em 3 grupos com restrições adicionais diferentes:

Input

Nota: O formato de input é diferentes nas três partes.

A primeira linha contém um inteiro P, que representa a parte que o caso de teste representa. Se for 1, então o caso de teste refere-se à Parte I, se for 2 então refere-se à Parte II, se for 3 então refere-se à Parte III.

Segue-se uma linha com dois inteiros separados por espaços, primeiro N, representando o número de votantes, seguido de Ko número de listas.

Partes I e II

Nestas partes adicionalmente segue-se uma linhas, contendo N inteiros separados por espaços, representando as intenções de voto de cada votante.

É garantido que vada voto é dado por um inteiro entre 1 e K.

Parte III

Nesta parte adicionalmente seguem-se N linhas, cada uma contendo K inteiros separados por espaços, representando a sequência de preferências de cada votante.

É garantido que vada cada sequência de preferências contém inteiros distintos entre 1 e K.

Output

Partes I e III

O output deve conter uma única linha com um inteiro, 0 caso o resultado da eleição seja um empate, ou um inteiro entre 1 e K representando a lista vencedora.

Parte II

O output deve conter uma única linha com K inteiros separados por espaços, representando o número de votos de cada lista.

Nota: deve existir exatamente um único espaço entre cada inteiro e não deve haver nenhum espaço no final da linha (ou seja, após o último inteiro deve aparecer apenas uma mudança de linha). Se não respeitares este formato o resultado de uma submissão será Presentation Error (consulta as instruções para mais informações).

Input do Exemplo 1

1
7 3
1 1 1 2 2 2 3

Output do Exemplo 1

0

Explicação do Exemplo 1

Este exemplo corresponde ao segundo exemplo da Parte I mencionado no enunciado.

Input do Exemplo 2

2
7 3
3 1 2 2 2 3 2

Output do Exemplo 2

1 4 2

Explicação do Exemplo 2

Este exemplo corresponde ao exemplo da Parte II mencionado no enunciado.

Input do Exemplo 3

3
5 3
1 3 2
2 1 3
3 1 2
2 3 1
1 2 3

Output do Exemplo 3

1

Explicação do Exemplo 3

Este exemplo corresponde ao exemplo da Parte III mencionado no enunciado.