| Fişierul intrare/ieşire: | labirint.in, labirint.out | Sursă | Lot Mehedinți 2015 - Baraj 4 Seniori |
| Autor | Adrian Panaete | Adăugată de |  Tatomir Alex •atatomir |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Labirint
Banca Dudaşu are forma unei matrice cu N linii şi 6 coloane. Fiecare element al matricei reprezintă o cameră iar fiecare cameră are 4 uşi care realizează comunicarea cu exteriorul sau cu camerele vecine. O bandă formată din N+6 hoţi vrea să dea o spargere la această bancă, dar pentru asta le trebuie un plan care să ţină cont de sistemele de securitate ale băncii. Fiecare hoţ va trebui sa intre printr-o uşa exterioară, să treacă printr-una sau mai multe camere şi sa părăsească banca printr-o altă uşa exterioara. Un hoţ nu are voie să treacă de două ori prin aceeaşi cameră. Doi hoţi diferiţi nu au voie să treacă prin aceeaşi cameră. Prin fiecare cameră trebuie sa treacă exact un hoţ. Pentru un plan de atac sensul în care un hoţ îşi parcurge traseul nu este relevant. Odată fixate cele N+6 trasee nu este relevant ce traseu va parcurge fiecare dintre cei N+6 hoţi. Se observă că, din modul in care e conceput un plan rezultă că fiecare uşă exterioara trebuie să fie folosită şi toţi cei N+6 hoţi trebuie să participe la spargere.
Cerinta
Cunoscând N să se calculeze în câte moduri poate fi realizat planul. Deoarece numărul calculat poate fi foarte mare se va afişa restul modulo 44449 al acestui număr.
Date de intrare
Pe prima linie a fişierului de intrare labirint.in se va afla un singur număr natural N cu semnificaţia din enunţ.
Date de ieşire
În fişierul de ieşire labirint.ou$t se va afişa un singur număr natural care va reprezenta restul $modulo 44449 a numărului de variante în care poate fi realizat planul spargerii.
Restricţii
- 1 ≤ N ≤ 100000
- Dudaşu=localitate din apropierea municipiului Drobeta Turnu-Severin.
Exemplu
| labirint.in | labirint.out | Exemplu |
|---|---|---|
| 3 | 9 | Una dintre cele 9 soluţii posibile este:
|
