Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | derdelus.in, derdelus.out | Sursă | Algoritmiada 2011, Runda 2 |
| Autor | Stefan Alexandru Filip | Adăugată de |  Stefan-Alexandru Filip •Prostu |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Derdelus
Oile se antreneaza pentru a sari peste garduri in visele oamenilor. Ele isi exerseaza aterizarile pentru ca unii oameni au niste garduri complicate prin vise: unele inalte, altele late, si unii chiar ziduri comparabile cu Marele Zid Chinezesc, ba chiar pot sa fie si imprejmuite de santuri umplute cu apa si in care salasluiesc crocodili. Oile trebuie sa fie foarte bine antrenate pentru a face fata viselor acestora.
In lumea oilor ele au un complex intreg pentru perfectionarea sariturilor, iar pe noi ne intereseaza o piramida. Oile se urca in varful acesteia si incep sa coboare pe una din fatade. De alungul coborarii ele pot sa ramana numai pe acea fatada. Piramida are a baza N cuburi, pe nivelul superior N-1 si asa mai departe pana in varf unde este un sigur cub de pe care oile isi incep antrenamentul. De pe acest cub ele pot sa sara pe cubul din stanga sau pe cel din dreapta. Piramida aceasta este insa destul de veche si cu timpul P cuburi s-au deteriorat si nu mai este sigur sa se aterizeze pe ele.
*
* *
* # *
* * * *
Oaia Dubota se pregateste sa isi inceapa antrenamentul. Ea se afla in varful piramidei si analizeaza fatada pe care sa coboare. Dubota este o oaie destul de smechera, si desi oile incepatoare pot sa sara doar pe nivelul inferior al piramidei fara a se rani, Dubota poate sa sara la un pas intre 1 si M niveluri. Asa ca daca se afla in locatia (i, j) atunci ea poate sari la stanga in (k, j) sau la dreapta (k, j + k - i) unde k > i.
Dubota este interesata sa stie in cate feluri poate cobora pana pe cuburile de pe primul nivel. Problema ei este ca s-a incurcat incercand sa calculeze si va cere ajutorul.
Sa se afiseze in cate feluri poate cobora Dubota pornind din varful dealului si terminand in fiecare din locatiile de la baza dealului. Deoarece valorile pot fi foarte mari, sa se afiseze acestea modulo 666013.
Date de intrare
Fişierul de intrare derdelus.in va contine pe prima linie valorile N, M si P. Pe urmatoarele P linii se vor gasi cuburile care sunt deteriorate sub forma nivel si indice. Nivelurile sunt numerotate de sus in jos incepand cu 1 si terminand cu N si pe un nivel cuburile sunt numerotate de la stanga la dreapta.
Date de ieşire
În fişierul de ieşire derdelus.out trebuie sa afisati N valori modulo 666013 reprezentand numarul de posibilitati pe care il are Dubota de a ajunge pe fiecare din cuburile de pe nivelul de la baza piramidei.
Restricţii
- 2 ≤ N ≤ 1000
- 1 ≤ M ≤ N
- 0 ≤ P ≤ N * (N+1) / 2
Exemplu
| derdelus.in | derdelus.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
