Lista de probleme 33

Sărbătorile de iarnă tocmai s-au încheiat. Florinel dorește să-și ajute părinții la despodobirea bradului. Tubul luminos pe care l-au folosit anul acesta este mai special. Are N3 becuri luminoase numerotate de la 1 la N3, iar fiecare bec care este inscripționat cu un număr prim, va rămâne mereu aprins. Cutia în care trebuie strâns tubul este un cub de latură N. Becul cu numărul 1, trebuie pus în colțul de coordonate (1,1,1), restul în spirală până la umplerea nivelului, apoi nivelul următor în sens invers, ș.a.m.d.

Cunoscând latura N a cubului, să se umple cubul cu tubul luminos (becurile fiind legate crescător), apoi să se determine:

1. Coordonatele (x,y,z) ale becului cu numărul V. (x-linia, y-coloana, z-înălțimea)
2. Numărul de becuri luminoase situate pe fiecare față a cubului.

Leneşul este un animal foarte leneş. El se deplasează numai în linie dreaptă, dar face din când în când câte un popas. În această problemă leneşul trebuie să traverseze de la nord la sud şi înapoi un teren reprezentat de o matrice de dimensiuni M×N cu valori numere naturale. Valorile reprezintă efortul cerut pentru traversarea zonei respective. Leneşul va alege o coloană pentru traversarea matricei, iar pentru popasuri, în număr de k1, va alege zone alăturate drumului din coloana din stânga sau cea din dreapta. În cazul în care se va întoarce va proceda la fel, dar va face k2 popasuri. Regulile problemei cer ca cele două drumuri să nu aibă zone comune.

Cunoscând dimensiunile M, N ale terenului, numărul de popasuri k1, k2 și efortul pentru traversarea fiecărei zone a terenului, să se determine:

1. Efortul minim de parcurgere a terenului de la Nord la Sud, folosind k1 popasuri.
2. Efortul minim de parcurgere a terenului de la Nord la Sud și înapoi de la Sud la Nord, folosind k1 popasuri la deplasarea Nord – Sud, respectiv k2 popasuri la deplasarea Sud – Nord.

În satul vecin există un teren agricol de formă dreptunghiulară împărțit în N*M pătrate elementare identice, dispuse alăturat câte M pe fiecare rând şi câte N pe fiecare coloană. Rândurile sunt numerotate de la 1 la N, iar coloanele de la 1 la M. Un pătrat elementar situat în teren pe rândul R și coloana C este identificat prin coordonatele (R,C).

Suprafețe dreptunghiulare din teren (formate fiecare din unul sau mai multe pătrate elementare alăturate) sunt revendicate de T fermieri din sat, în calitate de moștenitori, pe baza actelor primite de la strămoșii lor. Pentru că au apărut și acte false, s-a constat că pot exista mai mulți fermieri care revendică aceleași pătrate elementare.

În cele T acte ale fermierilor, suprafețele dreptunghiulare sunt precizate fiecare prin câte două perechi de numere (X,Y) și (Z,U), reprezentând coordonatele primului pătrat elementar din colțul stânga-sus al suprafeței (rândul X și coloana Y), respectiv coordonatele ultimului pătrat elementar situat în colțul dreapta-jos al suprafeței (rândul Z și coloana U).

Scrieţi un program care să citească numerele naturale N, M, T, R, C apoi cele T perechi de coordonate (X,Y) și (Z,U) precizate în acte (corespunzătoare suprafețelor dreptunghiulare revendicate) și care să determine:

1. numărul fermierilor care revendică pătratul elementar identificat prin coordonatele (R,C);
2. numărul maxim de fermieri care revendică același pătrat elementar;
3. numărul maxim de pătrate elementare ce formează o suprafață pătratică nerevendicată de niciun fermier.

Oli are un echer de forma unui triunghi dreptunghic, cu catetele de lungimi L1 și L2 unități, și o foaie de caiet de matematică cu M rânduri și N coloane de pătrățele având latura de o unitate.

Oli a poziționat echerul în colțul din stânga sus al foii de hârtie, ca în imaginea alăturată și vrea să îl mute astfel încât să atingă colțul din dreapta jos al foii de hârtie cu oricare din colțurile echerului, utilizând doar mutări de forma:

