SPOJ Eleições - 3773

Programação Java
#1

Pessoal, estou com um problema de testes.

Segue abaixo o Problema:

O prefeito de Piraporinha do Sul foi afastado de seu cargo, devido a acusações de corrupção em contratos da prefeitura, e por isso foram convocadas novas eleições para prefeito. Procurando uma renovação política, a comissão eleitoral permitiu que mesmo candidatos de fora da cidade concorressem ao cargo de prefeito.

Devido a essa nova regra, houve uma quantidade muito grande de candidatos à prefeitura. O software da comissão eleitoral de Piraporinha do Sul não estava preparado para isso, e por isso você foi contratado para escrever um programa que, dados os votos lançados pelos habitantes da cidade, decide qual candidato ganhou.

Entrada
A entrada é composta de um único caso de teste. A primeira linha contém um inteiro N representando o número de votos. Nas próximas N linhas, haverá um inteiro Xi, que representa o i-ésimo voto (os candidatos são identificados por inteiros).

Saída
Para cada conjunto de teste da entrada seu programa deve produzir uma única linha, contendo o número do candidato que venceu (aquele que obteve mais votos). Você pode supor que existe apenas um vencedor.

Restrições
1 ≤ N ≤ 100000
1 < Xi ≤ 1000000000
Exemplo
Entrada

5
1000
1000
2588
4000
2587

Saída

1000

Entrada

4
4000
3500
4000
4000

Saída

4000

Segue meu código abaixo.

import java.util.Scanner;

class eleicoes {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n, a, m = 0;
		int vet[] = new int[100000];
		n = scan.nextInt();
		for (int i = 0; i < n; i++) {
			a = scan.nextInt();
			vet[a] += 1;
		}
		for (int i = 0; i < vet.length; i++) {
			if(m<vet[i]){
				m = i;
			}
		}
		System.out.println(m);
	}
}

Ou seja, ele vai mostrar o ID do candidato que foi mais votado. Esta funcionando em java, me falaram que tinham que usar Hashmap… MAS… PRA QUE?
Alguem saberia me dizer?

#2

Talvez para associar o voto de cada candidato a uma chave, que seria seu id…mas pelo que vc disse não tem necessidade de usar um mapa, é apenas uma outra forma de resolver.

#3

Seu programa não está funcionando. Para provar isso, tente com o seguinte conjunto de entrada:

1
1000000000

Você precisa usar um hashmap, porque a cidade tem no máximo 100000 votos, mas o número do candidato pode estar entre 1 e 1000000000 . Você está supondo que o número do candidato é no máximo 100000. Portanto sua solução é inválida.

#4

aaaaahhhhhhhhh
ok… agora preciso estudar hashmap boa noticia kkkkkkk
mas pergunta que nao quer calar… no que isso me atrapalha? pois eu vou saber que… o fulado “1000000000” foi votado 1 vez pois aparece uma vez só… pelo menos foi isso oque eu entendi e é isso oque meu software faz… eu acho (tenho certeza) que nao entendi o problema :frowning:

#5

É o seguinte. Os problemas do SPOJ têm restrições de memória. Digamos que você tente corrigir sua solução, reservando um array de 1.000.000.000 elementos. O problema é que o tamanho desse array é de 4.000.000.000 bytes, o que normalmente não é aceito no SPOJ.
E é por isso que você precisa usar um Map<Integer, Integer>, onde a chave é o número do candidato, e o valor é a quantidade de votos que esse candidato teve. Então, para determinar qual é o candidato com mais votos, você percorre o mapa olhando os valores e determinando o valor máximo.

#6

cara o primeiro numero de entrada é o numero de candidatos… porque seria de 1 a 1000000000 ???

#7

ok… mas a cada voto é somado pela id?
como vou saber que acabou os votos?

#8

Você não leu o problema mesmo. N é o número de votos, não o de candidatos. A sua solução está correta se houver 9999 candidatos possíveis (diga porque não funciona se houver um candidato 10000); mas não funciona se o número do candidato for 1.000.000.000 como está escrito no enunciado.

