1062

+25

RafaelPontes replied 8 years ago

Esta questão não ficou muito clara. Não entendi realmente quais as regras de reorganização dos vagões para que saiam em ordem crescente na saída. Alguém pode dar uma explicação mais compreensível? '-'

+22

crussi replied 8 years ago

Vou dar o exemplo do último caso de teste da descrição: 1 3 2 5 4 6 Você tem duas escolhas de deslocamento para cada vagão, ou você desloca ele para a estação ou para a direção B. Como ele vem neste sentido -> (Esquerda,Direita), o primeiro vagão é o número 6 e ele não precisa entrar na estação, pois ele é o maior vagão e tem que ser o último, então até aqui tudo bem. A - 1 3 2 5 4 Est. - B - 6 O próximo vagão é o de número 4, veja agora que o vagão não pode passar direto para a direção B, pois ele tem que ficar atrás do vagão de número 5. Então neste caso vamos colocar ele na estação. A - 1 3 2 5 Est. - 4 B - 6 O próximo vagão é o de número 5 e ele pode passar direto, porque ele tem que ficar atras do vagão de número 6. A - 1 3 2 Est. - 4 B - 5 6 O próximo passo seria tirar o vagão 4 da estação e colocar ele atras do 5, e assim sucessivamente. A única restrição é que você tem que empilhar os vagões na estação, só podendo retirar o último que chegou, depois o antepenúltimo... Acho que dá pra ter uma noção agora. (y)

+12

btorres replied 7 years ago

Dica: Os N vagões estão no ponto de partida. Eles devem chegar no destino. Para isso, eles podem ir direto ao destino, ou parar na estação. Usando 3 pilhas o problema fica bem fácil de visualizar.

Exemplo: Se no ponto de partida estão os vagões 1,2,3(onde o vagão 1 é o primeiro a sair), é possível eles chegarem ao destino na ordem 1,3,2(onde 2 foi o último a chegar)? 1 sai do do ponto de partida, e chega ao destino (ok) 2 sai do ponto de partida em direcao a estação e lá fica estacionado. 3 sai do ponto de partida em direcao ao destino(ok) 2 sai da estação em direção ao destino(ok) sim

+7

lhnegri replied on Feb 17 2014

Atenção, tem uma linha em branco no final do arquivo. Submeti sem a linha e ganhei presentation error.

+5

draian replied 8 years ago

Achei confuso e li os comentários mas a realidade é... O trem vem ordenado de forma crescente e a entrada é para verificar se é possível compor o arranjo do trem ?

+5

ggroth replied 9 years ago

Os vagões sempre chegam em ordem crescente, e você precisa dizer se consegue que eles saiam conforme a entrada.

4 2 3 1 5 Vagão 1 chega e fica na estação 1 Vagão 2 chega e fica na estação 2 1 Vagão 3 chega e fica na estação 3 2 1 Vagão 4 chega e vai para a saida (pois é o primeiro da nova organização dos vagões) O próximo deveria ser o 2, mas para tirar o 2 precisa retirar o 3 da estação. Dessa forma, não é possível organizar como solicitado.

2 3 1 5 4 Vagão 1 chega e fica na estação 1 Vagão 2 chega e sai da estação (primeiro da fila) Estação: 1 Saída : 2 Vagão 3 chega e sai da estação (segundo da fila) Estação 1 saída: 3 2 (o mais à direita representa o primeiro a ter saído) O próximo da ordem é o 1 e ele já está na estação. Basta retirá-lo Estação Saída: 1 3 2 Vagão 4 chega e fica na estação Estação 4 Saída: 1 3 2 Vagão 5 chega e sai da estação Estação 4 Saída 5 1 3 2 Por último, basta retirar o 4 da estação Saída 4 5 1 3 2

Como pode-se perceber, basta usar uma pilha para resolver esse problema ;)

+5

crbonilha replied on Jun 14 2013

Entrada:

