TEMA

Comparação de Códigos

Efren Lopes de Souza preguntado 1 year ago

Abaixo estou colocando dois métodos main para resolver o mesmo problema. Ao meu ver, os códigos têm o mesmo custo assintótico e os custos constantes também não parecem mudar muito. Entretanto, o primeiro código termina no tempo 0.064seg e o segundo excede o tempo limite de 2seg.

Alguém consegue me apontar onde ocorre essa diferença tão gritante? OBS: eu precisei omitir o código que faz a ordenação pra caber aqui na descrição, mas estou usando o quick-sort.

#include <stdio.h>
#define MAX(X, Y) (((X) > (Y)) ? (X) : (Y))
#define SIZE 1000
short x[SIZE], y[SIZE];
int t[SIZE];
int b[SIZE];

int main() {
    int n, i, j;
    while(scanf("%d",&n) == 1) {
        for(i=0 ; i<n ; i++)
            scanf("%hd %hd", &x[i], &y[i]);
        quickSort(x, y, 0, n-1);
        t[0] = 1;
        b[0] = 1;

        for(i=1; i<n; i++){
            int maxtop = 1;
            int maxbot = 1;
            for(j=0; j<i; j++) {
                if (x[i] > x[j]) {
                    if (y[i] == y[j]+2)
                        maxtop = MAX(maxtop , b[j]+1);
                    else if (y[i] == y[j]-2)
                        maxbot = MAX(maxbot , t[j]+1);
                }
            }
            t[i] = maxtop;
            b[i] = maxbot;
        }
        int maximo = 1 ;
        for(i=0; i<n; i++) {
            maximo = MAX(maximo , t[i]);
            maximo = MAX(maximo , b[i]);
        }
        printf("%d\n", maximo);
    }
    return 0;
}

/*
int main_2() {
    int n, i, j, count_t, count_b, max_t, max_b;
    while (scanf("%d", &n)) {

        for(i=0; i<n; i++)
            scanf("%hd %hd", &x[i], &y[i]);
        quickSort(x, y, 0, n-1);

        max_t = max_b = 0;
        for(i=1; i<n; i++) {
            count_t = count_b = 1;
            for(j=0; j<i; j++) {
                if (x[j] < x[i]) {
                    if ( y[j] == y[i]+2 )
                        count_t++;
                    else if (y[j] == y[i]-2)
                        count_b++;
                }
            }
            if ( count_t > max_t ) max_t = count_t;
            if ( count_b > max_b ) max_b = count_b;
        }

        if (max_t > max_b)
            printf("%d\n", max_t);
        else
            printf("%d\n", max_b);
    }
    return 0;
}*/

Recuerda no enviar soluciones. Tu mensaje puede ser revisado por nuestros moderadores.

  • Aléxis Toigo respondido 1 year ago

    Este problema é EOF (End Of File), onde ele só ira finalizar quando acabar as entradas do juiz, como o segundo código não trata isso, seu programa nunca finaliza (ele sempre fica esperando pela próxima entrada), danto o tempo limite excedido, para corrigir isto é bem simples.

    Na linha 44, troque:

      while (scanf("%d", &n)) {

    Por:

      while (scanf("%d", &n)!=EOF) {

    No primeiro código ele faz a tratativa, com ==1, verificando se for verdadeiro o valor entrado, caso contrario ele encerra o laço while, assim, também encerrando o programa.