TOPIC

PROBLEM 1062 - URI Fórum 1.0

beecrowd asked 9 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • RafaelPontes replied 6 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? '-'

  • crussi replied 6 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)

  • btorres replied 6 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

  • lhnegri replied 8 years ago

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

  • draian replied 6 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 ?

  • ggroth replied 8 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 ;)

  • cbonilha replied 9 years ago

    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.

  • lcastro6 replied 6 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?

  • leonardo.fernandes replied 6 years ago

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

  • Roberto0 replied 7 years ago

    Olá, Mateus.

    Teste o seguinte caso de teste:

    5
    2 3 1 5 4 
    0
    0

    Espero ter ajudado.

    Abraço.

  • Mateus7 replied 7 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!!!

  • dmayr0 replied 5 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

  • btorres replied 6 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.

  • leonardo.fernandes replied 6 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;
         }
          }
       }
    }
  • FelipeZeiser replied 6 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?

  • dcpietropaolo replied 7 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

  • crussi replied 7 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.

  • v.batista replied 7 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

  • dcpietropaolo replied 7 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

  • ttogores replied 7 years ago

    Minha entrada estava invertida.

1 of 2