Scrieţi un program care citeşte lungimile catetelor echerului, numărul de rânduri, respectiv numărul de coloane ale foii de hârtie și determină:

1. numărul minim de mutări K, prin care poate muta echerul din colțul din stânga sus al foii de matematică, astfel încât echerul să atingă colțul din dreapta jos al foii;
2. cele K mutări efectuate pentru a deplasa echerul din colțul din stânga sus al foii, până când un colț al echerului atinge colțul din dreapta jos al foii; dacă există mai multe soluții, se va afișa soluția minimă în sens lexicografic.

Jocul pe care îl joaca Robo atunci când se plictisește este un joc inteligent pentru roboței. Pe ecranul tabletei lui roboțești, sunt N căsuțe de formă pătrată, cu latura egală cu 1. Căsuțele sunt așezate pe un rând, una lângă alta, fiind etichetate, în această ordine, cu numere de la 1 la N. Fiecare căsuță conține câte un număr natural, identificatorul câte unuia dintre prietenii săi, roboței, ca și el. Identificatorii se pot repeta.

Robo poate interschimba conținutul a două căsuțe, numai dacă distanța dintre centrele acestora pe orizontală este egală cu distanța dintre brațele sale; distanța, pe orizontală, dintre centrele a două căsuțe etichetate cu i, respectiv cu j, este j-i (1≤i<j≤N).

El își poate fixa în orice moment distanța dintre brațe la 1 sau își poate dubla distanța curentă dintre brațe, de oricâte ori este necesar, fără a depăși valoarea N-1. Astfel, distanța dintre brațele sale poate fi 1, apoi, prin dublare, 2, apoi, prin dublare 4, apoi, prin dublare 8 etc. La începutul jocului, distanța dintre brațele lui Robo este 1. De fiecare dată când consideră convenabilă distanța dintre brațe, realizează o interschimbare.

Se cere ca Robo să așeze identificatorii în căsuțe în ordine crescătoare, prin maximum 12500 interschimbări de tipul celei precizate mai sus.

Pentru a participa la un concert, n persoane s-au așezat la coadă pe un singur rând în așteptarea deschiderii casei de bilete. Înălțimile celor n persoane sunt toate distincte. Pe baza acestei informații cruciale, agenții de securitate au decis ca din motive de … securitate, ordinea persoanelor care așteaptă la coadă trebuie schimbată în funcție de înălțimile lor.

Astfel, agentii de pază vor alege, pe rând, câte o persoană și o vor trimite la sfârșitul rândului. După fiecare operație de tipul acesta, să-i spunem “de mutare”, rândul se restrânge, ocupându-se poziția rămasă liberă. Strategia agenților de pază este aceasta: la terminarea tuturor operațiilor de mutare, riscul minim de securitate se obține dacă toate persoanele aflate în dreapta persoanei celei mai înalte vor fi mai înalte decât cele aflate în stânga persoanei cele mai înalte. În plus, înalțimile persoanelor vor fi crescătoare până la poziția k a persoanei celei mai înalte și descrescătoare după poziția k.

Mai exact: dacă h[1], h[2], …, h[n] sunt înălțimile persoanelor după finalizarea operațiilor de mutare, atunci: există o poziție k, cu 1 ≤ k ≤ n astfel încât h[1] < h[2] < ... h[k-1] < h[k] > h[k+1] > … > h[n-1] > h[n] și în plus h[i] < h[j] pentru oricare i < k și k < j.

Deoarece o asemenea logică este greu de combătut, iar agenții nu au aerul că vor să glumească, persoanele care așteaptă la coadă vor accepta toate mutările impuse de către aceștia.

Cunoscând numărul de persoane n și înălțimile h[1], h[2], …, h[n] ale acestora să se scrie un program care determină :

1. Poziția persoanei celei mai înalte în rândul inițial, în cazul în care nu sunt necesare operații de mutare.
2. Numărul minim de mutări necesare pentru ca rândul de persoane să prezinte un risc minim de securitate.

În această poveste este vorba despre o casă cu mai multe camere. O cameră are forma unui pătrat de latură 1. Dacă două camere au un perete comun, atunci se poate trece dintr-o cameră în alta. Casa nu are neapărat formă dreptunghiulară.

