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 :
#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; }
|
|
DejaVu |
» 2012-08-24 00:02:53 Przekroczenie czasu wykonywania - za słaby algorytm. |
|
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ć ? |
|
DejaVu |
» 2012-08-24 00:09:13 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). |
|
Mike148 Temat założony przez niniejszego użytkownika |
» 2012-08-28 14:10:08 Niestety nie pomogło. Wynik identyczny jak przedtem. #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; }
|
|
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 |
|
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 ?
|
|
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ą. |
|
« 1 » 2 |