Lista de probleme 193

Un gospodar are N iepuri (pe care i-a numerotat de la 1 la N) și foarte mulți morcovi. Ce e mai deosebit în această gospodărie este că iepurii sunt organizați ierarhic, în funcție de vârstă, autoritate și nevoile nutriționale. Astfel, fiecare iepure are exact un șef direct (exceptându-l pe Rilă Iepurilă, care este șeful cel mare, șeful tuturor iepurilor). Orice iepure poate avea 0, 1 sau mai mulți subordonați direcți. Orice iepure-șef va mânca cel puțin un morcov mai puțin decât fiecare dintre subordonații săi direcți. Gospodarul nu se poate hotărî câți morcovi să dea fiecărui iepure și ar vrea să știe în câte moduri poate împărți morcovi la iepuri știind că fiecare iepure poate să mănânce minim un morcov și maxim K morcovi. Scrieți un program care calculează numărul de posibilități modulo 30011 de a împărți morcovi la cei N iepuri știind că orice iepure poate mânca între 1 și K morcovi și trebuie să mănânce cu cel puțin un morcov mai puțin decât fiecare dintre iepurii care îi sunt subordonați direcți.

Ion Petre, ca oricare adolescent, este pasionat atât de jocuri, cât şi de informatică. Ultimul astfel de joc este acela de a elimina dintr-un text cuvinte astfel încât fiecare cuvânt rămas să fie urmat de un cuvânt care începe cu aceeaşi literă cu care se termină cuvântul precedent. Face excepţie de la această regulă numai ultimul cuvânt.

Ion Petre, ca oricare adolescent, este pasionat atât de jocuri, cât şi de informatică. Ultimul astfel de joc este acela de a elimina dintr-un text cuvinte astfel încât fiecare cuvânt rămas să fie urmat de un cuvânt care începe cu aceeaşi literă cu care se termină cuvântul precedent. Face excepţie de la această regulă numai ultimul cuvânt.

Pentru un text dat, se cere să se afişeze numărul de cuvinte din text, apoi numărul minim de cuvinte ce pot fi eliminate astfel încât în textul rămas orice cuvânt (cu excepţia ultimului) să se termine cu aceeaşi literă cu care începe cuvântul următor, iar în final să se afişeze cuvintele din text rămase după eliminare, fiecare cuvânt fiind afişat pe câte o linie.

Pentru un text dat, se cere să se afişeze numărul de cuvinte din text, apoi numărul minim de cuvinte ce pot fi eliminate astfel încât în textul rămas orice cuvânt (cu excepţia ultimului) să se termine cu aceeaşi literă cu care începe cuvântul următor, iar în final să se afişeze cuvintele din text rămase după eliminare, fiecare cuvânt fiind afişat pe câte o linie.

Jocul nostru presupune parcurgerea unui tablou bidimensional cu două linii şi n coloane, format din 2•n celule pătratice. Fiecare celulă are asociată câte o valoare întreagă v care nu se modifică pe durata desfăşurării jocului. Jucătorii trebuie să găsească un drum de la celula de plecare la celula de sosire care respectă următoarele condiţii:

• celula de plecare este cea din linia 1 şi coloana 1, iar celula de sosire este cea din linia 2 şi coloana n.
• nu trece decât cel mult odată prin oricare celulă.
• deplasarea se poate face din celula curentă spre oricare altă celulă învecinată cu ea pe orizontală sau verticală.
• conţine cel mult k celule consecutive aflate pe aceeaşi linie.

Pentru un astfel de drum se calculează punctajul acestuia ca fiind egal cu suma valorilor asociate celulelor prin care trece drumul.

Cunoscând valorile asociate celulelor tabloului, scrieţi un program care determină punctajul maxim care poate fi obţinut în acest joc.

Constructorii angajaţi de faraonul Keops au terminat construirea piramidei în trepte mult visată. Măreaţa piramidă are n camere identice de formă cubică, numerotate de la 1 la n, dispuse pe m niveluri astfel:

• camera din vârful piramidei formează nivelul 1 şi are numărul 1;
• nivelul 2 al piramidei este format din următoarele 4 camere care în secţiune cu un plan paralel cu baza au aspectul unei matrice cu 2 linii şi 2 coloane; camerele de pe nivelul 2 sunt numerotate de la 2 la 5 în ordinea crescătoare a liniilor matricei, iar pe aceeaşi linie în ordinea crescătoare a coloanelor matricei;
  ………………..
