TOPIC

PROBLEM 1259 - URI Fórum 1.0

URI Online Judge asked 8 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Talles Brito replied 7 years ago

    Olá,

    Tenho tido problemas de 'time limit exceeded' para problemas resolvidos na linguagem Java, por exemplo:

    O problema 1259 http://www.urionlinejudge.com.br/judge/ ... /view/1259 consiste em ordenar um conjunto de valores de entrada.

    O que acontece é que o simples fato de ler e imprimir os valores sem ordená-los já gera um tempo maior do que 1.000.

    Se somente ler e imprimir os dados de entrada já passa do limite, obviamente é impossível processar a solução.

    Fiz o teste com o seguinte código:

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Scanner;
    
    class Main {
    
        public static void main(String[] args) throws IOException {
    
            InputStreamReader ir = new InputStreamReader(System.in);
            BufferedReader in = new BufferedReader(ir);
    
            int quantidade = Integer.parseInt(in.readLine());
            int vetor[] = new int[quantidade];
    
            for(int i=0;i<quantidade;i++)
                vetor[i] = Integer.parseInt(in.readLine());
    
            for(int i=0;i<quantidade;i++)
                System.out.printf("%d\n", vetor[i]);
    
        }
    
    }

    O que devo fazer? Isso nao é um 'bug' da plataforma?

  • Bruno Torres replied 5 years ago

    Dica: Use a STL se estiver usando C++, o std::sort pode receber uma funcao como criterio de ordenacao, e essa funcao so precisar de 3 linhas :D Pesquise sobre sorting custom objects.

  • Ivan Guimaraes Monte replied 5 years ago

    Runtime Error, alguém pode me ajudar?

    #include <stdio.h>
    #include <stdlib.h>
    
    void separaParImpar(int *array, int n);
    
    int compare(const void *a, const void *b) {
        return ( *(int*)a - *(int*)b );
    }
    
    int main() {
    
        int n, aux;
        int i;
    
        scanf("%d", &n);
    
        int array[n];
    
        for(i = 0; i < n; i++) {
            scanf("%d", &array[i]);
        }
    
        qsort(array, n, sizeof(int), compare);
    
        aux = n;
    
        separaParImpar(array, n);
    
        for(i = 0; i < aux; i++) {
            printf("%d\n", array[i]);
        }
    
        return 0;
    }
    
    void separaParImpar(int *array, int n) {
    
        int contPar = 0;
        int contImpar = 0;
        int i;
        int j;
    
        for(i = 0; i < n; i++) {
    
            if(array[i] % 2 == 0) {
                contPar++;
            } else {
                contImpar++;
            }
    
        }
    
        int par[contPar];
        int impar[contImpar];
    
        contPar = 0;
        contImpar = 0;
    
        for(i = 0; i < n; i++) {
    
            if(array[i] % 2 == 0) {
    
                par[contPar] = array[i];
                contPar++;
    
            } else {
    
                impar[contImpar] = array[i];
                contImpar++;
    
            }
    
        }
    
        for(i = 0; i < contPar; i++) {
            array[i] = par[i];
        }
    
        j = i;
    
        for(i = 1; i < n; i++, j++) {
            array[j] = impar[contImpar - i];
        }
    
    }
  • Bruno Elibio replied 5 years ago

    Por que está dando WA 100%? , esta errado fazer com Bubble sort?

    #include <stdio.h>
    #include <stdlib.h>
    
    int main (){
    
    int N, i, aux, a=0, b=0;
    int c , d, troca;
    
    scanf("%d", &N);
    int v1[N];
    int v2[N];
    
    if((N>=1)&&(N<100000)){
        for(i=0;i<N;i++){
            scanf("%d", &aux);
            if(aux>0){
                if(aux%2==0){
                        v1[a]=aux;
                        a++;
                }
                else{
                    v2[b]=aux;
                    b++;
                }
            }
        }
    }
            for(c=0;c<(a+1);c++){
                for(d=0;d<a-c-1;d++){
                    if(v1[d]>v1[d+1]){
                    troca = v1[d];
                    v1[d]=v1[d+1];
                    v1[d+1]=troca;
                       }
                }
            }
    
            for(c=0;c<(b+1);c++){
                for(d=0;d<b-c-1;d++){
                    if(v2[d]<v2[d+1]){
                       troca = v2[d];
                       v2[d]=v2[d+1];
                        v2[d+1]=troca;
                       }
                }
            }
    
            for(c=0;c<a;c++){
                printf("%d\n", v1[c]);
            }
             for(c=0;c<b;c++){
                printf("%d\n", v2[c]);
            }
    return 0;
    }
  • Unknown replied 5 years ago

    Alguem podia ver o por que está dando wrong answer 100%?

    #define MAX 100000
    #include <stdio.h>
    #include <stdlib.h>
    
    void merge_sort(int v[], int inicio, int fim);
    void merge(int v[], int inicio, int meio, int fim);
    
    int main()
    {
        int n, i, k[MAX];
    
        scanf("%i", &n);
    
        for (i = 0; i < n; i++)
        {
            scanf("%i", &k[i]);
        }
    
        merge_sort(k, 0, n);
    
        for (i = 1; i < n; i++)
        {
            if (k[i] % 2 == 0)
            {
                printf("%i\n", k[i]);
            }
        }
    
        for (i = n; i >-1; i--)
        {
            if (k[i] % 2 != 0)
            {
                printf("%i\n", k[i]);
            }
    
        }
        return 0;
    }
    
    void merge_sort(int v[], int inicio, int fim)
    {
        int meio = (inicio + fim) / 2;
        if (inicio<fim)
        {
            merge_sort(v, inicio, meio);
            merge_sort(v, meio + 1, fim);
            merge(v, inicio, meio, fim);
        }
    }
    
    void merge(int v[], int inicio, int meio, int fim)
    {
        int aux[100000];
        int i = inicio, j = meio + 1, k = 0;
        while (i <= meio && j <= fim)
        {
            if (v[i] <= v[j]) {
                aux[k] = v[i];
                i++;
            }
            else {
                aux[k] = v[j];
                j++;
            }
            k++;
        }
        for (i = i; i <= meio; i++) {
            aux[k] = v[i];
            k++;
        }
        for (j = j; j <= fim; j++) {
            aux[k] = v[j];
            k++;
        }
        k = 0;
        for (i = inicio; i <= fim; i++) {
            v[i] = aux[k];
            k++;
        }
    }
  • Ulysses Caetano Braga replied 5 years ago

    Dica: No ato da leitura já defina se o int é par ou impar, salve-os em vectors distintos (um pros pares e outro pros ímpares), feito isso use sort e reverse pra arrumar a saída e imprima percorrendo o vector da forma que preferir. Eu usei dois while(!vector.empty()) e ia retirando cada item impresso do vector. Passei com o tempo de 0.036.

  • Marcus Antunius replied 6 years ago

    Tô recebendo TLE mesmo com esse meu algoritmo super enxuto kk ,se alguém souber como melhorar, ajude-me.

    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        vector<int>vetor;
        int n;
        cin>>n;
        for (int i = 0; i < n; i++)
        {
            int valor;
            cin>>valor;
            vetor.push_back(valor);
            sort(vetor.begin(),vetor.end());
        }
        for (int i = 0; i < n; ++i)
        {
            if(vetor[i]%2==0){
             cout<<vetor[i]<<endl;
            }
        }
        for (int i = n-1; i >=0; i--)
        {
            if(vetor[i]%2==1){
             cout<<vetor[i]<<endl;
            }
        }
        return 0;
    }
  • Gustavo Borges replied 6 years ago

    Alguem pode me ajudar??? As saidas estão iguais mas recebo Worg Answer...

    Alias deixe eu dizer que esse negocio de Time Limit Exceed , Runtime Error , e Wrong answer quando a saida ta certa , acho uma baita frescura , na minha opinião se o codigo faz o que o exericio pede e a saida esta certa o codigo ja devia dar Accepted.

    Eis meu código (correto e não aceito)

    #include <stdio.h>
    #include <math.h>
    int N,i,j,num,p=0,im=0,aux,vetpar[100],vetimpar[100];
    void preencher ()
    {
        for (i=0;i<p-1;i++)
     {
         for (j=i+1;j<p;j++)
         {
             if (vetpar[i]>vetpar[j])
             {
                 aux = vetpar[i];
                 vetpar[i]=vetpar[j];
                 vetpar[j]=aux;
    
             }
         }
    
     }
     for (i=0;i<im-1;i++)
     {
         for (j=i+1;j<im;j++)
         {
             if (vetimpar[i]<vetimpar[j])
             {
                 aux = vetimpar[i];
                 vetimpar[i]=vetimpar[j];
                 vetimpar[j]=aux;
             }
    
         }
     }
    }
    int main ()
    {
     scanf("%d",&N);
     if (N>1 && N<pow(10,5))
     {
     for (i=0;i<N;i++)
     {
    
         scanf("%d",&num);
         if (num>=0)
         {
         if (num%2==0)
         {
             vetpar[p]=num;
             p++;
         }
         else
         {
             vetimpar[im]=num;
             im++;
         }
         }
    
     }
    
     preencher();
     for (i=0;i<p;i++)
     {
         printf("%d\n",vetpar[i]);
    
     }
     for (i=0;i<im;i++)
     {
         printf("%d\n",vetimpar[i]);
     }
     }
     return 0;
    }
  • Miguel Mendes replied 6 years ago

    Seu ultimo 'for' vai ate i == 1. Ele deveria ir ate 0;

    Por exemplo, suponha que seu vetor após ordenacao seja: 1 2 4 5 6 9 Vai ser exibido: 2 4 6 9 5

    O elemento 1 tá no indice 0 do array. Como i vai até 1, ele nao é exibido.

  • Pedro Henrique Medeiros Silveira replied 6 years ago

    Alguem poderia ver o que está errado nesse código? as saidas estão certa mas está aparecendo Wrong Answer

    #include <iostream>
    #include <algorithm>
    #include <utility>
    #include <vector>
    
    #include <stdio.h>
    
    int main(){
        int n;
        scanf("%d",&n);
        std::vector<int> v;
        int aux;
        for(int i=0;i<n;i++){
            scanf("%d",&aux);
            v.push_back(aux);
        }
        sort(v.begin(),v.end());
    
        for(int i=0;i<v.size();i++)
            if(v[i]%2==0)
                printf("%d\n",v[i]);
    
        for(int i=v.size()-1;i>0;i--)
            if(v[i]%2==1)
                printf("%d\n",v[i]);
    }
  • Lucas Teixeira Gonçalves replied 6 years ago

    Olá, estou recebendo TLE com o quicksort e também com o mergesort, tem alguma otimização que eu possa fazer no meu código?

    #include <stdio.h>
    #include <stdlib.h>
    
    void quick_sort (int *a, int n) {
        if (n < 2)
            return;
        int p = a[n / 2];
        int *l = a;
        int *r = a + n - 1;
        while (l <= r) {
            if (*l < p) {
                l++;
            }
            else if (*r > p) {
                r--;
            }
            else {
                int t = *l;
                *l = *r;
                *r = t;
                l++;
                r--;
            }
        }
        quick_sort(a, r - a + 1);
        quick_sort(l, a + n - l);
    }
    
    int main(){
        int in, j, n, pares[100050], impares[100050], i=0, p=0;
        scanf("%d ", &in);
        while(in--){
            scanf("%d ", &n);
            if(n%2==0){
                pares[p]=n;
                p++;
            }
            else{
                impares[i]=n;
                i++;
            }
            quick_sort(pares, p);
            quick_sort(impares, i);
        }
        for(j=0;j<p;j++)
            printf("%d\n", pares[j]);
        for(j=i-1;j>=0;j--)
            printf("%d\n", impares[j]);
        return 0;
    }
  • Cristhian Bonilha replied 6 years ago

    Ola, o problema esta na implementacao do quick sort.

    Eh preciso estabelecer um padrao dos limites (esq e dir). Por exemplo, o indice esq vai estar incluso e o indice dir vai estar excluso.

    Assim, quando voce for chamar recursivamente, deve prestar atencao nisso. Se fossemos seguir o padrao que eu citei, voce precisaria modificar algumas linhas do seu codigo:

    for(int i=esq+1;i<dir;i++)//
    e essa
    quick(vetor,esq,pos);
  • Jonatas Roberto replied 7 years ago

    #include<iostream>
    #include<algorithm>
    
    using namespace std;
    
    int dividir(int vetor[],int esq,int dir)
    {
        int aux;
        int cont=esq;
        for(int i=esq+1;i<dir+1;i++)//
        {
            if(vetor[i]<vetor[esq])
            {
            cont++;
                aux=vetor[i];
                vetor[i]=vetor[cont];
                vetor[cont]=aux;
    
            }
        }
        aux=vetor[esq];
        vetor[esq]=vetor[cont];
        vetor[cont]=aux;
    
        return cont;
    }
    
    void quick(int vetor[],int esq,int dir)
        {
            int pos;
            if(esq<dir)
            {
              pos=dividir(vetor,esq,dir);
              quick(vetor,esq,pos-1);//recursao excluindo o pivot
              quick(vetor,pos+1,dir);
            }
        }
    
    int main()
    {
    
            int n;
            cin>>n;
          int  vetor[n];
    
        for(int i=0;i<n;i++)
        {
    
            cin>>vetor[i];
    
        }
    
        quick(vetor,0,n);//ordenação com quick sort
    
            for(int i=0;i<n;i++)
            {
                if(vetor[i]%2==0)
                {cout<<vetor[i]<<endl;//exibe pares
                }
            }
    
        for(int i=n-1;i>=0;i--)//exibe impares
        {
                if(vetor[i]%2!=0)
                {cout<<vetor[i]<<endl;
                }
    
        }
    
        return 0;
    
    }

    Alguem poderia dar uma dica só estou recebendo WA Estou usando o metodo quick sort, mas mesmo assim está dando WA

  • Cristhian Bonilha replied 7 years ago

    Olha, bubbleSort é bem pouco recomendado, graças ao seu desempenho baixo. Procure estudar o QuickSort ou o MergeSort. Há também como usar o método de ordenação da biblioteca algorithm.

  • Unknown replied 7 years ago

    Muito obrigado, fiz todos esses teste e estou recebendo Time limit, a forma de ordenar os números pode ser com bubble sort ou deverá ser algum outro ?

  • Cristhian Bonilha replied 7 years ago

    Aqui está um:

    50
    89383
    30886
    92777
    36915
    47793
    38335
    85386
    60492
    16649
    41421
    2362
    90027
    68690
    20059
    97763
    13926
    80540
    83426
    89172
    55736
    5211
    95368
    2567
    56429
    65782
    21530
    22862
    65123
    74067
    3135
    13929
    79802
    34022
    23058
    33069
    98167
    61393
    18456
    75011
    78042
    76229
    77373
    84421
    44919
    13784
    98537
    75198
    94324
    98315
    64370

    Se precisar de mais, compile isso: https://github.com/crbonilha/codes/blob ... mpares.cpp

  • Unknown replied 7 years ago

    Alguém teria alguns casos de teste ?