Lista de probleme 108

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.

Se dă o matrice cu numere naturale nenule, pătratică, cu liniile şi coloanele numerotate de la 1 la N. Fiecare număr din matrice reprezintă înălţimea unui pilon plasat în acea poziţie.

Putem plasa un observator “sub” matrice (adică pe o poziţie i j cu i > N şi 1 ≤ j ≤ N), de unde poate vedea în 3 direcţii:

• nord (pe coloana j);
• nord-vest (elemente din matrice de pe poziţii is,js cu i - is = j - js, dacă există astfel de elemente);
• nord-est (elemente din matrice de pe poziţii is,js cu i - is = js - j, dacă există astfel de elemente);

Se cunoaşte configuraţia matricei şi mai multe poziţii posibile ale observatorului. Să se determine, pentru fiecare poziţie, numărul de piloni pe care îi vede observatorul plasat acolo.

Terminalul unui aeroport este o sală foarte mare având forma unui dreptunghi împărțit în pătrate cu latură unitară. Aici se află mai multe persoane, care trebuie să poarte la vedere un ecuson cu un cod de bare care poate fi citit în orice moment de camerele de supraveghere și decodificat de calculatoarele serviciului de protecție și pază. Într-un pătrat cu latură unitară poate să se afle doar o singură persoană la un moment dat. Sala este reprezentată printr-o matrice cu R linii și C coloane, elementele sale fiind numere naturale de cel mult 6 cifre cu valorile: 0 – pentru spațiu neocupat, respectiv numere naturale nenule, care reprezintă identificatorul (ID-ul) persoanelor. Printre aceste persoane există persoane infiltrate (intruși) care au ID-uri cu valori identice cu ale altor persoane. Dacă există două sau mai multe persoane cu același ID, acestea sunt considerate toate suspecte.

Intrușii vor să ajungă în apropierea unor VIP-uri (persoane importante), pentru a le înregistra discuțiile cu un microfon care poate înregistra sunete în interiorul unui pătrat cu latura D, în centrul căruia se află chiar el. Acest pătrat nu este cuprins neapărat integral în matricea sălii (vedeți figura alăturată)!

Prin convenție, ID-urile VIP-urilor sunt numere prime distincte. În plus, și un ID al unui VIP poate fi copiat, crescând astfel numărul suspecților. Un VIP se caracterizează printr-un nivel de importanță: cu cât ID-ul este un număr mai mare, cu atât nivelul de importanță este mai mare (este „mai importantă”).

Persoanele suspecte au asociat un „grad de periculozitate”. Acesta este cu atât mai mare cu cât numărul de VIP-uri aflate în interiorul pătratului de latură D, în centrul căruia se află suspectul, este mai mare. Dacă există doi suspecți cu același grad de periculozitate, se consideră „mai periculoasă” persoana care are în pătratul său VIP-ul cu ID-ul cel mai mare. În caz de egalitate, se consideră „mai periculoasă” persoana care este așezată pe o linie cu un indice mai mic, iar la egalitate de indici de linii, pe o coloană cu indice mai mic. Există și persoane suspecte cu gradul de periculozitate 0, dacă în interiorul pătratului în centrul căruia se plasează nu există niciun număr prim.

Cerințe

1) Să se determine numărul persoanelor suspecte aflate în sala de așteptare.
2) Să se determine ID-ul și coordonatele persoanelor suspecte, (RSi -linia suspectului i, CSi -coloana suspectului i) în ordinea descrescătoare a „gradului de periculozitate”.

Gigel a primit de la prietenul său Programatorul o hartă a grădinii acestuia. Grădina are forma dreptunghiulară şi harta pe care a primit-o Gigel conţine informaţii despre starea culturii de pomi fructiferi. Mai precis ea conţine înălţimile fiecărui copac şi zonele în care s-au săpat gropi dar încă nu au fost plantaţi copaci. Harta grădinii poate fi reprezentată sub forma unei table dreptunghiulare cu N linii, numerotate de la 1 la N de sus în jos, şi M coloane, numerotate de la 1 la M de la stânga la dreapta. În fiecare celulă se află un număr real corespunzător înălţimii copacului sau valoarea 0 corespunzătoare unei gropi.

Cunoscând coordonatele unui punct de pe hartă ajutaţi-l pe Gigel să determine pe care dintre cele 8 direcţii N, NE, E, SE, S, SV, V, NV corespunzătoare acestui punct se află cele mai multe gropi.

Se dă o matrice pătratică cu N linii şi N coloane care iniţial are toate elementele egale cu 0. Pe această matrice se execută 4 tipuri de operaţii:

1 LIN VAL: toate elementele de pe linia LIN cu valoarea mai mică decât VAL iau valoarea VAL.
2 COL VAL: toate elementele de pe coloana COL cu valoarea mai mică decât VAL iau valoarea VAL.
3 LIN COL: să se afişeze valoarea elementului de pe linia LIN şi coloana COL.
4: să se afişeze suma elementelor de pe diagonala principală.

Afișați rezultatele operațiilor 3 și 4 în ordinea citirii.

