Lista de probleme 78

Numerele iajb sunt numerele care pot fi scrise sub forma i * a + j * b. Cunoscând a și b și un număr n, să se determine valorile i și j pentru care se vor forma primele n numere iajb in ordine crescătoare.

Jaina are nevoie de ajutor pentru a ajunge la mentorul ei.

Se consideră șirul infinit inf="INFINFINFINF...".

Se dau două numere naturale n și k și un șir de caractere s de lungime n format doar din caracterele 'I' , 'N' și 'F'.

Să se afle numărul minim de modificări ce trebuie realizate în șirul s pentru a obține un subșir de lungime k al șirului infinit inf.

Eroul nostru Susan se află într-un turn de formă cubică, de latură n. El dorește să ajungă la comoara ascunsă în interiorul turnului. Din fericire, Susan a făcut rost de o hartă care îi indică cu exactitate coordonatele locului în care se află comoara din turn. Eroul nostru vrea să știe care este distanța minimă pe care o poate parcurge pentru a ajunge la comoară.

Într-o ţară în care corupţia este în floare şi economia la pământ, pentru a obţine toate aprobările necesare în scopul demarării unei afaceri, investitorul trebuie să treacă prin mai multe camere ale unei clădiri în care se află birouri.

Clădirea are un singur nivel în care birourile sunt lipite unele de altele formând un caroiaj pătrat de dimensiune n•n. Pentru a facilita accesul în birouri, toate camerele vecine au uşi între ele. În fiecare birou se află un funcţionar care pretinde o taxă de trecere prin cameră (taxă ce poate fi, pentru unele camere, egală cu 0). Investitorul intră încrezător prin colţul din stânga-sus al clădirii (cum se vede de sus planul clădirii) şi doreşte să ajungă în colţul opus al clădirii, unde este ieşirea, plătind o taxă totală cât mai mică.

Ştiind că el are în buzunar S euro şi că fiecare funcţionar îi ia taxa de cum intră în birou, se cere să se determine dacă el poate primi aprobările necesare şi, în caz afirmativ, care este suma maximă de bani care îi rămâne în buzunar la ieşirea din clădire.

În ultima ecranizare a celebrei piese shakespeariene Romeo și Julieta trăiesc într-un oraș modern, comunică prin e-mail și chiar învață să programeze. Într-o secvență tulburătoare sunt prezentate frământările interioare ale celor doi eroi încercând fără succes să scrie un program care să determine un punct optim de întâlnire.
Ei au analizat harta orașului și au reprezentat-o sub forma unei matrice cu N linii şi M coloane, în matrice fiind marcate cu spațiu zonele prin care se poate trece (străzi lipsite de pericole) şi cu X zonele prin care nu se poate trece. De asemenea, în matrice au marcat cu R locul în care se află locuința lui Romeo, iar cu J locul în care se află locuința Julietei. Ei se pot deplasa numai prin zonele care sunt marcate cu spaţiu, din poziţia curentă în oricare dintre cele 8 poziţii învecinate (pe orizontală, verticală sau diagonale).
Cum lui Romeo nu îi place să aştepte şi nici să se lase aşteptat n-ar fi tocmai bine, ei au hotărât că trebuie să aleagă un punct de întâlnire în care atât Romeo, cât şi Julieta să poată ajunge în acelaşi timp, plecând de acasă. Fiindcă la întâlniri amândoi vin într-un suflet, ei estimează timpul necesar pentru a ajunge la întâlnire prin numărul de elemente din matrice care constituie drumul cel mai scurt de acasă până la punctul de întâlnire. Şi cum probabil există mai multe puncte de întâlnire posibile, ei vor să îl aleagă pe cel în care timpul necesar pentru a ajunge la punctul de întâlnire este minim.
Scrieţi un program care să determine o poziţie pe hartă la care Romeo şi Julieta pot să ajungă în acelaşi timp. Dacă există mai multe soluţii, programul trebuie să determine o soluţie pentru care timpul este minim.

Pe autostrada Soarele Estului sunt aşezate de-a lungul şoselei, la distanţe egale, panouri publicitare ale unor firme. Aceeaşi firmă, poate să aibă mai multe panouri publicitare şi fiecare panou poate să apară în mai multe locuri. Panourile se identifică prin numere naturale, numărul total de panouri fiind N. Firma X Corporation are panouri de T tipuri diferite. Firma a primit aprobarea construirii unui mare complex turistic în apropierea autostrăzii; de aceea, pentru alegerea locului, este interesată şi de următorul aspect: care este lungimea minimă de şosea, în care se pot întâlni, toate cele T tipuri de panouri publicitare ale firmei, indiferent de ordinea acestora, şi indiferent dacă între ele se mai interpun sau nu panouri ale altor firme. Cunoscând N – numărul total de panouri de la marginea autostrăzii şi ordinea amplasării lor, ca şi cele T tipuri de panouri amplasate de firmă, determinaţi numărul minim de intervale dintre două panouri între care firma X Corporation îşi regăsește toate panourile sale.

