Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
MWP6_1H - Gra |
Stasiowi i Grzesiowi znudziła się już gra w "kamień, papier i nożyce", w związku z czym postanowili zagrać w pewną bardzo ambitną grę planszową. Zasady gry są następujące. Staś i Grześ rzucają naprzemiennie kostką zawierającą 100 ścian ponumerowanych od 1 do 100. Po swoim rzucie każdy z nich przesuwa pionka po planszy o tyle pól do przodu ile wypadło na kostce. Wygrywa ten z nich, który jako pierwszy dotrze do mety znajdującej się na k-tym polu. Chłopcy startują z pola o numerze 0.
Właśnie Grześ miał stanąć na polu oznaczonym jako meta i świętować zwycięstwo kiedy Staś krzyknął w jego stronę:
- Oszukujesz! Zapisałem wszystkie wartości jakie wypadały na kostce przy Twoich rzutach i widać po nich, że Twój pionek nie może znajdować się na k-tym polu!
- Ależ oczywiście, że może. Wyniki moich rzutów jasno wskazują że mogłem dotrzeć na pole o numerze k na dokładnie m sposobów!
Twoim zadaniem jest napisanie programu, który obliczy resztę z dzielenia liczby m przez 1012. Niestety Staś nie zapisał ile razy wypadła na kostce dana liczba w związku z czym należy założyć, że każdy z zapisanych wyników mógł zostać wylosowany nieskończenie wiele razy.
Wejście
W pierwszej linii wejścia znajdują się dwie liczby całkowite w oraz k (1 ≤ w ≤ 100, 1 ≤ k ≤ 1000). Liczba w opisuje ile unikatowych wyników wyrzucił Grześ na kostce w trakcie gry, liczba k natomiast oznacza pole na którym znajduje się jego pionek (możliwość dotarcia do tego pola wzbudza wątpliwości Stasia). W drugiej linii wejścia znajduje się w liczb - jest to zbiór wyników rzutów Grzesia.
Wyjście
Na wyjściu należy wypisać liczbę określającą na ile sposobów Grześ mógł dotrzeć na k-te pole modulo 1012.
Przykład
Wejście
4 10 2 3 5 8
Wyjście
16
Wyjaśnienie do przykładu
Sekwencje rzutów, które umożliwią przejście na pole o numerze 10 to:
- 2 2 2 2 2
- 2 2 3 3
- 2 3 2 3
- 2 3 3 2
- 3 2 2 3
- 3 2 3 2
- 3 3 2 2
- 2 3 5
- 2 5 3
- 3 2 5
- 3 5 2
- 5 2 3
- 5 3 2
- 5 5
- 2 8
- 8 2
Dodane przez: | Maciej Boniecki |
Data dodania: | 2014-03-01 |
Limit czasu wykonania programu: | 0.5s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM64 SCM qobi |