Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Zadanie z OIG - program wywłaszczony

Ostatnio zmodyfikowano 2012-08-31 16:28
Autor Wiadomość
Mike148
Temat założony przez niniejszego użytkownika
Zadanie z OIG - program wywłaszczony
» 2012-08-24 00:01:58
Witam,
Rozwiązuje sobie zadanie z ubiegłej olimpiady informatycznej gimnazjalistów. Napotkałem się na problem w zadaniu pt. "Dwa słowa" (http://main.edu.pl/pl/user.phtml?op=showtask&task=dwa&con=OIG6). Problem polega na tym iż w niektórych testach program zostaje wywłaszczony.
Oto kod źródłowy :
C/C++
#include <cstdio>
#include <algorithm>
#include <string.h>

#define MAX 1000000

int main()
{
    int n = 0;
    scanf( "%d", & n );
   
    char w1[ MAX ];
    char w2[ MAX ];
   
    scanf( "%s", w1 );
    scanf( "%s", w2 );
   
    int t, x, y;
    scanf( "%d", & t );
   
    while( t-- )
    {
        scanf( "%d %d", & x, & y );
       
        std::swap( w1[ x ], w2[ y ] );
       
        if( strcmp( w1, w2 ) == 0 )
        {
            printf( "0\n" );
        }
        else
        {
            if( std::lexicographical_compare( w1, w1 + n, w2, w2 + n ) )
            {
                printf( "2\n" );
            }
            else
            {
                printf( "1\n" );
            }
        }
    }
   
    return 0;
}
P-63486
DejaVu
» 2012-08-24 00:02:53
Przekroczenie czasu wykonywania - za słaby algorytm.
P-63487
Mike148
Temat założony przez niniejszego użytkownika
» 2012-08-24 00:06:46
Ale szybka odpowiedź!
Skoro mój algorytm jest słaby to jak proponujesz to rozwiązać ?
P-63489
DejaVu
» 2012-08-24 00:09:13
C/C++
int iCmpResult = strcmp( w1, w2 );
if( iCmpResult == 0 )
     kod1();
else
if( iCmpResult < 0 )
     kod2();
else
if( iCmpResult > 0 )
     kod3();

Reszta jest zbędna (tj. lexical cośtam).
P-63491
Mike148
Temat założony przez niniejszego użytkownika
» 2012-08-28 14:10:08
Niestety nie pomogło. Wynik identyczny jak przedtem.

C/C++
#include <cstdio>
#include <algorithm>
#include <string.h>

#define MAX 1000000

int main()
{
    int n = 0;
    scanf( "%d", & n );
   
    char w1[ MAX ];
    char w2[ MAX ];
   
    scanf( "%s", w1 );
    scanf( "%s", w2 );
   
    int t, x, y;
    scanf( "%d", & t );
   
    while( t-- )
    {
        scanf( "%d %d", & x, & y );
       
        std::swap( w1[ x ], w2[ y ] );
       
        int iCmpResult = strcmp( w1, w2 );
       
        if( iCmpResult == 0 )
        {
            printf( "0\n" );
        }
        else
        if( iCmpResult < 0 )
        {
            printf( "2\n" );
        }
        else
        if( iCmpResult > 0 )
        {
            printf( "1\n" );
        }
    }
   
    return 0;
}
P-63888
ison
» 2012-08-28 14:35:43
jak chcesz rozwiązywać zadania algorytmiczne to musisz najpierw nauczyć się obliczać złożoność i oceniać czas działania programu w pesymistycznym przypadku

masz 10^5 zapytań, w każdym zapytaniu rozpatrujesz ciąg znaków o długości 10^6 bo używasz strcmp które działa liniowo, wykonujesz więc 10^11 operacji co jest zdecydowanie za dużo, możesz sobie zapuścić u siebie taki test i zobaczyć jak długo będzie liczył Twój program ;) nie doczekasz się

po prostu znajdź rozwiązanie, które nie będzie wykonywało więcej niż ~10^8 operacji
P-63894
Mike148
Temat założony przez niniejszego użytkownika
» 2012-08-28 14:55:23
A czy jest jakaś funkcja która porównuje to szybciej czy problem leży po stronie koncepcji algorytmu ?
P-63895
ison
» 2012-08-28 15:20:08
Nie ma, musisz wpaść na pomysł jak w czasie stałym lub logarytmicznym stwierdzać po zamianie 2 znaków ze sobą, który string jest późniejszy leksykograficznie wiedząc, który był przed zamianą.
P-63897
« 1 » 2
  Strona 1 z 2 Następna strona