O asemenea casă poate fi descrisă în povestea noastră în două moduri:

• prin matricea minimală: o matrice cu elemente 0 şi 1 în care există N valori egale cu 1, ce corespund camerelor, iar prima linie, ultima linie, prima coloană şi ultima coloană au cel puţin un element egal cu 1.
• prin construcţie: un şir de N-1 perechi (a[i], b[i]) 1≤i<n în care a[i] din {1,2,…,i} şi b[i] din {N, S, E, V}. Camerele vor fi numerotate de la 1 la n. Perechea (a[i], b[i]) precizează poziţia camerei i+1 faţă de camera a[i]: E înseamnă la dreapta (est), N deasupra (nord), V la stânga (vest), S dedesubt (sud). Observaţi că pentru prima cameră nu există nicio precizare!

De exemplu, casa de mai sus poate fi descrisă de şirul (1 E) (2 E) (2 S) (3 S), adică a doua cameră e “lipită” la est de prima cameră, următoarea (a treia) la est de camera 2, a patra la sud de camera 2, iar ultima la sud de camera 3.

Cerința

1. Se dă descrierea unei case prin construcţie şi se cere descrierea acesteia prin matricea minimală.
2. Se dă descrierea unei case prin matricea minimală şi se cere descrierea acesteia prin construcţie.

Un arheolog a găsit un sipet interesant. După ce l-a deschis cu grijă, a constatat cu surprindere că sipetul conține bănuți de aur. Uitându-se mai atent a mai găsit ceva: un pergament ascuns într-un compartiment secret al sipetului, cu un text scris într-o limbă antică, pe care, din fericire, arheologul o cunoștea. Din text a reieșit că un grup de negustori foarte bogați a vrut să ascundă în mare secret averea breslei lor, formată din monede de aur, deoarece se prevestea un război cumplit. Negustorii știau că există șanse ca această comoară să fie găsită și confiscată de dușmani, deci s-au sfătuit cum e mai bine să procedeze, cum să ascundă comoara. Arheologul a reușit să deducă din text următoarele:

a) Cele N monede, care formau averea breslei, au fost împărțite în maximum trei feluri de grămezi, formate din p1, p2 și p3 bănuți, p1, p2 și p3 fiind numere prime consecutive, p1<p2<p3. Fiecare grămadă a fost pusă în întregime într-un sipet.
b) Este posibil să existe 0 (zero) grămezi formate din p1 sau p2 sau p3 monede, scopul fiind să se obțină o împărțire în care numărul monedelor rămase nedistribuite să fie minim, iar dacă există mai multe posibilități, se alege aceea pentru care numărul de grămezi este mai mare. Dacă există mai multe astfel de soluții, se consideră corectă oricare dintre ele.
c) Monedele care nu au putut fi distribuite conform regulilor stabilite, au fost donate bisericii.

Scrieți un program care determină numărul maxim S de sipete și numărul sipetelor cu p1, p2 respectiv p3 monede, precum și suma donată bisericii.

Pe o tablă de şah cu N linii şi N coloane sunt plasaţi M nebuni. După cum se ştie de la jocul de şah, nebunii atacă doar în diagonală.

O poziţie de pe tabla de şah este considerată sigură dacă nu este atacată de niciun nebun aflat pe tablă.

Scrieţi un program care să determine numărul de poziţii sigure de pe tabla de şah.

Manole a învățat de la profesorul de informatică cum să calculeze suma elementelor oricărei matrice A cu N linii și M coloane. El numerotează liniile de la 1 la N și coloanele de la 1 la M. Mai mult, Manole fiind extrem de pasionat de numere, va calcula sumele tuturor subtablourilor din cadrul matricei A. Șirul acestor sume îl scrie pe o hârtie, după ce l-a ordonat crescător.

Prin subtablou el înțelege o zonă dreptunghiulară din matricea A, identificată prin colțul stânga-sus (x1,y1) şi colţul dreapta-jos (x2,y2), elementele subtabloului fiind toate elementele A[i][j] pentru care x1≤i≤x2 şi y1≤j≤y2. Suma unui subtablou este suma tuturor elementelor sale.