• nivelul m al piramidei este format din m*m camere şi au, în secţiune cu un plan paralel cu baza, aspectul unei matrice cu m linii şi m coloane; camerele de pe nivelul m sunt numerotate în continuarea celor de pe nivelurile 1, 2,…, m-1, în ordinea crescătoare a liniilor matricei de secţiune, iar pe aceeaşi linie în ordinea crescătoare a coloanelor matricei. De exemplu, piramida din desenul de mai sus are n=30, m=4 iar camerele sunt numerotate şi dispuse pe niveluri astfel:

Nivelurile de camere sunt poziţionate astfel încât camerele de pe prima linie şi prima coloană a fiecărui nivel să se suprapună. Pentru exemplul dat, camerele 1, 2, 6 şi 15 sunt situate una sub alta, în această ordine.

Accesul în oricare din camerele piramidei, situate pe diferite niveluri, se realizează prin drumuri construite astfel:

• intrarea în piramidă se face doar prin camera din vârful ei, cea cu numărul 1;
• din camera cu numărul k de pe un drum se poate intra într-una din cele patru camere situate pe nivelul imediat următor al piramidei şi anume: camera situată sub cea cu numărul k sau una din cele trei camere vecine acesteia în secţiune (în direcţiile Est, Sud-Est, Sud, considerând secţiunile poziţionate ca în imaginile de mai sus). De exemplu, din camera cu numărul 10 se poate intra într-una din camerele cu numerele: 20, 21, 24 sau 25.

Faraonul priveşte cu mândrie şi tristeţe la frumoasa piramidă. Banii din visterie s-au împuţinat iar camerele piramidei trebuie finisate şi decorate. Scribul său favorit a refăcut toate calculele, a eliminat obiectele inutile şi a stabilit pentru fiecare cameră k un cost ck aferent finisării şi decorării ei (1≤k≤n).

Însă, suma totală necesară fiind încă mare, faraonul i-a cerut scribului să aleagă un drum, dintre cele construite, care să treacă prin toate nivelurile piramidei astfel încât suma s a tuturor costurilor aferente finisării şi decorării camerelor de pe acest drum să fie minimă. Deocamdată, doar aceste camere vor fi aranjate…

Scrieţi un program care să determine numărul m de niveluri ale piramidei, suma minimă s a tuturor costurilor aferente finisării şi decorării camerelor de pe un drum ce trece prin toate nivelurile piramidei, construit în modul descris în enunţ, precum şi un astfel de drum pentru care se obţine suma minimă, putând fi ales de scrib.

Se consideră un şir de biţi şi un număr natural K. Şirul se împarte în secvenţe astfel încât fiecare bit din şir să aparţină unei singure secvenţe şi fiecare secvenţă să aibă lungimea cel puţin 1 şi cel mult K. După împărţire, fiecare secvenţă de biţi se converteşte în baza 10, obţinându-se un şir de valori zecimale. De exemplu, pentru şirul de biţi 1001110111101010011 şi K = 4, se poate obţine 1 0011 101 111 0 1010 011, apoi în baza 10: 1, 3, 5, 7, 0, 10, 3. O altă împărţire poate fi 1 00 1 1 10 11 110 1010 011, adică 1, 0, 1, 1, 2, 3, 6, 10, 3.

Scrieţi un program care:

• determină valoarea maximă (în baza 10) care se poate obţine dintr-o secvenţă de cel mult K biţi
• împarte şirul iniţial în secvenţe de cel mult K biţi astfel încât şirul zecimal obţinut să conţină un subşir strict crescător de lungime maximă posibilă.

Avem o matrice triunghiulară cu n linii, cu elemente numere întregi. În această matrice putem construi un traseu după următoarea regulă:

• primul element al traseului este elementul a1,1
• dacă elementul ai,j aparţine traseului, atunci următorul element al traseului poate fi doar ai+1,j sau a_i+1,j+1, pentru orice 1≤j≤i<n.
• traseul se va codifica cu numerele de ordine ale coloanelor, parcurgând liniile de la 1 la n. Valoarea traseului este egală cu suma elementelor ce îl formează.
  Traseul evidenţiat în exemplul din dreapta are valoarea 5+4+6+5+4=24, şi se codifică cu 1,2,3,3,4.