5
4 2 3 1 5 
2 3 1 5 4 
2 1 3 4 5 
2 1 5 4 3 
1 2 5 4 3 
5 4 3 2 1 
0
10
10 3 9 8 4 7 2 5 6 1 
4 7 2 1 3 6 5 8 10 9 
7 9 5 4 2 10 3 1 6 8 
1 10 9 8 7 6 5 4 3 2 
1 2 10 9 8 7 6 5 4 3 
2 1 10 9 8 7 6 5 4 3 
0
20
2 1 7 6 10 5 20 12 18 16 8 17 14 4 9 13 11 19 15 3 
3 5 18 8 16 9 12 20 4 7 1 11 6 2 19 17 13 14 15 10 
17 11 3 8 7 2 14 13 16 20 5 12 1 6 9 19 10 15 4 18 
1 9 8 7 6 5 4 3 2 20 19 18 17 16 15 14 13 12 11 10 
1 3 2 5 4 12 11 10 9 8 7 6 13 20 19 18 17 16 15 14 
2 1 5 4 3 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 
0
30
26 9 28 10 17 1 15 22 8 21 3 20 14 30 19 4 12 18 6 16 25 24 11 29 13 27 5 7 2 23 
5 14 8 22 23 13 21 3 2 18 16 12 25 9 6 17 10 27 11 19 1 28 26 7 4 20 15 29 24 30 
18 13 6 9 10 21 3 25 27 8 22 14 24 16 2 19 7 11 1 12 4 20 30 28 26 17 15 23 29 5 
2 1 3 4 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 
1 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 20 19 30 29 28 27 26 25 24 23 22 21 
2 1 3 12 11 10 9 8 7 6 5 4 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 
0
50
24 25 23 5 36 22 8 16 48 27 20 19 2 4 34 10 29 7 21 35 9 49 42 3 40 11 17 1 32 15 39 18 38 33 26 30 41 14 45 47 43 46 50 13 28 12 37 31 44 6 
39 26 16 21 38 4 9 23 34 1 8 48 28 27 20 22 2 50 11 29 40 49 44 41 3 32 17 18 42 36 19 35 46 6 5 25 13 33 10 12 24 7 15 14 31 30 37 45 43 47 
19 42 4 27 25 31 44 36 49 6 30 10 11 13 20 3 34 40 41 9 24 39 8 32 21 14 22 18 46 50 5 37 33 38 45 2 15 43 16 12 35 23 1 17 29 48 7 26 28 47 
2 1 4 3 5 13 12 11 10 9 8 7 6 21 20 19 18 17 16 15 14 24 23 22 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 
1 2 5 4 3 7 6 18 17 16 15 14 13 12 11 10 9 8 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 
2 1 3 7 6 5 4 13 12 11 10 9 8 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 
0
0

Teste as saídas no toolkit.

+3

leonardo.fernandes replied 7 years ago

Pelo menos no meu caso não se trata de Presentation Error. É Wrong Answer mesmo.

+3

FelipeZeiser replied 8 years ago

#include <stdio.h>

struct pilha{
  int TOPO;
  int VETOR[1010];
};

struct pilha criapilha()
{
  struct pilha P;
  P.TOPO = -1;
  return P;
}

int pilhavazia(struct pilha P)
{
  if(P.TOPO==-1)
    return 1;
  else
    return 0;
}

int tamanhopilha(struct pilha P)
{
  return P.TOPO+1;      
}

int pilhatopo(struct pilha P)
{
  return P.VETOR[P.TOPO];
}

struct pilha push(int VLR,struct pilha P)
{
  P.TOPO++;
  P.VETOR[P.TOPO] = VLR;
  return P;
}

struct pilha pop(struct pilha P)
{
  P.TOPO--;       
  return P;
}

int main()
{
    int i, tam, v, j, cont;
    struct pilha trem, tremaux, estacao;
    while(1){
        scanf("%d",&tam);
        if(tam == 0)
            break;
        while(1){
            cont = 0;
            trem = criapilha();
            tremaux = criapilha();
            estacao = criapilha();
            for(i=0;i<tam;i++){
                scanf("%d",&v);
                if(v==0)
                    break;
                trem = push(v,trem);
            }
            if(v==0){
                printf("\n");
                break;
            }
            for(i=0;i<tam;i++){
                tremaux = push(pilhatopo(trem),tremaux);
                trem = pop(trem);
            }

            for(i=1;i<=tam;i++){
                estacao = push(i,estacao);
                if(pilhatopo(estacao) == pilhatopo(tremaux)){
                    estacao = pop(estacao);
                    tremaux = pop(tremaux);
                    cont++;
                    for(j=i;j>=1;j--){
                        if(pilhatopo(estacao) == pilhatopo(tremaux)){
                            estacao = pop(estacao);
                            tremaux = pop(tremaux);
                            cont++;
                        }else
                            break;
                    }
                }
            }

            if(cont < tam)
                printf("No\n");
            else
                printf("Yes\n");
        }
    }
}

Alguém poderia me ajudar e me dizer porque da time limit no judge?

+3

lcastro6 replied 8 years ago

