Descrição
Ecaterimburgo, Rússia, é uma cidade com um curioso sistema de votação. Em uma eleição em que haja V vagas para um cargo, cada eleitor tem direito a fazer V votos, ordenados em sua ordem de preferência. Assim, se, por exemplo, há 3 vagas de senador, cada eleitor vota em até 3 nomes. Serão eleitos os candidatos que tiverem o maior número de votos, sem importar em que posição da preferência do eleitor está o candidato. Apenas quando há empate no número de votos se torna relevante a ordem dada pelos eleitores. Ganha aquele candidato que tiver mais indicações em primeiro lugar. Se persistir o empate, em segundo lugar, e assim por diante. Caso dois ou mais candidatos que estejam em posição de serem eleitos tenham exatamente o mesmo número de indicações em todas as posições, todos são eleitos (podendo inclusive exceder o número de vagas).
Candidatos com zero votos podem ser eleitos se ainda existir vagas disponíveis.
Entrada
A entrada é composta por diversas instâncias e termina com final de arquivo (EOF).
Cada instância começa com o número N de eleitores, o número K de candidatos e V de vagas. A seguir vêm N linhas com os votos de cada um dos eleitores. Em seu voto, o eleitor i indicará o número Li de candidatos em quem votará, e os índices destes candidatos na sua ordem de preferência. Índices de candidatos fora do intervalo [1, K] significam votos em branco apenas para a opção de preferência correspondente. Se indicar mais que V votos, os últimos serão desconsiderados. Um eleitor nunca indica o mesmo candidato mais de uma vez.
A entrada deve ser lida da entrada padrão.
Saída
Para cada instância da entrada seu programa deverá imprimir, em uma única linha, a lista de candidatos eleitos ordenada pela classificação dos candidatos na eleição. No caso de dois candidatos possuirem a mesma classificação, o de menor índice vem antes.
A saída deve ser escrita na saída padrão.
Restrições
• 1 ≤ N ≤ 10^5
• 1 ≤ V ≤ K ≤ 100
• 1 ≤ Li ≤ 100
Exemplos de Entrada | Exemplos de Saída |
---|---|
5 3 2 |
3 1 |
Efetue Login ou Cadastre-se para submeter uma solução.
Adaptado por Erich Rodrigues | Competição: USP - Seletiva para Maratona de Programação, 2013