Fie mulţimea tuturor traseelor de valoare maximă generate în ordine lexicografică și numerotate. Pentru exemplul de mai sus avem șase trasee de lungime maximă:

• traseul 1. 1 1 1 1 2 (5+2+7+6+4=24)
• traseul 2. 1 1 1 2 2 (5+2+7+6+4=24)
• traseul 3. 1 2 2 2 2 (5+4+5+6+4=24)
• traseul 4. 1 2 3 3 4 (5+4+6+5+4=24)
• traseul 5. 1 2 3 4 4 (5+4+6+5+4=24)
• traseul 6. 1 2 3 4 5 (5+4+6+5+4=24)

Cunoscând dimensiunea și elementele unei matrice triunghiulare, respectiv două numere naturale st şi dr (st≤dr), se cere să se determine:

1. Numărul total al traseelor de valoare maximă. În cazul în care această valoare depășește 2000000000, se va tipări valoarea 2000000001;
2. Traseele cu numerele de ordine st, st+1, … , dr.

După strălucita victorie de la Austerlitz împotriva coaliţiei ruso-austriece, împăratul Napoleon Bonaparte doreşte să recompenseze N generali care s-au remarcat în luptă. Pentru aceasta, el dispune de o sumă în franci de valoare S. La festivităţile dedicate victoriei, cei N generali vor fi aliniaţi în ordinea descrescătoare a meritelor lor pe câmpul de luptă şi împăratul îi va chema pentru înmânarea recompensei în această ordine.

Bonaparte doreşte să împartă întreaga sumă astfel încât generalul cel mai merituos să primească suma cea mai mare şi oricare alt general să primească o sumă cel mult egală cu a generalului care a fost premiat anterior. De asemenea, generalul cu cel mai mic premiu nu trebuie să primească mai puţin de F franci.

Determinaţi numărul de variante distincte de acordare a recompenselor de către împăratul Napoleon.

Matca cea tânără a decis să părăsească stupul şi să îşi facă propria familie de albine, lucru nu tocmai uşor. Ea, împreună cu albinele sale trebuie să meargă din floare în floare până la marginea plantaţiei. Plantaţia are formă dreptunghiulară cu N linii (numerotate de la 1 la N) şi M coloane (numerotate de la 1 la M). În fiecare punct este o floare. Florile sunt codificate cu 0 sau 1, cele codificate cu 0 putând fi ocupate doar de matcă, cele cu valoarea 1 doar de câte o albină. Roiul de albine pleacă de la marginea stângă a plantaţiei (coloana 1) şi trebuie să ajungă în marginea din dreapta (coloana M). La un pas, toate albinele (inclusiv matca) trebuie să se afle pe poziţii consecutive pe aceeaşi coloană. La pasul următor ele se pot deplasa doar pe coloana următoare, dar tot pe poziţii vecine (eventual îşi pot schimba ordinea). Efortul depus pentru deplasarea de pe o coloană pe alta este egal cu diferenţa dintre prima linie ocupată de un membru al roiului de albine (matca sau albină) la pasul anterior şi prima linie ocupată de un membru al roiului albine (matca sau albină) după mutare.

Determinaţi numărul maxim de membri ai roiului de albine (matcă + albine) care pot părăsi stupul pentru a traversa toată plantaţia în scopul formării unei noi familii. Determinaţi, de asemenea efortul total minim cu care matca poate traversa plantaţia cu numărul maxim de albine determinat.

Cunoscând dimensiunea m*n a tablei de şah, respectiv poziţia iniţială (l1,c1) şi poziţia finală (l2,c2) a traseului regelui, să se calculeze numărul drumurilor minime distincte în care regele poate parcurge drumul.

Se dau L şi C două numere naturale şi o matrice cu L linii şi C coloane având elementele numere întregi. Trebuie alese elemente care să respecte următoarele proprietăţi:

• de pe fiecare linie se alege o secvenţă de elemente aflate pe coloane cu indici consecutivi, începând cu elementul de pe prima coloană;
• pentru orice două linii consecutive, lungimile secvenţelor alese trebuie să difere prin 1 sau să fie egale;
• nu trebuie să existe 3 linii consecutive pentru care lungimile secvenţelor alese să fie egale, sau să fie în ordine strict crescătoare sau strict descrescătoare;

Se cere să se facă o alegere a secvenţelor de pe fiecare linie a matricei respectând restricţiile precizate, astfel încât însumând elementele acestora să se obţină suma maximă posibilă.