#include<stdio.h>
int tam,cont=1,k,i,j;
int main(){
    while(1==1){
        inicio:
        k=0;cont=1;tam=0;
        int trem[100100],pos[100100],n,x;
        scanf("%d",&n);
        if(n==0)break;
        while(1==1){
            k=0;cont=1;tam=0;
            for(i=0;i<n;i++){
                tam++;
                scanf("%d",&pos[tam]);
                if(pos[tam]==0)goto inicio;
                trem[i+1]=i+1;
            }
            k=1;
            for(i=1;i<=n;i++){
                if(trem[i]==pos[k]){
                    k++;
                    cont++;
                    j=i;
                    trem[j]=-1;
                    while(1==1){
                        j--;
                        if(j<=0)break;
                        while(trem[j]==-1){
                            j--;
                            if(j<=0){
                                j++;
                                break;
                            }
                        }
                        if(trem[j]==pos[k]){
                            cont++;
                            k++;
                        }
                        else break;
                    }
                }
            }
            if(cont-1==n)printf("Yes\n");
            else printf("No\n");
        }
        printf("\n");   
    }
    return 0;
}

Wrong Answer 100% ... Alguem sabe pq?

+1

Roberto0 replied 9 years ago

Olá, Mateus.

Teste o seguinte caso de teste:

Espero ter ajudado.

Abraço.

+1

Mateus7 replied 9 years ago

Alguém poderia me dar casos de teste??? Estou recebendo 10% de WA!

Ai vai o código.

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

main()
{
    int a,b,c,d,e,f,g,v[1009];
    g=0;

    while(1){
        g++;

        if(g!=1) printf("\n");

        scanf("%d", &a);
        if(a==0) break;

        while(1){

            scanf("%d", &c);
            if(c==0) break;

            v[0]=c;

            for(b=1; b<a; b++)
                scanf("%d", &v[b]);

            c=0;
            e=0;
            for(b=1; b<a; b++){

                if(v[b]!=(v[b-1]-1)){

                    for(d=(b-1); d>=0; d--)
                        if(v[d]>e) e=v[d];

                    if(e>=v[b]){
                        c=1;
                        break;
                    }
                }
            }
            if(c==1) printf("No\n");
            else printf("Yes\n");
        }
    }
}

Desde já agradeço!!!

+1

ttogores replied 9 years ago

Minha entrada estava invertida.

0

dmayr0 replied 7 years ago

Olá, estava comparando a versão em inglês do problema e acho que ela está um tanto diferente da em português (bem mais confusa para ser sincero e faltando algumas partes da versão em pt). Isso é normal ou tem como reportar em algum lugar esse problema?

Link para a versão em inglês: https://www.urionlinejudge.com.br/judge ... /view/1062

0

btorres replied 7 years ago

Esses problemas de "presentation error" são muito incoerentes... Em vários problemas existe uma linha no fim de cada caso, em outros não existe, em outros não existe apenas no último... Acho que o sistema deveria ignorar esses erros de apresentação, pois creio que eles nada tem a acrescentar na resolução do problema. Não foram raros os exercícios que passei mais tempo tentando descobrir a causa do presentation error do que resolvendo o problema em si.

0

leonardo.fernandes replied 7 years ago

Olá, estou obtendo 10% de WA. Alguém tem algum caso de teste que não funcione no meu código? Todos os testes que fiz bateram com o toolkit...

#include<stdio.h>
#define SIZE 1001

struct pilha{
   int v[SIZE];
   int *top;
};

int peek(struct pilha *p){
   if(p->top > p->v)
      return *(p->top-1);
   else
      return 0;
}

int pop(struct pilha *p){
   int valor;
   if(p->top > p->v){
      p->top--;
      valor = *(p->top);
      return valor;
   }
   else
      return 0;
}

int push(struct pilha *p,int valor){
   if(p->top < p->v+SIZE){
      *(p->top) = valor;
      p->top++;
      return 1;
   }
   else
      return 0;
}

int main(){
   int entrada[SIZE],saida[SIZE];
   int *in = entrada;
   int *out = saida;
   int n,i;
   struct pilha p;
   p.top = p.v;
   for(i=0;i<SIZE;i++){
      entrada[i] = i+1;
   }

   scanf("%d",&n);
   while(n){
      scanf("%d",&saida[0]);
      if(saida[0]){
     for(i=1;i<n;i++){
        scanf("%d",&saida[i]);
     }
     in = entrada;
     out = saida;
     while(in<entrada+n){
        push(&p,*in);
        in++;
        while(peek(&p) == *out){
           pop(&p);
           out++;
        }
     }
     if(saida+n == out)
        printf("Yes\n");
     else
        printf("No\n");
     p.top = p.v;
      }
      else{
     scanf("%d",&n);
     if(n){
        printf("\n");
        p.top = p.v;
     }
      }
   }
}

0

dcpietropaolo replied 9 years ago