#9

serio… nao entendi mesmo.
pois cara… qual o problema dele receber o dado dentro de uma variavel de valor inteiro se é só 1000000000.
???

#10

Mas olha agora…

import java.util.Scanner;

class eleicoes {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n, a, m = 0;
		int vet[] = new int[1000000000];
		n = scan.nextInt();
		if (n < 100000) {
			for (int i = 0; i < n; i++) {
				a = scan.nextInt();
				vet[a] += 1;
			}
			for (int i = 0; i < vet.length; i++) {
				if (m < vet[i]) {
					m = i;
				}
			}
			System.out.println(m);
		}
	}
}

Se o vetor for muito grande, ele daria tempo excedido…
Ja que eu coloquei um espaço maior ele da Erro em tempo de execução… de qualquer forma o algoritmo esta errado mas em algum outro lugar, nao no tamanho do vetor.

#11

Seu algoritmo está certo, mas não é adequado para resolver o problema - esquisito, não?

É que o Spoj requer que:

  • O algoritmo esteja certo;
  • Que rode dentro de um determinado tempo;
  • Que não esgote a memória disponível.

Do jeito que você escreveu, o programa irá esgotar a memória disponível, então será rejeitado.

#12

[quote=denisspitfire] if (m < vet[i]) { m = i; }
[/quote]
m é o número de votos ou o número do candidato? Aqui estás a usar para as duas coisas!

#13

Yeaahh agora entendi, mente cansada é uma beleza rs.
(solução para problemas de programação… dormir)
Seguinte fiz esse código porém… como eu posso verificar quantas vezes a ID foi acessada e jogar dentro da variavel m?

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

class eleicoes {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n, a, m = 0;
		Map<Integer, Integer> pessoas = new HashMap<Integer, Integer>();
		n = scan.nextInt();
		if (n < 100000) {
			for (int i = 0; i < n; i++) {
				a = scan.nextInt();
				pessoas.put(n,a);
			}
		}
		System.out.println(m);
	}
}
#14

acho que posso usar o equals pro segundo parametro… mas… como? estou perdidao a respeito disso.

#15

Aqui vai um programa que gera um arquivo que o SPOJ poderia usar para testar seu programa. Rode esse programa e ele irá gerar um arquivo “teste.txt”. Então, passe esse arquivo para seu programa (como seu programa lê da entrada-padrão, use o redirecionamento - “java -cp . SeuPrograma < teste.txt”).
Se ele rodar em mais de dois segundos, seu programa não vai passar no SPOJ. Esse conjunto de dados que esse programa de teste vai gerar deve fazer com que seu programa ache que o candidato 71186000 ganhou porque recebeu 4 votos.

import java.util.*;
import java.io.*;

public class GeradorArquivoTesteSPOJ {
    public static void main (String[] args) throws IOException {
		PrintWriter pw = new PrintWriter ("teste.txt");
		Random r = new Random (1); // estipulamos um valor fixo para a semente do gerador de números aleatórios
		// para que os resultados possam ser reprodutíveis. Adicionalmente, vou também
		// indicar qual o candidato mais votado e mostrar o resultado na saída-padrão. 
		// Para o valor 1, temos:
		// O candidato 71186000 ganhou porque obteve 4 votos
		Map<Integer, Integer> votosPorCandidato = new TreeMap<Integer, Integer>();
		int nVotos = 100000;
		int nMaxCandidato = 1000000000;
		pw.println (nVotos);
		for (int i = 1; i <= nVotos; ++i) {
			// Artificialmente, estou reduzindo um pouco a variabilidade dos números possíveis para
			// os candidatos, porque senão não consigo ter um candidato com mais de um voto. 
			int nCandidato = 1000*(1+r.nextInt (nMaxCandidato/1000));
			pw.printf ("%d%n", nCandidato);
			if ( ! votosPorCandidato.containsKey (nCandidato)) {
				votosPorCandidato.put (nCandidato, 1);
			} else {
				votosPorCandidato.put (nCandidato, votosPorCandidato.get(nCandidato) + 1);
			}
		}
		pw.close();
		int nCandidatoComMaisVotos = 0;
		int nMaximoVotos = 0;
		for (Map.Entry<Integer, Integer> entry : votosPorCandidato.entrySet()) {
			Integer candidato = entry.getKey();
			Integer votos = entry.getValue();
			if (votos > nMaximoVotos) {
				nCandidatoComMaisVotos = candidato;
				nMaximoVotos = votos;
			}
		}
		System.out.printf ("O candidato %d ganhou porque obteve %d votos%n", nCandidatoComMaisVotos, nMaximoVotos);
	}
}
#16

