Lista de probleme 7

Un experiment urmăreşte comportarea unui şoricel pus într-o cutie dreptunghiulară, împărţită în n x m cămăruţe egale de formă pătrată. Fiecare cămăruţă conţine o anumită cantitate de hrană. Şoricelul trebuie să pornească din colţul (1, 1) al cutiei şi să ajungă în colţul opus (n, m), mâncând cât mai multă hrană. El poate trece dintr-o cameră în una alăturată (două camere sunt alăturate dacă au un perete comun), mănâncă toată hrana din cămăruţă atunci când intră. Se asemenea, nu va intra niciodată într-o cameră fără hrană. Stabiliţi care este cantitatea maximă de hrană pe care o poate mânca.

Se consideră harta universului ca fiind o matrice cu 250 de linii și 250 de coloane. În fiecare celulă se găsește o așa numită poartă stelară, iar în anumite celule se găsesc echipaje ale porții stelare. La o deplasare, un echipaj se poate deplasa din locul în care se află în oricare alt loc în care se găsește o a doua poartă, în cazul nostru în orice altă poziție din matrice. Nu se permite situarea simultană a mai mult de un echipaj într o celulă. La un moment dat un singur echipaj se poate deplasa de la o poartă stelară la alta.

Dându-se un număr p de echipaje, pentru fiecare echipaj fiind precizate poziția inițială și poziția finală, determinați numărul minim de deplasări necesare pentru ca toate echipajele să ajungă din poziția inițială în cea finală.

A fost o dată un balaur cu 6 capete. Într-o zi Făt-Frumos s-a supărat şi i-a tăiat un cap. Peste noapte i-au crescut alte 6 capete în loc. Pe acelaşi gât! A doua zi, Făt-Frumos iar i-a tăiat un cap, dar peste noapte balaurului i-au crescut în loc alte 6 capete … şi tot aşa timp de n zile. În cea de a ( n+1 )-a zi, Făt-Frumos s-a plictisit şi a plecat acasă!

Scrieţi un program care citeşte de la tastatură n , numărul de zile, şi care afişează pe ecran câte capete avea balaurul după n zile.

Directorul unei şcoli doreşte să premieze la sfârşitul anului şcolar pe cei mai buni elevi la învăţătură. Pentru acest lucru el are de rezolvat două probleme:

1. Să determine câţi elevi vor fi premiaţi dintre cei n ( 2≤n≤700 ) elevi ai şcolii. După discuţii aprinse cu ceilalţi profesori se hotărăşte în Consiliul Profesoral ca numărul premianţilor să fie n-k , unde k este cel mai mare număr pătrat perfect mai mic strict decât n . De exemplu, pentru n=150 , k este 144 (pentru că 144=12*12 ), deci vor fi premiaţi 150- 144 = 6 elevi.
2. Pentru a fi cât mai multă linişte la premiere, în Consiliul Profesoral se ia decizia ca elevii care nu vor fi premiaţi să fie aşezaţi pe terenul de sport pe rânduri de câte p elevi (unde p*p=k ). În acest scop, directorul a numerotat elevii nepremiaţi de la 1 la k şi a hotărât ca elevii să fie aşezaţi în ordinea descrescătoare a numerelor asociate.

Scrieți un program care citește numărul de elevi din școală și afișează numărul de elevi premiați și apoi aranjarea elevilor nepremiați.

Autorităţile dintr-o zonă de munte intenţionează să stabilească un plan de urgenţă, pentru a reacţiona mai eficient la frecventele calamităţi naturale din zonă. În acest scop au identificat N puncte de interes strategic şi le-au numerotat distinct de la 1 la N. Punctele de interes strategic sunt conectate prin M căi de acces având priorităţi în funcţie de importanţă. Între oricare două puncte de interes strategic există cel mult o cale de acces ce poate fi parcursă în ambele sensuri şi cel puţin un drum (format din una sau mai multe căi de acces) ce le conectează.
Autorităţile estimează gravitatea unei calamităţi ca fiind suma priorităţilor căilor de acces distruse de aceasta şi doresc să determine un scenariu de gravitate maximă, în care punctele de interes strategic să fie împărţite într-un număr de K grupuri.

În fața palatului Prințesei Mofturoase se află n pețitori așezați la coadă, unul în spatele celuilalt. Fiecare poartă sub mantie un număr de pietre prețioase pe care dorește să le ofere prințesei ca dar de nuntă. Pentru a nu semăna vrajbă în rândurile lor, prințesa a decis să-i determine ca n-1 dintre ei să renunțe în chip pașnic, pețitorul rămas devenind alesul prințesei (indiferent de numărul de pietre prețioase deținute de acesta). Doi pețitori vecini la coadă se pot înțelege între ei astfel: cel care are mai puține pietre prețioase pleacă de la coadă primind de la celălalt un număr de pietre astfel încât să plece acasă cu un număr dublu de pietre față de câte avea. Dacă doi pețitori au același număr de pietre, unul din ei (nu contează care) pleacă luând toate pietrele vecinului său. Un pețitor se poate înțelege la un moment dat cu unul singur dintre cei doi vecini ai săi. După plecarea unui pețitor, toți cei din spatele lui avansează.

Fie P numărul de pietre prețioase pe care le are pețitorul care va deveni alesul prințesei. Se cer valorile distincte ale lui P la care se poate ajunge prin toate succesiunile de negocieri posibile.

Principala misiune a unei expediții științifice este de a studia evoluția vieții pe o planetă nou descoperită. În urma studiilor efectuate, cercetătorii au asociat fiecărui organism viu descoperit pe acea planetă un cod caracteristic. Codul caracteristic este un număr natural de maximum 200 de cifre zecimale nenule. De asemenea, cercetătorii au observat că pentru orice organism viu de pe planetă, codurile caracteristice ale strămoșilor săi pe scara evoluției se pot obține prin ștergerea unor cifre din codul caracteristic al organismului respectiv, iar un organism este cu atât mai evoluat cu cât codul său caracteristic are o valoare mai mare.

Date fiind codurile caracteristice ale două organisme vii diferite, scrieți un program care să determine codul caracteristic al celui mai evoluat strămoș comun al lor.