Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-08-13 12:04:13.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:drum.in, drum.outSursăLista lui Francu
AutorCatalin FrancuAdăugată degabitzish1Gabriel Bitis gabitzish1
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Drum

Se considera o tabla de 5×5 patratele si 25 de piese patrate, fiecare
piesa putand avea una din formele:

(1)
Imaginile trebuie neaparat sa fie atasamente ale unei pagini.
  (2)
Imaginile trebuie neaparat sa fie atasamente ale unei pagini.
  (3)
Imaginile trebuie neaparat sa fie atasamente ale unei pagini.

Se observa ca piesa (1) are conectate marginile N-S si E-V, piesa 2 are conectate marginile N-E si S-V, iar piesa 3 are conectate marginile N-V si S-E. Subliniem ca cele doua linii din piesa 1 NU se intersecteaza, ci trec "una pe sub cealalta".

Cerinta

Se cere sa se aseze cele 25 de piese pe tabla in asa fel incat sa se obtina un drum care:

  • Sa treaca prin fiecare patrat o singura data;
  • Sa nu se autointersecteze;
  • Sa porneasca din coltul de NV al tablei (linia 1, coloana 1), incepand de la exteriorul tablei (fie dinspre nord, fie dinspre vest);
  • Sa se termine in coltul de SE al tablei (linia 5, coloana 5) si sa paraseasca tabla.

Date de intrare

De pe prima linie a fisierului drum.in se vor citi numerele N<sub>1</sub>, N<sub>2</sub> si N<sub>3</sub>, reprezentand numarul de piese din tipurile 1, 2 si 3. Se garanteaza ca suma lor este 25.

Date de iesire

In fisierul drum.out se va tipari o matrice cu 5×5 numere separate prin spatii, reprezentand tipul piesei plasate in fiecare patratel. Daca exista mai multe solutii, se va tipari una la alegere. Daca nu exista nici o solutie, fisierul va contine mesajul "Imposibil".

Exemplu

drum.indrum.out
6 9 10
1 2 3 1 2
3 3 1 3 3
1 3 3 2 2
1 2 2 3 3
2 1 3 2 2
drum.indrum.out
6 9 10
1 2 3 1 2
3 3 1 3 3
1 3 3 2 2
1 2 2 3 3
2 1 3 2 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?