Bridge

bridge

==Include(page="template/taskheader" task_id="bridge")==

== include(page="template/taskheader" task_id="bridge") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| bridge.in | bridge.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="bridge") ==

==Include(page="template/raw")==
 
Link: [1]File-List
 
Bridge
 
 
 
Fat-Frumos a plecat in cautarea iubirii sale, fiica imparatului, Simona, care a fost rapita de balaurul cel rau si dusa in pestera acestuia. Acesta s-a pregatit intens de lupta insa el nu a stiut ca balaurul ii pregatise o surpriza, si astfel l-a atras pe acesta pe un pod. Pe pod Fat-Frumos se poate deplasa pasind (se va deplasa o scandura la dreapta), sarind (se va deplasa 2 scanduri la dreapta), stationand (va ramane pe aceeasi scandura) sau teleportandu-se (vezi scandura teleportoare). Insa podul este putin mai ciudat fiind format din 4 tipuri de scanduri astfel:
 
0 - scandura buna (pe o astfel de scandura se poate stationa, pasi, sari sau teleporta, si se poate ajunge oricum pe ea)
 
1 - scandura subreda (la fel ca la o scandura buna, numai ca pe acest tip de scandura nu se poate ajunge decat prin pasire)
 
2 - scandura lipsa (Daca Fat-Frumos va ajunge pe o astfel de scandura el va ajunge felul principal al crocodililor de sub pod)
 
3 - scandura teleportoare (pe astfel de scandura se poate ajunge oricum, iar o astfel de scandura il va teleporta pe eroul nostru pe o alta scandura numita scandura destinatie)
 
h2. Cerinta
 
Fat-Frumos va trebui sa isi coordoneze miscarile cat mai bine pe pod de aceea va roaga pe voi sa ii raspunde-ti la M intrebari de forma "In cate moduri pot ajunge pe scandura X in K pasi?"
 
h2. Date de Intrare
 
Pe prima linie a fisierului bridge.in vor fi scrise 2 numere N si M reprezentand numarul de scanduri respective numarul de intrebari. Pe urmatoarea linie vor fi scrise N numere cuprinse intre 0 si 3 reprezentand configuratia podului, corespondenta fiind cea de mai sus. Pe urmatoarele linii vor fi scrise scandurile destinatie pentru fiecare scandura teleportoare in ordinea aparitiei acestora pe pod, si, in final, pe urmatoarele M linii vor fi scrise cate 2 numere X si K care definesc o intrebare de genul "In cate moduri se poate ajunge pe scandura X in K pasi?".
 
h2. Date de Iesire
 
Fisierul de iesire bridge.out va contine M linii reprezentand raspunsul pentru fiecare intrebare din fisierul de intrare in ordine.
 
h2. Restrictii si Precizari
 
- 1 < N < 4001
 
- 1 < M < 30001
 
- Numarul maxim de pasi dintr-o intrebare nu va depasi valoarea 4000
 
- Daca scandura x este teleportoare si are ca destinatie scandura y atunci vom avea urmatoarea relatie x < y
 
- Mai multe scanduri teleportoare pot avea ca destinatie aceeasi scandura
 
- In momentul in care Fat-Frumos ajunge pe o scandura teleportoare el va fi teleportat pe scandura destinatie indiferent daca el vrea sau nu (nu poate stationa, sari sau pasi de pe ea)
 
- Teleportarea se considera pas
 
- Raspunsurile se vor afisa modulo 666013
 
- Numarul de moduri de a ajunge pe o scandura lipsa sau pe o scandura teleportoare care are ca destinatie o scandura lipsa sau subreda este 0
 
- Fat-Frumos nu se poate deplasa inapoi (el la un pas se va deplasa 0,1 sau 2 scanduri la dreapta sau va fi teleportat in cazul in care scandura respective are aceasta propietate)
 
- Initial Fat-Frumos se afla in afara podului pozitie pe care nu poate stationa, la primul pas el ori va pasi pe prima scandura ori va sari pe cea de-a doua daca acest lucru este posibil
 
- Prima scandura nu este niciodata lipsa
 
- Pe o scandura teleportoare se poate ajunge ca si pe o scandura buna
 
- Daca o scandura teleportoare nu are ca scandura destinatie o scandura lipsa sau subreda atunci numarul de moduri de a ajunge pe aceasta in K pasi nu este neaparat 0 (vezi exemplu)
 
h2. Exemplu
 
 
 
 
|bridge.in |bridge.out |
 
|5 3 |0 |
| | |
|0 0 3 1 2 |3 |
| | |
|4 |0 |
| | |
|4 4 | |
| | |
|2 3 | |
| | |
|3 2 | |
 
 
 
 
References
 
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/bridge/enunt_files/filelist.xml
==Include(page="template/taskfooter" task_id="bridge")==