Zadanie "Na troje baba..." z treningu zeszłorocznego OIG
Ostatnio zmodyfikowano 2012-03-08 19:17
neverneve Temat założony przez niniejszego użytkownika |
Zadanie "Na troje baba..." z treningu zeszłorocznego OIG » 2012-03-08 19:17:36 Nurtuje mnie jedno zadanie z V OIG. Od razu zaznaczę, że konkurs ten dawno już się skończył, a ja jedno z zadań zacząłem robić po prostu dla treningu (przed 2 etapem VI OIGa, który jest w sobotę :d). Pochodzi ono z 4 rundy treningowej, a jako że nie wszyscy mają dostęp do strony OIGa i Archiwum zadań (gdzie można wysyłać rozwiązania do zadań z poprzednich etapów), przytoczę treść: W Krainie Wielkich Liczb siała Baba mak, a było to tak: każdego dnia trzech dziadów otrzymywało pewną liczbę ziarenek maku na obsianie pola. Jeżeli ziaren nie udało się pomiędzy nich równo podzielić, to Baba zabierała je z powrotem i gromadziła w zapasie. Twoim zadaniem jest obliczyć, ile ziarenek maku wysiało w sumie trzech dziadów.
Wejście
W każdym wierszu standardowego wejścia zapisano wartość do 250 cyfr, oznaczającą liczbę ziarenek maku przeznaczonych do wysiania w danym dniu. W ostatnim wierszu znajduje się znak końca pliku (EOF).
Wyj±cie
W jedynym wierszu standardowego wyjścia zapisz, ile ziarenek maku w sumie wysiało trzech dziadów.
Zadanie łatwe, moim zdaniem wystarczy tu funkcja dodawania bignumów i sprawdzania, czy są podzielne przez 3. To nie sprawiło mi problemu, za to pojawił się on przy wczytywaniu z pliku, gdyż był to pierwszy raz jak się z tyn bawiłem. Ogólnie ograniczyło się to do zrobienia pętli while z warunkiem "cin>>a" (lub getline(cin,a), jest wiele sposobów), a w pętli sprawdzanie, czy podzielna przez 3 jest liczba i ew. dodawanie do sumy ziarenek. Oczywiście doszedłem do tego dopiero po parokrotnym wysłaniu programu do sprawdzenia, a tak uczynić można 10 razy (jest limit 10 zgłoszeń). No i doszedłem w końcu do momentu, gdzie nie miałem pomysłu jak ulepszyć program, a ciągle nie przechodził on 3 testów (z 15). Po kombinowaniu "a może to dodać, a może to" wykorzystałem wszystkie 10 zgłoszeń, a program ciągle nie przechodzi 3 testów (i to testów ze środka, czyli prawdopodobnie nie zawierających jakiś horrendalnych, 250-cyfrowych liczb). Z racji wykorzystania wszystkich zgłoszeń programu już nie wyślę, ale niezmiernie mnie zżera ciekawość "co tu jest nie tak". Zaciągnąłem nawet kolegę do kminienia, ale nic nie wymyśliliśmy, więc zwracam się teraz z prośbą do Was, abyści orzekli, co w tym kodzie jest nie tak. Z wysłaniem zgłoszenia będzie już ciężko, bo ja wykorzystałem wszystkie możliwości, ale zawsze mogę jakiegoś kolegę poprosić o wysłanie. Oto kod: #include <iostream> #include <string> using namespace std;
string dodaj( string a, string b ) { if( a.size() < b.size() ) swap( a, b ); a = "0" + a; for( int ia = a.size() - 1, ib = b.size() - 1; ib >= 0; ia--, ib-- ) { a[ ia ] += b[ ib ] - '0'; if( a[ ia ] > '9' ) { a[ ia ] -= 10; a[ ia - 1 ] ++; } } while( a[ 0 ] == '0' ) a.erase( 0, 1 ); return a; }
bool czyPrzez3( string a ) { int suma = 0; for( int i = 0; i < a.size(); i++ ) { suma += a[ i ] - '0'; } if( suma % 3 == 0 ) return 1; return 0; }
int main() { string a; string suma = "0"; while( cin >> a ) { if( czyPrzez3( a ) ) suma = dodaj( suma, a ); } cout << suma; return 0; }
|
|
« 1 » |