Fişierul intrare/ieşire:labirint.in, labirint.outSursăLot Mehedinți 2015 - Baraj 4 Seniori
AutorAdrian PanaeteAdăugată deatatomirTatomir Alex atatomir
Timp execuţie pe test0.4 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.inlabirint.outExemplu
3
9
Una dintre cele 9 soluţii posibile este:
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?