Fişierul intrare/ieşire:derdelus.in, derdelus.outSursăAlgoritmiada 2011, Runda 2
AutorStefan Alexandru FilipAdăugată deProstuStefan-Alexandru Filip Prostu
Timp execuţie pe test0.1 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Derdelus

Oile se antrenează pentru a sări peste garduri în visele oamenilor. Ele îşi exerseaza aterizările pentru că unii oameni au nişte garduri complicate prin vise: unele înalte, altele late, şi unii chiar ziduri comparabile cu Marele Zid Chinezesc, ba chiar pot să fie şi împrejmuite de şanţuri umplute cu apă şi în care sălăşluiesc crocodili. Oile trebuie să fie foarte bine antrenate pentru a face faţă viselor acestora.

În lumea oilor ele au un complex întreg pentru perfecţionarea săriturilor, iar pe noi ne interesează o piramidă. Oile se urcă în vârful acesteia şi încep să coboare pe una din faţade. De alungul coborârii ele pot să rămâna numai pe acea faţadă. Piramida are la bază N cuburi, pe nivelul superior N-1 şi aşa mai departe până în vârf unde este un sigur cub de pe care oile îşi încep antrenamentul. De pe acest cub ele pot să sară pe cubul din stânga sau pe cel din dreapta. Piramida aceasta este însă destul de veche şi cu timpul P cuburi s-au deteriorat şi nu mai este sigur să se aterizeze pe ele.
   *
  * *
  * # *
 * * * *

Oaia Dubota se pregăteşte să îşi înceapă antrenamentul. Ea se află în vârful piramidei şi analizează faţada pe care să coboare. Dubota este o oaie destul de şmecheră, şi deşi oile începătoare pot să sară doar pe nivelul inferior al piramidei fără a se răni, Dubota poate să sară la un pas între 1 şi M niveluri. Aşa că dacă se află în locaţia (i, j) atunci ea poate sări la stânga in (k, j) sau la dreapta (k, j + k - i) unde i < k si k - i ≤ M.

Dubota este interesată să ştie în câte feluri poate coborî până pe cuburile de pe primul nivel. Problema ei este ca s-a încurcat încercând să calculeze şi vă cere ajutorul.

Să se afişeze în câte feluri poate coborî Dubota pornind din vârful dealului şi terminând în fiecare din locaţiile de la baza dealului. Deoarece valorile pot fi foarte mari, să se afişeze acestea modulo 666013.

Date de intrare

Fişierul de intrare derdelus.in va conţine pe prima linie valorile N, M şi P. Pe următoarele P linii se vor găsi cuburile care sunt deteriorate sub forma nivel şi indice. Nivelurile sunt numerotate de sus în jos începând cu 1 şi terminând cu N şi pe un nivel cuburile sunt numerotate de la stânga la dreapta.

Date de ieşire

În fişierul de ieşire derdelus.out trebuie să afişaţi N valori modulo 666013 reprezentând numărul de posibilităţi pe care le 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
  • Pozitia de start (1, 1) nu poate fi stricata.

Exemplu

derdelus.inderdelus.out
4 2 2
3 2
2 2
3 2 2 1

Explicaţie

   *
  * #
  * # *
 * * * *

Pentru prima casuta, cele trei posibilitati sunt: (1, 1) -> (3, 1) -> (4, 1); (1, 1) -> (2, 1) -> (4, 1); (1, 1) -> (2, 1) -> (3, 1) -> (4, 1).
Pentru casuta a doua: (1, 1) -> (3, 1) -> (4, 2); (1, 1) -> (2, 1) -> (3, 1) -> (4, 2).
Pentru a treia casuta: (1, 1) -> (2, 1) -> (4, 3); (1, 1) -> (3, 3) -> (4, 3).
Pentru casuta a patra: (1, 1) -> (3, 3) -> (4, 4).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content