Într-o matrice pătratică, pentru fiecare poziție identificată prin linia i și coloana j, se adună toate elementele care se găsesc pe linia i sau pe coloana j sau pe diagonalele care trec prin a[i][j] și sunt paralele cu diagonala principală sau cu diagonala secundară, cu precizarea că în această sumă, elementul a[i][j] apare o singură dată.

Să se determine suma maximă care se obține prin procedeul prezentat mai sus precum și poziția corespunzătoare (linia și coloana) sumei maxime. Dacă există mai multe poziţii pentru care se obţine suma maximă, se va alege prima dintre acestea, în ordinea parcurgerii matricei pe linii.

În camera copiilor problema spațiului este esențială. De aceea locul unde sunt depozitate jucăriile este asemănător unei matrici pătratice, dispuse vertical, fiecare jucărie ocupând un locație bine stabilită.

Entuziasmul și bucuria copiilor în a se juca este bine cunoscută, dar și ”disponibilitatea” acestora de a ordona (reașeza) jucăriile la locul prestabilit este proverbială. Cum, după o rundă de joacă, întotdeauna urmează un episod din serialul de desene animate preferat, copii așează la întâmplare jucăriile.

Cunoscând numărul M de jucării, iar pentru fiecare jucărie locația în care copii au pus jucăria (linie, coloană), precum și locația unde trebuie corect pusă aceasta (linie, coloană), ajutați bona să reașeze jucăriile astfel încât numărul de mutării să fie minim. În cazul în care locația unde trebuie mutată o jucărie este ocupată, atunci bona depozitează temporar jucăria într-o locație specială, dacă este liberă, până când locația unde trebuie mutată se va elibera.

Să se determine:

• numărul minim de mutări ce nu necesită folosirea locației speciale
• numărul minim de mutări necesar rearanjării tuturor jucăriilor

Pe o zonă în formă de dreptunghi cu laturile de lungimi N și M se găsesc NxM pătrate de latură 1. În centrul fiecărui pătrat se găsește înfipt câte un ac de grosime neglijabilă. Fiecare ac este descris de înălțimea sa. Această zonă se poate reprezenta ca un tablou bidimensional de dimensiuni N și M, iar fiecare element din matrice reprezintă înălțimea (număr natural nenul) fiecărui ac. În centrul pătratului (N,M) există o cameră de luat vederi de ultimă generație, mobilă, care se poate roti cu 360⁰ în orice plan, situată la nivelul solului. Dimensiunile camerei sunt neglijabile.

Pentru direcția N, camera va vedea acul de coordonatele (3,4) – în totalitate, iar acul (2,4) se va vedea doar parțial . Acul (1,4) nu se vede pentru că este acoperit total de (2,4). În direcția V, camera va vedea doar acul (4,3), deoarece (4,2) și (4,1) sunt acoperite total de (4,3). Pentru celelalte direcții se vor vedea parțial sau în totalitate acele (3,3), (3,2), (3,1), (2,3), (1,3), (2,2), (2,1), (1,2). Acul (1,1) nu se vede din cauza acului (2,2), care îl acoperă total. Acul (2,2) se vede doar parțial, pentru că o parte din el este acoperit de acul (3,3).

1. Câte ace vede camera de luat vederi dacă se poate roti în plan vertical, doar în direcțiile N și V?
2. Câte ace vede camera de luat vederi dacă se poate roti în orice plan și în orice direcții?

Avem o jucărie formată din NxN pătrate de latură 1 dispuse ca într-o matrice cu N linii și N coloane. Liniile și coloanele matricei sunt numerotate de la 1 la N, iar N este mereu impar. Pătrățelele pot fi albe și le vom codifica 0, sau negre și le codificăm 1. Împărțim matricea în zone concentrice astfel: zona 1 este formată din linia 1, coloana N, linia N și coloana 1; zona 2 este formată din linia a doua, coloana N-1, linia N-1, coloana 2 etc. Sunt [N/2] astfel de zone. În mijlocul matricei este, evident, un singur element, N fiind impar. Asupra oricărei zone putem aplica o operație de rotire, doar spre stânga.

Dată fiind codificarea jucăriei, precum și “lungimea” maximă permisă pentru o rotire în oricare zonă, să se determine numărul de posibilități de a aplica rotiri asupra zonelor așa încât să rezolvăm jucăria. Evident, unei zone i se poate aplica o singură rotire, de lungime cuprinsă între 0 și valoarea maximă permisă.

Se consideră o matrice A având N linii și N coloane. Elementele acesteia aparțin mulțimii {0,1,2}. Pe fiecare linie și pe fiecare coloană valorile elementelor sunt dispuse crescător.

Fie două elemente din matrice situate pe linia i1 și coloana j1 respectiv i2 și j2,unde i1≤i2 și j1≤j2. O submatrice a lui A, având colțurile stânga-sus şi dreapta-jos în (i1,j1) și (i2,j2), este formată din toate elementele situate pe linii cuprinse între i1 și i2, inclusiv, și coloane între j1 și j2, inclusiv. Numim submatrice constantă o submatrice a matricei A, având toate elementele egale.

Realizați un program care determină numărul maxim K de elemente pe care îl are o submatrice constantă a lui A și numărul submatricilor constante formate din K elemente.