Înspăimântătorii tăi luptători au răpit-o pe Prinţesa Ghiocela şi au închis-o în castelul tău de pe vârful Muntelui Pleşuv. Deoarece eşti un geniu malefic, te-ai hotărât să îi oferi prinţesei iluzia unei şanse de evadare.
Castelul tău are forma unui caroiaj cu M linii şi N coloane. Cele M x N celule ale castelului sunt numerotate de la 1 la M x N în ordinea parcurgerii caroiajului pe linii de sus în jos, iar pe aceeaşi linie în ordinea coloanelor de la stânga la dreapta. În fiecare dintre celulele castelului ai pus câte o cheie, mai precis celula i conţine cheia cu numărul i. Evident, pentru a intra într-o cameră, prinţesa are nevoie de o anume cheie care permite deschiderea acesteia. Mai mult, dintr-o cameră prinţesa se poate deplasa într-un moment numai într-una dintre cele maximum patru camere adiacente pe orizontală şi verticală, doar dacă deţine cheia necesară deschiderii sale. Odată ce a intrat într-o cameră şi a obţinut o cheie, prinţesa o păstrează şi poate să o utilizeze ori de câte ori doreşte. Deşi eşti convins că prinţesa nu va scăpa din castel, eşti curios să afli câte dintre cele M x N camere îi sunt accesibile. Date fiind dimensiunile castelului, camera în care se află iniţial prinţesa şi cheile necesare deschiderii fiecăreia dintre camere, află răspunsul la această întrebare presantă.

Miruna se pregăteşte de vacanţa de vară. Ea a hotărât deja că împreună cu un grup de colegi să facă o excursie în regatul INFO unde moneda locală se numeşte BOSS. A studiat deja harta acestei zone şi a aflat multe lucruri interesante. Ea ştie că regatul se află pe o insula cu suprafaţa uscatului sub forma dreptunghiulară ce poate fi reprezentată ca o matrice cu N linii şi M coloane în care fiecare element este un cod pentru un tip de obiectiv turistic ce poate fi vizitat. Deoarece sosirea şi plecarea de pe insulă se face cu avionul, ea cunoaşte poziția (l0,c0) unde va fi debarcată şi poziţia (lf,cf) unde va fi plecarea de pe insulă. Ea se poate deplasa pentru vizitarea obiectivelor turistice doar în celule vecine pe cele opt direcţii (N, S, E, V, NE, NV, SE, SV), iar dacă nouă poziţie are alt cod decât cel din care venise la pasul precedent, atunci trebuie să plătească o taxa de vizitare egală cu produsul codurilor celor doua zone (exprimată tot în moneda locală, BOSS!!!). Miruna ar dori să afle care ar fi suma minimă necesară pentru a se deplasa până la locul de plecare de pe insulă. Dându-se configuraţia regatului şi poziţiile de plecare şi sosire, să se determine suma minimă necesară
deplasării.

Într-un oraș există un hotel de formă cubică, cu N etaje, numerotate de la 1 la N. Suprafața fiecărui etaj K (1 ≤ K ≤ N) este pătratică și este împărțită în N x N camere identice alăturate, dispuse pe N linii și N coloane, fiecare cameră având drept etichetă un triplet de numere naturale (K L C) (K=etajul, L=linia, C=coloana, 1 ≤ L, C ≤ N), ca în imaginea alăturată.

Dintre cele N x N x N camere ale hotelului, una este specială deoarece în ea locuiește de mult timp un șoricel. Fiind isteț, el știe eticheta camerei în care se află precum și eticheta camerei în care bucătarul hotelului depozitează alimente.

Studiind hotelul, șoricelul a constatat că pe fiecare etaj, din orice cameră poate intra în toate camerele care au un perete comun cu aceasta (existând un mic orificiu pentru aerisire).

De asemenea, șoricelul a constatat că din fiecare cameră (situată la etajele 2, 3, …, sau N-1) poate intra în camera situată imediat deasupra ei și în camera situată imediat sub ea.

Fiind un șoricel binecrescut, el nu intră în nicio cameră ocupată de clienți ca să nu-i deranjeze. Hotelul având mulți clienți, șoricelul trebuie să-și găsească cel mai scurt traseu de la camera lui la camera cu alimente, traseu care să treacă printr-un număr minim de camere, toate neocupate.

Se cere să se determine:
a) numărul de camere prin care trece cel mai scurt traseu al șoricelului de la camera lui la camera cu alimente (inclusiv camera lui şi camera cu alimente);
b) etichetele camerelor prin care trece traseul determinat la punctul a).