Lista de probleme 9

Primăria orașului Constanța reamenajează plaja din stațiunea Mamaia. Aceasta este reprezentată ca o zonă dreptunghiulară cu lățimea de a unități și lungimea de b unități. Pe plajă sunt trasate linii paralele cu laturile dreptunghiului astfel încât să formeze pătrate cu latura de o unitate, numite zone. Pe plajă se vor pune obiecte: umbrele și prosoape. Se consideră că dacă un obiect intră în interiorul unei zone, o ocupă în întregime. Se poziționează u umbrele de soare. Într-o zonă se poate așeza cel mult o umbrelă.

N turişti vin şi îşi aşează prosoapele pe plajă. Un prosop are formă dreptunghiulară şi va fi aşezat paralel cu laturile dreptunghiului. Turiştii îşi pot aşeza prosoapele pe zone libere sau peste prosoape deja aşezate. Un turist nu îşi poate aşeza însă prosopul pe plajă dacă suprafaţa acoperită de acesta include cel puţin o zonă în care se află o umbrelă.
M localnici au suprafeţe favorite pentru aşezarea prosoapelor. O suprafaţă favorită are forma unui dreptunghi cu laturile paralele cu laturile dreptunghiului care marchează plaja. După ce turiştii termină aşezarea prosoapelor, localnicii verifică dacă zonele din suprafaţa favorită sunt libere (neacoperite de prosoape aşezate de turişti sau de umbrele).

Scrieţi un program care să determine numărul de turişti care au reuşit să îşi aşeze prosoapele pe plajă, precum și numărul de localnici ale căror zone favorite sunt libere.

Acceleratorul de particule CERN este dispus sub forma a 3 cercuri cu aceeaşi rază, tangente exterioare două câte două, numerotate pe figură cu 1, 2, 3. Traiectoria unei particule elementare porneşte din unul din punctele marcate pe figură cu A, B, C, D, E, F şi se deplasează cu viteză constantă de \( {1}^{0} \) /unitatea de timp numai pe circumferinţa cercurilor. La trecerea printr-un punct de tangenţă dintre două cercuri particula îşi schimbă atât sensul de deplasare, cât şi cercul pe care se deplasează. Astfel, dacă sensul de deplasare a fost la un moment dat trigonometric, la trecerea printr-un punct de tangenţă devine invers trigonometric şi dacă sensul de deplasare a fost invers trigonometric, la trecerea printr-un punct de tangenţă devine trigonometric.

Să se scrie un program, care, cunoscând punctul iniţial şi sensul de deplasare al unei particule, să determine poziţia particulei în accelerator după un număr dat de unităţi de timp.

Fie n un număr natural nenul şi un şir de n numere naturale nenule, fiecare număr din şir având cel mult 3 cifre. Şirul dat se „maximizează” prin aplicarea următoarelor transformări:

Se consideră o matrice cu elemente 0 sau 1, cu L linii (numerotate de la 1 la L) şi C coloane (numerotate de la 1 la C).
Definim o zonă dreptunghiulară ca fiind o submatrice ce are pe contur numai valori 1 şi cu proprietatea că nu există valori de 1 nesituate pe contur şi în acelaşi timp la distanţa 1 faţă de un punct de pe contur. Două puncte sunt la distanţa 1 dacă şi numai dacă sunt vecine pe una dintre cele 8 direcţii.
Să se determine numărul total de zone dreptunghiulare din matrice, ordinul maxim al unei zone şi numărul de zone care au acest ordin maxim.

După multe năzbâtii făcute împreună, Alex şi Cipri nu mai au voie să se întâlnească. Alex – strategul echipei – a plănuit o nouă poznă şi a decis să-i transmită prietenului său planul de luptă, constând din anumite cuvinte dintr-un mesaj m[0]. Pentru a nu fi descoperiți, i-a trimis ulterior mai multe mesaje m[1], m[2], … lui Cipri, acesta trebuind să le descifreze folosind convenția secretă stabilită la începutul prieteniei lor și să “acționeze”. Fiecare mesaj m[i] este format din mai multe cuvinte, separate prin câte un spațiu, numerotate cu valori consecutive, începând de la 1.
Pentru a afla planul, Cipri trebuie să găsească cea mai mare valoare i ≥ 0 astfel încât mesajele m[i] și m[0] să conțină cel puțin un cuvânt identic având același număr de ordine în ambele mesaje. Din m[0] se păstrează toate cuvintele care se găsesc și în mesajul m[i] cu același număr de ordine ca în m[0].
Cuvintele păstrate trebuie ordonate în ordine descrescătoare lexicografică a puterii lor. Puterea cuvântului cu numărul de ordine j în m[0] este egală cu șirul ordonat descrescător al indicilor mesajelor în care apare cu același număr de ordine ca în m[0]. Astfel, un cuvânt care a apărut cu numărul de ordine 2 în mesajele m[0], m[6] și m[8] are puterea {8,6,0}. Dacă două cuvinte au aceeași putere, vor rămâne în ordinea din mesajul inițial. Lui Cipri nu i-a mai rămas decât să citească fiecare cuvânt de la dreapta la stânga şi a descifrat tot planul de luptă Cunoscând mesajele transmise de Alex, ajutaţi-l pe Cipri să descifreze planul de luptă conform convenţiei secrete.

D şi S se pregătesc pentru primul lor concurs de dans şi ei lucreaza momentan la coregrafia de tango. Chiar dacă va fi primul lor concurs, ei deja ştiu n figuri de dans şi au calculat pentru fiecare dintre aceste figuri câţi timpi muzicali durează. Fiindcă le place foarte mult să danseze împreună, ei vor să pregătească o coregrafie frumoasă pentru o piesă care durează exact k timpi muzicali.

Miruna a găsit pe fundul mării o matrice cu n linii şi m coloane având elementele numere naturale. Din motive necunoscute, Mirunel, prietenul misterios al Mirunei, vrea să afle care este latura celei mai mari submatrice pătratice care conţine maxim k numere distincte. Submatricea cu colţul stânga-sus (xs, ys) şi colţul dreapta-jos (xd, yd) este formată din toate elementele din matrice având indicele liniei în intervalul [xs, xd] şi indicele coloanei în intervalul [ys, yd]. Scrieţi un program care să determine latura maximă a unei submatrice care respectă condiţiile lui Mirunel.

Se dă o matrice cu M linii şi N coloane în care toate elementele sunt numere naturale. Fie L latura maximă a unei submatrici simetrice din această matrice. Pentru fiecare dimensiune i între 1 și L să se determine câte submatrici simetrice şi cu latura i ale matricii date există.

Se organizează o petrecere la care participă N băieți (numerotați de la 1 la N) și N fete (numerotate de la 1 la N). S-a decis ca petrecerea să dureze mai multe minute. În fiecare minut fetele și băieții formează o configurație de dans, adică N perechi, după una din următoarele reguli:
1. băiatul i dansează cu fata i;
2. băiatul i dansează cu fata j și atunci obligatoriu băiatul j dansează cu fata i.
De exemplu, pentru N = 7, două configurații de dans posibile sunt:
(1, 1) (2, 2) (3, 7)(4, 5) (5, 4) (6, 6) (7, 3)
(1, 1) (2, 2) (3, 3)(4, 5) (5, 4) (6, 6) (7, 7)
Prin perechea (i, j) s-a notat faptul că băiatul i dansează cu fata j. Două configurații sunt distincte dacă ele diferă prin cel puțin o pereche. Ştiind că în fiecare minut trebuie formate configuraţii de dans distincte, să se determine câte minute durează petrecerea.