#include <stdio.h>
#include <string.h>
#include <stack>
#include <iostream>
using namespace std;
int main (){
    stack <int> d, e;
    int a, c, v, b, cont=0, g, k, vd, j, h;
    while (1){
        if(cont!=0){
            puts("");
        }
        scanf ("%d", &a);
        if (a==0){
            break;
        }
        cont++;
        for (c=0; c<a; c++){
            d.push(a-c);   

        }
        while(1){
            k=0;
            g=0;
            for (c=0; c<a; c++){
                scanf ("%d", &b);
                vd=0;

                int aux=b;
                if (b==0 && c==0){
                    k=1;
                    break;
                }
                j=d.size();
                if (e.size()!=0){

                    if (e.top()==b){
                        g++;
                        e.pop();
                        vd++;                
                    }
                }
                if (vd==0){
                    for (h=0; h<j; h++){
                        if (b==d.top()){
                            g++;

                            d.pop();
                            break;
                        }
                        if (b!=d.top()){

                            e.push(d.top());

                            d.pop();

                        }
                         if (b==e.top()){
                            g++;

                            e.pop();
                            break;
                        }
                    }

                }
            }
            if (k==1){
                break;
            }
            if (g==a){
                printf ("Yes\n");
            }
            if (g!=a){
                printf ("No\n");
            }
            while (1){
                if (d.size()==0)
                    break;
                d.pop();
           }
           for (c=0; c<a; c++){
                d.push(a-c);   
            }
            while (1){
                if (e.size()==0)
                    break;
                e.pop();
           }

        }

    }
}

WA 100% x.x

0

crussi replied 9 years ago

Sim, o toolkit gerou alguns erros na saída e o problema já foi reportado. Se encontrar mais bugs no portal, é só reportar diretamente neste link: https://www.urionlinejudge.com.br/judge/pt/feedbacks/add

Vlws.

0

v.batista replied 9 years ago

A seguinte entrada gera a resposta abaixo no tollkit, não estaria errado?

Entrada 15 1 2 3 4 5 6 7 8 9 10 11 12 15 14 13 1 2 3 4 5 6 7 8 9 10 14 15 11 13 12 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 0 0

Saída Yes No No

Yes No No Yes No No No No No

0

dcpietropaolo replied 9 years ago

#include <stdio.h>
int top=0, pilha[1001];

int  push (int a){
        pilha[top]=a;
        top++;
}
int pop (){
        int aux=pilha[top];
        pilha[top]=0;
        top--;
        return aux;
}

int main(){
        int a, b, c, d, ent[1001], gar[1001], taux=0;
        int tux, v;
        while (1){
                scanf ("%d", &a);
                if(a==0)
                        break;
                d=1;
                while(d!=0){
                        int ai=a;
                        for (b=0; b<a; b++){
                                scanf ("%d", &ent[b]);
                                gar[b]=ai;
                                if (ent[b]==0){
                                        d=0;
                                        break;
                                }
                                ai--;
                        }
                        if(d==0) break;
                        taux=a;
                        tux=a;
                        for (b=0; b<a; b++){
                                            if (gar[b]!=ent[b]){
                    for (c=0; c<taux; c++){

                        if (gar[c]!=0 && gar[c]!=ent[b]){
                            push (ent[b]); 

                        }
                        if(gar[c]!=0 && gar[c]==ent[b]){
                            taux--;
                            break;
                            }
                    }
                    if (pilha[top]==ent[b]){
                        taux--;
                        pop();
                        break;

                    }
                }
                if (gar[b]==ent[b]){
                    gar[b]=0;
                    taux--;
                }
            }
            if(taux!=0){
                puts("No");
                }
            if(taux==0){
                puts("Yes");
                }

                        }

                        if(tux==0)
                                printf ("Yes\n");
                        if(tux!=0)
                                printf ("No\n");
                }
        }

WA x.x gente me ajuda que to boiando nesse problema

beecrowd

TOPIC

beecrowd asked on Feb 8 2013

RafaelPontes replied 8 years ago

crussi replied 8 years ago

btorres replied 7 years ago

lhnegri replied on Feb 17 2014

draian replied 8 years ago

ggroth replied 9 years ago

crbonilha replied on Jun 14 2013

leonardo.fernandes replied 7 years ago

FelipeZeiser replied 8 years ago

lcastro6 replied 8 years ago

Roberto0 replied 9 years ago

Mateus7 replied 9 years ago

ttogores replied 9 years ago

dmayr0 replied 7 years ago

btorres replied 7 years ago

leonardo.fernandes replied 7 years ago

dcpietropaolo replied 9 years ago

crussi replied 9 years ago

v.batista replied 9 years ago

dcpietropaolo replied 9 years ago