TOPIC

PROBLEM 1062 - URI Fórum 1.0

beecrowd asked on Feb 8 2013

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • ttogores replied 9 years ago

    Por que o toolkit devolve No como resposta para o seguinte caso de teste?

    8
3 4 7 8 5 6 1 2
0
0

    [list:2iveawbe]

    • Os vagões 1 e 2 entram e saem da estação. Estação: Vazia; Trilho B: 1 2
    • Os vagões 3 e 4 entram na estação. Estação: 4 3; Trilho B: 1 2
    • Os vagões 5 e 6 entram na estação. Estação: 6 5 4 3; Trilho B: 1 2
    • Os vagões 5 e 6 saem da estação. Estação: 4 3; Trilho B: 5 6 1 2
    • Os vagões 7 e 8 entram na estação. Estação: 8 7 4 3; Trilho B: 5 6 1 2
    • Os vagões 7 e 8 saem da estação. Estação: 4 3; Trilho B: 7 8 5 6 1 2
    • Os vagões 3 e 4 saem da estação. Estação: Vazia; Trilho B: 3 4 7 8 5 6 1 2 [/list:u:2iveawbe]

  • oman10 replied 9 years ago

    Não preciso mais de ajuda para este problema, já o resolvi. :) Obrigado.

  • oman10 replied 9 years ago

    Olá, já faz dias que estou tentando resolver este problema. Agora criei uma solução e acho que estou quase lá. Submeti este código abaixo e recebi 90% WA. Se alguém puder me ajudar a finalizar este código, pode ser dica, ou até onde meu código está errando. Por mais agradeço a ajuda.

    Segue o código abaixo:

    Resolvido :)

  • pmoggi replied 9 years ago

    **OBS: Acabei achando a resposta para minha pergunta:

    • O algoritmo deve parar quando a primeira entrada da permutação for 0 Seria interessante alterarem essa parte na descrição do problema para não haver mais confusões **

    Olá a todos, Estou com uma pequena duvida na seguinte parte da descrição:

    "Em cada uma das próximas N linhas de entrada haverá uma permutação..."

    Exatamente N linhas ou ? Pois o toolkit aceita mais de N linhas

    E o Cristhian "comentou" um caso de teste que ultrapassa essas N linhas no caso, 5:

    ... Estou recebendo 10% resposta errada e creio que seja pelo fato do meu algoritmo estar preso em N linhas

    **OBS: Acabei achando a resposta para minha pergunta:

    • O algoritmo deve parar quando a primeira entrada da permutação for 0 Seria interessante alterarem essa parte na descrição do problema para não haver mais confusões **

  • ggroth replied 9 years ago

    estou recebendo wa sem porcentagem... o q pode ser?[/quote]

    Teste com a seguinte entrada:

    5
