Lista de probleme 2

#149 scara

Claudia vrea să construiască o scară cu N trepte astfel încât prima treaptă să fie la înălţimea 0 şi ultima treaptă să fie la înălţimea H. Fiind pusă pe glume, ea îi cere arhitectului să proiecteze o scară neobişnuită, în care treptele sunt dispuse astfel încât, la un moment dat, să poţi urca, coborî sau rămâne la acelaşi nivel. Pentru a fi uşor de urcat sau coborât, valoarea absolută a diferenţei dintre înălţimile la care se află oricare două trepte consecutive trebuie să fie mai mică sau egală cu o valoare dată, K. Nicio treaptă nu se poate afla la o înălţime negativă sau la o înălţime mai mare decât H.

Scrieţi un program care să determine numărul de scări diferite cu N trepte, ce pot fi construite respectând cerinţele Claudiei. Deoarece numărul de scări poate fi foarte mare, determinaţi restul împărţirii acestui număr la 666013.

Urmasii lui Moisil, Iasi, 2013

Bulbuka este foarte pasionată de gătit deserturi. Ea a decis să facă (n+2)*(n+2) brioşe pe care le-a numerotat (cu ciocolată, bineinţeles) în modul următor: primele n*n brioşe au fost numerotate de la 1 la n*n, iar restul până la (n+2)*(n+2) au primit valoarea 0. De asemenea, după ce au fost gata, Bulbuka nu a putut rezista tentaţiei de a ordona brioşele într-un pătrat cu latura (n+2) după cum urmează: cele cu 0 pe conturul exterior iar cele numerotate de la 1 la n*n, în interior, în ordine crescătoare, pe linii, de sus in jos, ca în figura alăturată. Bulbuka a numit această aranjare configuraţia ordonată a brioşelor.

Acest aranjament frumos a durat foarte puţin deoarece, pe când Bulbuka stătea cu spatele, Randomel a amestecat brioşele între ele, într-o ordine aleatoare. Când s-a întors şi a văzut fapta, ea s-a supărat foarte tare şi l-a pedepsit pe Randomel punându-l să le aranjeze la loc cum erau (ca în imagine) folosind doar un set limitat de operaţii: shiftări circulare pe linii şi pe coloane. O shiftare presupune deplasarea circulară la dreapta, pe linie sau în jos, pe coloană, cu cel puţin una şi cel mult n+1 poziţii.

Randomel vă roagă să scrieţi un program care, pentru o aranjare aleatorie a brioşelor, să afişeze shiftările circulare posibile care transformă configuraţia dată într-o configuraţie ordonată.

Urmasii lui Moisil, Iasi, 2013