Lista de probleme 3

#2140 poartas

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 (1<p<5000) 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ă.

#2137 nunta1

Î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.

#2139 codul

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.