3 2 5 4 1
0
0

    Dica: esse problema é mais fácil de ser resolvido usando a implementação de pilha da stl (stack)

  • mfdoliveira replied 9 years ago 

    #include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    int i;
    int contzero = 0;
    scanf("%d", &i);
    int lasti = i;
    //vetor
    int indVetor = 0;
    int Vetor[1000];

    //pilha
    int Pilha[1000];
    int addPilha = 0; //indica em que altura deve-se add na pilha
    int indPilha = -1; //indica em que altura esta na pilha
    int j = 0;

    while ( i > 0 && contzero < 2)
    {
        while (j < i)
        {
            scanf("%d", &Vetor[j]);
            j++;
        }

        bool erro =  false;
        int a = 1;

        while( indVetor < i && !erro)
        {
            if (Vetor[indVetor] == a)
            {
                indVetor++;
                a++;
            }
            else if (Pilha[indPilha] > 0 && indPilha >= 0 && Pilha[indPilha] == Vetor[indVetor])
            {
                Pilha[indPilha] = 0;
                if (indPilha != 0)
                {
                    indPilha--;
                }
                indVetor++;
            }
            else if (a <= i)
            {
                Pilha[addPilha] = a;
                addPilha++;
                indPilha = addPilha-1;
                a++;
            }
            else
            {
                erro = true;
            }
        }

        if (erro == true)
        {
            printf("No\n");
        }
        else
        {
            printf("Yes\n");
        }

        //vetor
        indVetor = 0;
        Vetor[1000] = NULL;

        //pilha
        Pilha[1000] = NULL;
        addPilha = 0; //indica em que altura deve-se add na pilha
        indPilha = -1; //indica em que altura esta na pilha

        scanf("%d", &i);

        if (i == 0)
        {
            contzero++;
            scanf("%d", &i);
            lasti = i;
            //if (i != 0)
            //{
                printf("\n");
            //}
            j = 0;
        }
        else
        {
            j = 1;
            Vetor[0] = i;
            i = lasti;
            contzero = 0;
        }

    }

    return 0;
}

    estou recebendo wa sem porcentagem... o q pode ser?

  • aluiz1 replied 9 years ago

    Estou obtendo 10% de erro e não consigo achar =/. O que está faltando?

    import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        boolean iniciou = false;
        while(true){

            int n = Integer.valueOf(in.readLine());
            if (n==0)
                break;

            if (iniciou){
                writer.newLine();
                iniciou=false;
            }
            String[] linha = null;
            while(true){

                linha = in.readLine().split(" ");
                if (linha.length==1)
                    break;

                Stack<Integer> pilha = new Stack<Integer>();
                Stack<Integer> pilha2 = new Stack<Integer>();
                for(int i=n-1;i>=0;i--)
                    pilha2.add(Integer.valueOf(linha[i]));
                int i=1;

                while(true){
                    pilha.add(i);

                    while (true){
                        if (pilha.isEmpty() || pilha2.isEmpty())
                            break;
                        if (pilha2.peek()==pilha.peek()){
                            pilha.pop();
                            pilha2.pop();
                        }else
                            break;
                    }

                    if (i==n)
                        break;

                    i++;
                }

                if (pilha.empty())
                    writer.write("Yes");
                else
                    writer.write("No");

                writer.newLine();

            }

            iniciou=true;}
        writer.flush();
    }
}

  • oman10 replied 9 years ago

    Legal, valeu pela explicação. Vou tentar implementar. :)

  • oman10 replied 9 years ago

    ninguém?

  • oman10 replied 9 years ago

    Não entendi o problema. :( Alguma dica? Não entendi o porque do Yes ou No. 4 2 3 1 5 - No 2 3 1 5 4 - Yes

    Alguma dica que explique o motivo do primeiro ser No e não Yes? Não entendi muito bem. Se puder me dizer.

  • fptominc replied on Jun 15 2013

    Tenho, as unicas variaveis que eu realmente preciso me preocupar em zerar são as 2 pilhas, ja que o resto eu leio todas as vezes... Zero as pilhas sempre que chego no final do processamento ou o cara entra com o 0 no nivel mais interno... Acho que estou enfrentando aquele paradigma da computação: "Na minha maquina funciona" haha

  • jbez10 replied on Jun 15 2013

    Tem certeza que a pilha está sendo limpa e as variáveis resetadas a cada caso de teste?

    Peço isso porque aquele caso que te enviei por email era o 4º caso de teste e no primeiro, que continha a mesma sequência ele deu a resposta correta. Tente verificar isso, talvez ajude.

  • fptominc replied on Jun 15 2013

    Ola Cristhian, obrigado pelas entradas... Enfim, testei aqui e a unica diferença da minha saida com a do toolkit foi uma linha em branco no final do arquivo... Coloquei para imprimi-la e submeti novamente, porem recebi WA como resposta... Ja to desanimando com esse problema :(

  • crbonilha replied on Jun 15 2013

    Bom, apelei e gerei todos as permutações possíveis:

    https://www.dropbox.com/s/c3ea896cb8v02 ... os_in2.txt

    De 3 a 6, espero que sirva.

  • fptominc replied on Jun 14 2013

    Boa noite, estou recebendo wrong answer apesar de todos os testes que eu fiz produzirem o resultado correto... Alguem pode me ajudar a tentar encontrar meu erro??

    #include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;

template <class T1>
class Pilha {
private:
    T1 A[1001];
    int topo;
public:
    Pilha();
    T1 pop();
    void Push(T1 A);
    bool Pilhavazia();
    void EsvaziaPilha();
    T1 Checktopo();
};

template <class T1>
Pilha<T1>::Pilha() {
    topo = -1;
}

template <class T1>
T1 Pilha<T1>::pop() {
    return (this->A[this->topo--]);
}

template<class T1>
void Pilha<T1>::Push(T1 A) {
    this->A[++this->topo] = A;
}

template<class T1>
bool Pilha<T1>::Pilhavazia() {
    return (this->topo == -1);
}

template<class T1>
void Pilha<T1>::EsvaziaPilha() {
    this->topo = -1;

}

template<class T1>
T1 Pilha<T1>::Checktopo() {
    return (this->A[this->topo]);
}

int main(int argc, char **argv){
    Pilha<int> A,B;
    int N,S[1000];
    Fora:
    while(scanf("%d", &N)&&N){
        Top:
        for (int i = N; i >0 ; i--){
            A.Push(i);
        }
        for (int i = 0; i < N; i++){
            scanf("%d", &S[i]);
            if(i==0 && S[0] == 0){
                A.EsvaziaPilha();
                B.EsvaziaPilha();
                puts("");
                goto Fora;
            }
        }
        for (int i = 0; i < N; i++){
            while(A.Checktopo() < S[i] && !A.Pilhavazia()){
                B.Push(A.pop());
            }
            if(A.Checktopo() == S[i]){
                A.pop();
            }
            if(B.Checktopo() == S[i]){
                B.pop();
            }
        }
        if(A.Pilhavazia() && B.Pilhavazia()){
            printf("Yes\n");
        }else
            printf("No\n");
        A.EsvaziaPilha();
        B.EsvaziaPilha();
        goto Top;
    }
    return 0;
}

    PS: Desconsiderem os goto haha

  • jbez10 replied on Jun 14 2013

    Respondemos o feedback no seu email.

  • fptominc replied on Jun 14 2013

    A ultima foi a 168360

  • jbez10 replied on Jun 14 2013

    Qual é o número da sua submissão?

    Alguma entradas do portal são as originais, disponíveis em outros locais, porém outras são geradas para testar diversos casos de teste, inclusive os casos de borda. Por isso alguns problemas acabam não passando aqui.

  • fptominc replied on Jun 14 2013

    Olá Cristhian, obrigado pelas entradas mas infelizmente essas entradas não ajudaram a encontrar o erro... O engraçado é que consegui accepted no UVA e no ACM e aqui não passa :(

  • fptominc replied on Jun 13 2013

    Alguem tem mais casos de testes? ja testei com varios e nada de accepted :/

2 of 2