AL_29_04 - Czarno białe

[patryk007]

1. Czy ktoś mógłby podać kilka losowych testów dla tego zadania?
   Dla małych przykładów, dla których można policzyć wszystkie możliwości na kartce, moje rozwiązanie wydaje się działać OK, ale widocznie tak nie jest, bo sprawdzarka SPOJ zwraca mi Błędna odpowiedź.
2. Czy w tym zadaniu trzeba implementować własną arytmetykę?
   Dla wejścia 1 500 500 1 łatwo sprawdzić, że odpowiedź jest równa 2^500, co w zapisie dziesiętnym ma 151 cyfr.

EDIT: Przepisałem kod do Pythona (gdzie arytmetyka dużych liczb jest out of the box) i zadanie co prawda zaakceptowane, ale sądząc po osiągniętym czasie (1.78s), jest na to szybszy sposób...

[redysz]

Próbowałeś użyć szybkiego i/o w Pythonie? Mi to często skraca czas z sekundy na jej ułamek:
fast in
fast out

Jeżeli zaś chodzi o zrobienie tego w C++... to z tego co widzę, wystarczy użyć mnożenia wielkich liczb (Jeżeli zrobiłeś zadanie http://pl.spoj.com/problems/TMUL/ to powinno łatwo wyjść) oraz dodawanie samych wyników w tablicy.

Skoro już udało Ci się zrobić to zadanie to mógłbyś rzucić jakieś testy? Dla Twojego 1 500 500 1 mam 2^500, ale gdzieś coś źle robię. Możesz na przykład sprawdzić mi ten wynik?
In:
1
700 800 4

Out:
18680330847703464518688309150428604455933377501043539228532749986198161368658034797840898631798395354798998161920

PS. Wiele wyników pośrednich się powtarza. Może można by było je jakoś stablicować?

[swiergu]

Szybkie i/o tu nie przyspieszy, gdyż na wejściu jest 30 liczb, a najdłuższe możliwe wyjście to tylko nieco ponad 3000 znaków. Zadanie można rozwiązać bez mnożenia dużych liczb.

Podany wynik dla przykładu: 700 800 4 jest poprawny.

[redysz]

Zadanie można rozwiązać bez mnożenia dużych liczb.

Czy to oznacza, że zadanie można rozwiązać bez obliczania wartości symbolu Newtona? Czy tylko to, że licznik z mianownikiem skrócą się zawsze tak, że wynik mieścić się będzie w typie long long?

[swiergu]

W typie long long się nie zmieści, ale można policzyć wynik używając tylko dodawania dużych liczb i programowania dynamicznego.