TOPIC

PROBLEM 1062 - URI Fórum 1.0

URI Online Judge asked 6 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Bruno Torres replied 3 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

  • Rafael G. Pontes replied 3 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? '-'

  • Lucas Hermann Negri replied 5 years ago

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

  • Diego Raian replied 3 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 ?

  • Caio Russi replied 3 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)

  • Leonardo Fernandes replied 3 years ago

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

  • Dionisius Mayr replied 2 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

  • Bruno Torres replied 3 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 3 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;
         }
          }
       }
    }
  • Felipe Zeiser replied 3 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?

  • Lucas Castro replied 4 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?

  • Domitila Crispim Pietropaolo replied 4 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

  • Caio Russi replied 4 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 4 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

  • Domitila Crispim Pietropaolo replied 4 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

  • Roberto replied 4 years ago

    Olá, Mateus.

    Teste o seguinte caso de teste:

    5
    2 3 1 5 4 
    0
    0

    Espero ter ajudado.

    Abraço.

  • Mateus replied 4 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!!!

  • Tiago Togores replied 4 years ago

    Minha entrada estava invertida.

  • Tiago Togores replied 4 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]
  • Old man replied 4 years ago

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

1 of 2