Lista de probleme 6

Oraşele Nordemos şi Suderim sunt separate de un munte foarte înalt. Inginerul Negrimon a fost desemnat să construiască un drum prin munte care să unească cele două oraşe. Harta care i s-a pus la dispoziţie descrie muntele ca o matrice cu N linii şi M coloane numerotate de la 1 la N, respectiv de la 1 la M . Un drum reprezintă o succesiune de elemente din matrice cu proprietatea că oricare două elemente consecutive sunt alăturate, pe linie sau pe coloană. Un drum uneşte oraşul Nordemos (linia 1) şi oraşul Suderim (linia N). Valorile din matrice reprezintă densităţile rocilor din munte în acele zone. Pentru fiecare drum posibil se poate calcula valoarea dmax, egală cu densitatea maximă a rocilor pe care le traversează. Negrimon trebuie să construiască un drum pentru care valoarea dmax este cea mai mică.

Ajută-l pe Negrimon să afle cea mai mică dintre densităţile dmax corespunzătoare drumurilor care unesc Nordemos şi Suderim în condiţiile de mai sus.

GM are un şir de N numere naturale a1 , a2 ,…, aN , cu proprietatea ai ≤ ai+1 ≤ 2*ai pentru orice i, 1 ≤i < N. El doreşte să scrie în faţa fiecărei valori din şir un semn + sau - astfel încât valoarea S a expresiei obţinute să aibă proprietatea 0 ≤ S ≤ a1 .

Scrieţi un program care să-l ajute pe GM să determine un mod de a scrie cele N semne.

La ora de geometrie, Aurel a primit de la profesorul X o temă foarte dificilă: fiind date N segmente orizontale (paralele cu axa Ox), cu extremităţile de coordonate numere naturale, să se numere câte dreptunghiuri speciale pot fi formate în plan, luând în considerare aceste segmente.

Un dreptunghi este special dacă respectă simultan următoarele trei condiţii:
1. Cele patru vârfuri ale dreptunghiului au coordonate numere naturale
2. Laturile dreptunghiului sunt paralele cu axa Ox, respectiv Oy
3. Fiecare dintre cele patru vârfuri ale dreptunghiului aparţine cel puţin unui segment

Scrieţi un program care să-l ajute pe Aurel să determine numărul de posibilităţi de a plasa un dreptunghi în plan astfel încât să fie dreptunghi special. Deoarece rezultatul poate fi foarte mare, se va determina numărul modulo 946021 (restul împărţirii numărului calculat la 946021).

Fiind date n numere naturale a1 , a2 ... an , se calculează ai ^ aj , pentru oricare i şi j (1 ≤ i < j ≤ n) şi se obţine un şir de valori naturale. Cu caracterul ^ s-a notat operatorul sau exclusiv pe biți (xor) şi se aplică conform regulii din tabelul de mai jos.

Fiind date cele n valori şi un număr natural nenul m, 1 ≤ m ≤ n*(n-1)/2, să se determine al m-lea număr din şirul obținut mai sus, considerând valorile în ordine crescătoare.

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.

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ă.