Pe o tablă pătrată de dimensiune n x n se desenează o secvenţă de triunghiuri dreptunghice isoscele. Fiecare triunghi are vârfurile numerotate cu 1, 2 şi 3 (2 corespunde unghiului drept iar ordinea 1, 2, 3 a vârfurilor este în sens invers acelor de ceasornic – vezi figura).



Triunghiurile au catetele paralele cu marginile tablei. Primul triunghi, având lungimea catetei Lg, are vârful 1 pe linia L şi coloana C şi este orientat ca în figură.
Jocul constă în alipirea câte unui nou triunghi la unul din vârfurile 2 sau 3 ale triunghiului curent. Dacă se alătură colţului 2, noul triunghi se aşează cu vârful 1 în prelungirea laturii [1,2] a triunghiului curent, iar dacă se alătură colţului 3 se aşează cu vârful 1 în prelungirea laturii [2,3].
Iniţial noul triunghi este orientat ca şi cel anterior. El se poate plasa pe tablă dacă nu sunt depăşite marginile acesteia sau nu se suprapune peste un alt triunghi. În caz contrar, se face o singură rotaţie cu 90o spre stânga, obţinându-se o nouă orientare a triunghiului. Dacă nici în acest caz noul triunghi nu poate fi plasat, jocul se opreşte.
Zona ocupată de primul triunghi se completeză cu litera ’a’; zona celui de-al doilea se completeză cu litera ‘b’, ş.a.m.d. Când literele mici ale alfabetului englez sunt epuizate, se reîncepe de la ‘a’.

Cerinţă

Cunoscându-se dimensiunea tablei, poziţia primului triunghi (linie, coloană) şi lungimea catetei precum şi o secvenţă de triunghiuri care se doresc a fi alipite se cere să se genereze matricea rezultată în finalul jocului. Jocul se termină dacă un triunghi nu mai poate fi alipit sau au fost plasate toate triunghiurile descrise în secvenţă.

Date de intrare

În fişierul de intrare joc9.in, pe prima linie se află n (dimensiunea tablei). Pe a doua linie separate prin câte un spaţiu se află: L (linia), C (coloana) şi Lg (lungimea catetei) corespunzătoare primului triunghi. Următoarele linii, până la sfârşitul fişierului, conţin câte două numere naturale separate prin câte un singur spaţiu reprezentând colţul triunghiului curent la care va fi alipit triunghiul următor şi dimensiunea catetei triunghiului următor.

Date de ieşire

În fişierul de ieşire joc9.out va fi afişată matricea rezultată. Celulele tablei care nu sunt completate cu litere ale alfabetului vor fi completate cu ‘.’.

Restricţii

1 ≤ n ≤ 100
1 <= C, L <= n ; 2 <= Lg <= n
Fiecare linie din fişierul de intrare şi din fişierul de ieşire se termină cu marcaj de sfârşit de linie.

Exemple

joc9.in	joc9.out	Explicaţii
20 16 8 4 3 5 2 3 3 4 2 3 3 5 3 3 2 2 3 4 2 3 3 3 3 2 3 3 3 3 2 4	.................... .................... ..........fffffeee.. ..........ffff..ee.. ..........fff....e.. ..........ff..dddd.. ..........f....ddd.. ......hhggg...b.dd.. ......h.gg...bb..d.. jjjiiii.g...bbb..c.. jj.iii.....bbbb.cc.. j..ii.....bbbbbccc.. k..i......a......... kk.......aa......... kkkl....aaa......... ...llm.aaaa......... .....mm............. .....mmmn........... ........nn.......... ........nnn.........	Triunghiul ‘a’ este plasat în linia 16 coloana 8 şi are latura 4. Triunghiul ‘b’ se alipeşte în colţul 3 şi are lungimea 5. Triunghiul ‘c’ se alipeşte în colţul 2 şi are lungimea 3. Tringhiurile ‘a’, ‘b’ şi ‘c’ păstrează aceeaşi aranjare. Triunghiul ‘d’ nu se poate alipi în aceeaşi aranjare colţului 3 deoarece are cateta de lungimea 4 şi depăşeşte tabla. Rotim triunghiul cu 90o spre stânga şi obţinem o nouă aranjare. Triunghiul ‘e’ se alipeşte în colţul 2 şi are cateta de lungime 3 în aranjarea curentă. Triunghiul ‘f’ nu se poate alipi în aceeaşi aranjare cu ‘e’ în colţul 3 deoarece are cateta de lungimea 5 şi depăşeşte tabla. Rotim triunghiul cu 90o spre stânga şi obţinem o nouă aranjare. Triunghiul ‘f’ se alipeşte în colţul 3, are lungimea 5 şi o nouă aranjare. Algoritmul continuă până la al 14-lea triunghi, ‘n’. Al 15-lea triunghi nu se mai poate plasa.

autor: Prof. Cristina Luca

propunător: Prof. Marinel Şerban

Liceul de Informatică “Grigore Moisil”

marinel_serban@yahoo.com