culori

Culori

== include(page="template/taskheader" task_id="culori") ==

Alice si Bob, doi renumiti montaniarzi care tocmai au iesit din sesiune, s-au hotarat sa isi petreaca vacanta in inima muntilor. Intr-o zi, explorand padurile din preajma, au descoperit o pestera despre care au presupus ca odinioara a apartinut unei colonii de maimute. Conform cunostintelor acumulate in domeniu, pestera este formata din $N$ camere unite prin coridoare bidirectionale astfel incat intre oricare doua camere exista un singur drum. Mai mult, peretii fiecarei camere au fost vopsiti de catre maimute intr-o culoare notata cu un numar intreg intre $1$ si $N$.

Alice si Bob, doi renumiti montaniarzi care tocmai au iesit din sesiune, s-au hotarat sa isi petreaca vacanta in inima muntilor. Intr-o zi, explorand padurile din preajma, au descoperit o pestera despre care au presupus ca odinioara a apartinut unei colonii de maimute. Conform cunostintelor in domeniu, pestera este formata din $N$ camere unite prin coridoare bidirectionale astfel incat intre oricare doua camere exista un singur drum. Mai mult, peretii fiecarei camere au fost vopsiti de catre maimute intr-o culoare notata cu un numar intreg intre $1$ si $N$.

Temerarii nostri doresc sa reconstituie harta pesterii. Pentru aceasta ei procedeaza in felul urmator:

h2. Date de iesire

Pe prima linie a fisierului de iesire veti afisa numarul de posibilitati de intocmire a hartii $modulo 666013$.

Pe prima linie a fisierului de iesire veti afisa numarul de posibilitati de intocmire a hartii $modulo 9901$.

h2. Restrictii

h3. Explicatie

In desen observam cele doua harti posibile pentru primul exemplu. Parcurgand oricare dintre cele doua pesteri dupa algoritmul lui Bob (incepand din camera $#1$ marcata in desen cu rosu) obtinem sirul de culori $3 1 3 1 3$.

In desen observam cele doua harti posibile pentru primul exemplu, traseul parcurs de Bob fiind marcat cu sageti albastre. Parcurgand oricare dintre cele doua pesteri dupa algoritmul lui Bob (incepand din camera $#1$ marcata in desen cu rosu) obtinem sirul de culori $3 1 3 1 3$.

!problema/culori?culori.gif!

!problema/culori?culori_s.GIF!

== include(page="template/taskfooter" task_id="culori") ==

1564