Lista de probleme 17

Pentru un număr dat cu k cifre $c_1{c}_2\dots c_k$, se numeşte algoritm de deplasare circulară spre dreapta de la o cifră iniţială $c_i$, la o cifră finală $c_j$, deplasarea din cifră în cifră spre dreapta de $c_i$ ori (1≤i,j≤k). Dacă pe parcursul deplasării s-a ajuns la cifra $c_k$, se continuă deplasarea circulară spre dreapta cu cifra $c_1$. Un număr cu k cifre se numeşte număr „circular” dacă îndeplineşte următoarele două cerinţe:

• toate cifrele sunt nenule;
• pornind de la cifra $c_1$, aplicând algoritmul de deplasare circulară spre dreapta de exact k ori, se ajunge din nou la $c_1$, fiecare dintre cifrele numărului fiind exact o singură dată cifră iniţială.

Scrieţi un program care citeşte numărul natural nenul n, apoi numerele naturale $x_1,x_2,\dots ,x_n$, şi determină: a) cel mai mare număr din şir în care există cel puţin o cifră care apare de minimum două ori, iar în cazul în care în şir nu există un astfel de număr, se va afişa cel mai mare număr din şir; b) un şir $a_1,a_2,\dots ,a_n$ de n numere naturale pentru care un element $a_i$(1≤i≤n)se calculează astfel:

• este egal cu $x_i$ , dacă $x_i$ este număr circular;
• este numărul cel mai apropiat de $x_i$ (număr mai mare sau mai mic decât $x_i$), cu proprietatea că este număr circular; dacă pentru un număr din şir se identifică un număr circular y, $y>x_i$ şi un număr circular z, z<$x_i$, pentru care $y–x_i$ = $x_i–z$, atunci se va alege numărul y.

În oraşul Iaşi, cele N firme IT derulează în prezent M proiecte din acest domeniu (printre care şi ONI 2012). Firmele sunt identificate prin numere naturale de la 1 la N, iar proiectele sunt identificate prin numere naturale de la 1 la M. Fiecare proiect are una sau mai multe etape, o etapă fiind executată de o singură firmă IT. Spunem că o firmă coordonează un proiect dacă execută mai mult de jumătate din etapele proiectului.
Cunoscând numărul firmelor IT, numărul proiectelor, numărul de etape ale fiecărui proiect şi firmele ce execută fiecare etapă, să se determine firma/firmele care coordonează cel mai mare număr de proiecte.

Se consideră n copaci de diferite înălţimi, aflaţi în linie dreaptă la distanţe egale, numerotaţi de la 1 la n. Pentru fiecare copac se cunoaşte înălţimea sa $H_i$. Cum şi copacii simt nevoia să socializeze, fiecare dintre ei are prieteni printre ceilalţi copaci. Prietenii oricărui copac i se pot afla atât la stânga, cât şi la dreapta sa. Relaţiile de prietenie sunt definite în felul următor: pentru fiecare copac i considerăm un şir $d_1,d_2,\dots ,d_x$ reprezentând prietenii copacului i situaţi în dreapta sa şi un şir $s_1,s_2,\dots ,s_y$ reprezentând prietenii copacului i situaţi în stânga acestuia. Copacii din cele două şiruri corespunzătoare unui copac i formează împreună lista prietenilor acestuia. Determinaţi în câte moduri se pot alege 3 copaci diferiţi dintre cei n cu proprietatea că, oricum am alege 2 copaci dintre cei 3, fie aceştia copacul A şi copacul B, atunci A este prieten cu B şi B este prieten cu A.

Locuitorii planetei Aritmo au hotărât ca în celebrul an 2012 să le explice pământenilor metoda plus de adunare a numerelor naturale pe planeta lor. La fel ca și planetele, înainte de adunare, numerele se aliniază astfel încât să se obțină cât mai multe cifre egale pe aceleași poziții. Cifrele egale, astfel obținute, se elimină din cele două numere. Pentru a obține rezultatul final, se adună cele două numerele deplasate, obținute după eliminare.

Într-o expresie în care se adună mai multe numere pot să apară paranteze rotunde. În evaluarea unei asemenea expresii, numită expresie parantezată, se efectuează mai întâi adunările din paranteze conform metodei descrise mai sus, parantezele fiind apoi înlocuite cu rezultatul adunărilor din paranteze.

Pentru a-i ajuta pe pământenii care doresc să învețe acest nou mod de adunare, scrieți un program care citește o expresie parantezată și determină:

a) adâncimea expresiei date;
b) valoarea acestei expresii.

După ce au vizitat toate obiectivele turistice din municipiul Iaşi, Ioana şi Maria au inventat un joc.

Ele au la dispoziţie un număr de n cutii aranjate în linie dreaptă, numerotate în ordine de la 1 la n, şi un număr de m bile ce pot fi aşezate în unele dintre aceste cutii. Unele cutii sunt deteriorate, astfel că bilele dispar dacă sunt puse în acele cutii.

O mutare constă în alegerea unei bile şi poziţionarea ei în una din cutiile învecinate (precedenta sau următoarea ). Bilele pot fi mutate după următoarea regulă: când o bilă a fost mutată pentru prima dată într-o anumită direcţie, atunci bila îşi păstrează direcţia de deplasare la următoarele mutări (de exemplu, dacă o bilă a fost mutată pentru prima dată spre stânga atunci orice mutări ulterioare ale acestei bile se pot face doar spre stânga).

Jocul se termină atunci când nici un jucător nu mai poate face nici o mutare. Pierde primul jucător care nu mai poate face nici o mutare. Fetele joacă un număr de T astfel de jocuri. Ştiind că Ioana este prima care face o mutare, iar apoi fetele mută alternativ, se cere să se stabilească pentru fiecare din cele T jocuri dacă ea are sau nu o strategie sigură de câştig.

Scrieţi un program care citeşte cheia de codificare şi un text codificat şi determină mesajul decodificat.

Gigel primea de la mama lui, ca temă, o foaie pe care era scris un şir de N numere întregi. Singurul calcul pe care ştia să îl facă până acum era suma tuturor numerelor. Pentru aceasta el plasa N-1 semne de adunare, +, între numerele aflate pe poziţii consecutive în şir şi calcula astfel suma acestor numere. Între timp a crescut şi a învăţat şi operaţia de înmulţire pentru care foloseşte semnul *. Din şirul celor N-1 semne de adunare, îi trece prin minte să înlocuiască K semne + cu K semne *.
Îşi dă seama că tema se complică, deoarece înmulţirile trebuie efectuate înaintea adunărilor, dar nu se dă bătut şi duce calculul până la capăt.
Scrieţi un program care să determine valoarea minimă pe care o poate obţine şi valoarea maximă pe care o poate obţine după înlocuirea menţionată.