Elaine |
» 2013-10-03 12:30:58 Praktycznie każdy kompilator potrafi zoptymalizować dzielenie przez stałą, w szczególności przez potęgę dwójki, do postaci, w której żadnej instrukcji dzielenia nie ma. |
|
Wiesiek |
» 2013-10-03 13:27:58 najszybsze będzie: bool dostepne[ 1000001 ], bez_kontroli[ 1000001 ];
int main( void )
{
int iloscSkrzatow, czasDoSnu;
dostepne[ 1 ] = true;
scanf( "%i", & iloscSkrzatow );
scanf( "%i", & czasDoSnu );
for( int i = 0; i < czasDoSnu; i++ )
{
int k = 1;
int length;
scanf( "%i", & length );
for( int j = 0; j < length; j++ )
{
int temp;
scanf( "%i", & temp );
for(; k < temp; k++ ) bez_kontroli[ k ] = false;
bez_kontroli[ k++ ] = true;
}
bool wzrasta = false;
for( int j = 1; j < k )
if( dostepne[ i ] && bez_kontroli[ i ] )
{
wzrasta = true;
break;
}
if( wzrasta )
for( int j = 2; j < k; j++ ) if( bez_kontroli[ j ] ) dostepne[ j ] = true;
if( dostepne[ iloscSkrzatow ] ) break;
}
printf( "%i\n", czasDoSnu );
return 0;
}
Złożoność rzędu liczbaSkrzatow*czasDoSnu, a nawet rzędu suma (najwyższy numer skrzata obserwowanego w czasie t) po t od 1 do czasDoSnu. |
|
Chumanista Temat założony przez niniejszego użytkownika |
» 2013-10-06 09:00:30 [ for( int j = 1; j < k )
if( dostepne[ i ] && bez_kontroli[ i ] )
{
wzrasta = true;
break;
} Do czego jest ten for? Te wszystkie j tak mają być? Kompilacja rozwiązania zakończyła się porażką
skr.e:39:2: warning: no newline at end of file
skr.e: In function 'int main()':
skr.e:7: error: 'scanf' was not declared in this scope
skr.e:25: error: expected `;' before ')' token
skr.e:37: error: 'printf' was not declared in this scope
skr.out: No such file or directory Po drobnych poprawkach wywłaszcza w 5j i 5l. |
|
DejaVu |
» 2013-10-08 23:19:51 Zrobiłeś już to zadanie? Ten temat ciągnie się już miesiąc i efektów brak. |
|
Wiesiek |
» 2013-10-09 13:31:55 Mój program był prawie dobry, gdy dane wejściowe podawały których miejsc smok NIE obserwuje (tylko dodać inkrementację j, i zrobić zmienną globalną i na wyjście wysłać i, a nie czasDoSnu). Poprawiony kod, to bool dostepne[ 1000001 ], kontrolowany[ 1000001 ];
int main( void )
{
int iloscSkrzatow, czasDoSnu;
int maxKontrolowany;
int czas;
dostepne[ 1 ] = true;
scanf( "%i", & iloscSkrzatow );
scanf( "%i", & czasDoSnu );
for( czas = 0; czas < czasDoSnu; czas++ )
{
int k = 1;
int length;
scanf( "%i", & length );
for( int j = 0; j < length; j++ )
{
int temp;
scanf( "%i", & temp );
for(; k < temp; k++ ) kontrolowany[ k ] = false;
kontrolowany[ k++ ] = true;
}
maxKontrolowany = --k;
bool wzrasta = false;
for( int j = 1; j < maxKontrolowany; j++ )
if( dostepne[ j ] && !kontrolowany[ j ] )
{
wzrasta = true;
break;
}
if( !wzrasta )
for( int j = maxKontrolowany + 1; j < iloscSkrzatow; j++ )
if( dostepne[ j ] )
{
wzrasta = true;
break;
}
if( wzrasta )
{
for( int j = 2; j < maxKontrolowany; j++ ) if( !kontrolowany[ j ] ) dostepne[ j ] = true;
for( int j = maxKontrolowany + 1; j <= iloscSkrzatow; j++ ) dostepne[ j ] = true;
}
if( dostepne[ iloscSkrzatow ] ) break;
}
printf( "%i\n", czas );
system( "pause" );
return 0;
}
Ciekawe, jak teraz z wydajnością programu :). Można by to rozwiązywać za pomocą dwóch kolejek "dostępne" i "kontrolowany", implementowanych w tablicach, w których nie umieszczałoby się "pustych" informacji (o niedostępnych i o niekontrolowanych), ale praca na dwóch strumieniach wydłuża kod, wtedy np. uzupełnianie informacji o dostępnych wymaga kodu podobnego do sortowania na podstawie dwóch posortowanych strumieni. Szkoda zabawy (przynajmniej dla mnie) - obecny kod jest przyzwoity. |
|
Chumanista Temat założony przez niniejszego użytkownika |
» 2013-10-09 18:31:30 To rozwiązanie jest dużo wolniejsze od mojego.
Dziękuję za wszelkie próby pomocy. |
|
DejaVu |
» 2013-10-09 18:44:00 Twoim problemem jest rozwiązywanie zadania metodą brute-force. Twoje pętle mówią, że złożoność masz O(n*m), a że n i m mogą wynosić tyle samo, to de-facto algorytm ma pesymistyczną złożoność O(max(n,m)^2), czyli złożoność kwadratową. |
|
| 1 2 3 4 « 5 » |