SPOJ 1388. Vivo ou Morto[Resolvido]

25 de abril de 2012 10 respostas

Vinicius_Zibetti_Res 25 de abril de 2012

Gente não estou conseguindo saber o que tem de errado no meu algoritmo pra resolucao deste probleminha ai do SPOJ, segue solucao:
(Tomando Resposta errada)

import java.io.PrintWriter;
import java.util.Scanner;

public class MortoVivo {
	private final int MAX_PARTICIPANTES = 100;
	private final int MAX_RODADAS = 100;

	public void solve() {
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int test = 1; // numero do teste
		while (true) {
			int p, r, rest, comm, pComm; //p = participantes totais, r = rodadas, rest = participantes restantes da rodada, comm = comando da rodada (0 ou 1) que o chefe deu, pComm é o comando que cada aprticipante faz na rodada
			p = in.nextInt();
			int[] participantes = new int[p];
			r = in.nextInt();
			if (p == 0 && r == 0)
				break;
			for (int i = 0; i &lt; p; i++) {
				participantes[i] = in.nextInt();
			}
			for (int i = 0; i &lt; r; i++) {
				rest = in.nextInt();
				comm = in.nextInt();
				int z = rest;
				for (int j = 0; j &lt; rest; j++) {
					pComm = in.nextInt();
					if (comm != pComm) {
						participantes[j] = -1;
						z--;
					}
				}
				int[] aux = new int[z];
				for (int j = 0, k = 0; j &lt; rest; j++) {
					if (participantes[j] != -1) {
						aux[k++] = participantes[j];
					}
				}
				participantes = aux;
			}
			out.println("Teste " + (test++) + " \n" + participantes[0]);
		}
		out.close();
	}

	public static void main(String[] args) {
		new MortoVivo().solve();
		System.exit(0);
	}
}

10 Respostas

entanglement 25 de abr. de 2012

Também não sei (he he he). Estou dando um monte de chutes agora, que é função de quem já viu muita coisa nessa vida.

Você :

a) Debugou o programa para ver se não tem alguma coisa boba, como um nextInt que está lendo o dado errado? (Já vi muitos algoritmos certos que davam pau porque os dados foram entrados incorretamente )

b) Pegou a entrada, e refez o programa usando um “teste de mesa” (ou seja, fez as coisas no papel, em vez de sair cuspindo tudo no computador)?

Vinicius_Zibetti_Res 25 de abr. de 2012

Sim, sinceramente criei muitos testes, no qual debuguei eles na mão ( de raiva que eu to de tomar wrong answer) e depois coloquei o algoritmo pra rodar e deu a mesma resposta que eu cheguei no teste de mesa…

Sinceramente não sei onde que ta errado…

gomesrod 25 de abr. de 2012

Momento histórico

Vinicius_Zibetti_Res 26 de abr. de 2012

Pois é né…
Os testes que eu fiz na mão deram o resulatdo esperado mesmo, ainda testei no computador pra ver, tambem deu certo…
PRAGA DE RESPOSTA ERRADA !

gomesrod 26 de abr. de 2012

Não entendi bem a situação… para você está tudo certo, mas o resultado não bate com o exemplo que está lá no site?

Vc observou que abaixo tem um pessoal colocando comentários dizendo que o exemplo está com erro?

Vinicius_Zibetti_Res 26 de abr. de 2012

Nao…

Eu realizei varios testes de mesa por mim mesmo que eu criei.
Testei todos eles na mão, segundo o que o problema pede.
Peguei estes testes e joguei no meu algoritmo.
Todos eles estavam batendo com o resultado obtido nos testes que eu fiz na mão.

Obs: Os do site estão corretos sim, faz o teste de mesa pra vc ver.

O que está acontecendo é que quando eu dou um submit na minha solução, o site me diz: “resposta errada”, ou seja, minha solução apresenta algum erro lógico.

gomesrod 26 de abr. de 2012

Quando submeto o seu programa dá Tempo Excedido.

Aliás, estou conhecendo agora esse mecanismo de submeter os problemas e ter a avaliação automaticamente, muito legal!

Conforme tiver tempo livre vou tentando analisar, enquanto isso vamos ver se alguém aparece com mais idéias…

entanglement 26 de abr. de 2012

Ou seja:
a) Ou seu algoritmo é ruim para entradas de dados grandes, ou
b) você tem de reimplementá-lo em outra linguagem (não Java, que é notoriamente lenta para resolver os problemas do SPOJ).

Note que P pode ser 100 e R pode ser 100, e o tempo limite é de 1 segundo. Veja o que ocorre no seu programa se você entrar com 100 participantes e 100 rodadas, e veja quanto tempo ele leva.

Vinicius_Zibetti_Res 26 de abr. de 2012

AH se o problema fosse tempo limit, ele reclamaria “tempo limite excedido”, mas ele esta reclamando “resposta errada”.

Vinicius_Zibetti_Res 28 de abr. de 2012

Merda, bolei outra solucao em C++, mas tava dando time limit pq eu tava usando CIN, dps q mudei ora SCANF deu certo.

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;stdio.h&gt;

using namespace std;

int nTest = 1, p, r, rest, ordem;

int main() {
        while(~scanf(&quot;%d%d&quot;, &p, &r)){
                int partic[p];
                if(!p && !r) break;
                for (int i = 0; i &lt; p; i++) {
                    scanf(&quot;%d&quot;, &partic[i]);
                }
                while (r-- &gt; 0) {
                    scanf(&quot;%d%d&quot;, &rest, &ordem);
                    int aux[rest];
                    for (int i = 0, j = 0; i &lt; rest; i++) {
                        int nCmd;
                        scanf(&quot;%d&quot;, &nCmd);
                        if(nCmd == ordem){
                            aux[j++] = partic[i];
                        }
                    }
                    for(int i = 0; i &lt; rest; i++)
                        partic[i] = aux[i];
                }
                cout &lt;&lt; &quot;Teste &quot; &lt;&lt; nTest++ &lt;&lt; &quot;\n&quot; &lt;&lt; partic[0] &lt;&lt; endl;
        }
        return 0;
}

Nunca fui tao sacaneado por 1 problema tao simples.

ID: 6921321  
DATA: 2012-04-29 09:19:24                    
PROBLEMA: Vivo ou Morto
RESULTADO: aceito            
TEMPO: 1.00
MEM: 2.6M
LING: C++ 4.3.2

Criado 25 de abril de 2012

Ultima resposta 28 de abr. de 2012

Respostas 10

Participantes 3

10 Respostas

Topicos relacionados