Mas o meu código ainda falta mostrar os valores da hash… engraçado que quando eu uso pessoas.size(); ele mostra 1…
???
nao estou inserindo certo?
Depois de inserir preciso contar quantas vezes cada um aparece. Dai mostrar ele.

import java.util.HashMap;   
import java.util.Map;   
import java.util.Scanner;   
  
class eleicoes {   
    public static void main(String[] args) {   
        Scanner scan = new Scanner(System.in);   
        int n, a, m = 0;   
        Map<Integer, Integer> pessoas = new HashMap<Integer, Integer>();   
        n = scan.nextInt();   
        if (n < 100000) {   
            for (int i = 0; i < n; i++) {   
                a = scan.nextInt();   
                pessoas.put(n,a);   
            }   
        }   
        System.out.println(m);   
    }   
}
#17

Você está “trapaceando” no SPOJ. Você teria de responder isso sozinho :slight_smile:

Isto posto, você deu uma olhada no programa que eu usei para gerar o arquivo de entrada para seu programa? Experimente lê-lo direitinho e veja como é que eu consegui contar quantos votos tem um determinado candidato. (Eu uso isso para poder indicar qual o candidato que tem mais votos, para você poder conferir com sua solução.)

#18

ahh to nada! kkkkk
eu tentei… mas cara eu nao consegui entender mta coisa. Porque eu nao sei onde o hashmap me ajuda nisso…
Pergunta.
O Hashmap, duplica dados?
Como posso imprimir o “vetor” sendo que é um hash? soap(map ) nao funciona…
pois só imprime zero…
outra…
na parte que eu estou inserindo os valores…
se depois eu colocar
map.size() aparece zero…
estou muito perdidao nesse hash…
como vou inserir dados no hash? esse meu codigo esta errado?

#19

Um Map é uma estrutura de dados que serve para armazenar pares chave -> valor.
A função dessa estrutura é, dada uma chave, retornar o valor correspondente, sem ter de fazer uma “busca linear” (ou seja, ficar comparando um por um até achar).
A idéia é que você cadastre como chave o número do candidato, e como valor a contagem de votos desse candidato.

#20

Bom vamos lá…

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

class eleicoes {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n, a;
		Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
		n = scan.nextInt();
		if (n < 100000) {
			for (int i = 0; i < n; i++) {
				a = scan.nextInt();
				if (map.containsKey(a)) {
					map.put(a, map.get(a) + 1);
				} else
					map.put(a, 1);
			}
			int nCandidatoComMaisVotos = 0;
			int nMaximoVotos = 0;
			for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
				Integer candidato = entry.getKey();
				Integer votos = entry.getValue();
				if (votos > nMaximoVotos) {
					nCandidatoComMaisVotos = candidato;
					nMaximoVotos = votos;
				}
			}
			System.out.println(nCandidatoComMaisVotos);
		}
	}
}

Fiz aqui de uma maneira que “resolvesse” o problema. Pois agora esta dando tempo limite excedido… creio que terá de ser feito em outra linguagem… Infelizmente… pois nao tem nenhum envio em Java.
Mas a minha questão nao é essa… só quero saber pq foi criado uma TreeMap ao invez de um hashmap… qual a diferença?(neste problema)