Lista de probleme 9

N prieteni, numerotaţi de la 1 la N, beau bere fără alcool la o masă rotundă. Pentru fiecare prieten i se cunoaşte \( {C}_{i} \) – costul berii lui preferate. Din când în când, câte un prieten, fie el k, cumpără câte o bere pentru o secvenţă de prieteni aflaţi pe poziţii consecutive la masă, începand cu el, în sensul acelor de ceasornic. El este dispus să cheltuiască x bani şi doreşte să facă cinste la un număr maxim posibil de prieteni.

Se cere numărul de beri pe care le va cumpăra fiecare prieten k în limita sumei x de bani de care dispune. În caz că x este mai mare decât costul berilor pentru toţi prietenii de la masă, se vor achiziţiona maxim N beri.

Pentru un concurs de design de jocuri, Gigel vrea să construiască un joc. La joc participă n concurenţi numerotaţi de la 1 la n. Fiecare concurent are la dispoziţie câte un şir de m încăperi, numerotate de la 1 la m. Scopul jocului este de a găsi o comoară ascunsă în una din aceste încăperi. Fiecare încăpere conţine un cod, număr natural, fie egal cu 0, fie având cel puţin 2 cifre. Ultima cifră indică numărul de etape de penalizare, adică numărul de etape în care concurentul nu are voie să părăsească încăperea. Numărul obţinut prin eliminarea ultimei cifre a codului indică numărul încăperii în care se va deplasa acesta la următoarea etapă sau la expirarea penalizării.

Fiind dat numărul n de concurenţi, numărul m de încăperi alocate fiecărui concurent, şi codurile din cele n×m încăperi să se determine câştigătorul jocului, numărul încăperii în care a găsit comoara, numărul de etape parcurse până când câştigătorul găseşte comoara precum şi numărul de concurenţi eliminaţi din joc până la etapa respectivă (inclusiv).

Se consideră o matrice pătratică cu N linii şi N coloane ce conţine toate numerele naturale de la 1 la N*N.
Asupra matricei se definesc trei tipuri de operaţii codificate astfel:

• C i j – interschimbarea coloanelor i şi j ale matricei
• R i j – interschimbarea liniilor i şi j ale matricei
• E i j x y – interschimbarea elementului de pe linia i şi coloana j cu elementul de pe linia x şi coloana y.

Asupra matricei se efectuează un set de M astfel de operaţii.

Se cere să se determine numărul minim de aplicări complete ale acestui set de operaţii după care se ajunge din nou în starea iniţială. În cadrul setului operaţiile se efectuează mereu în aceeaşi ordine şi nu se poate sări peste o operaţie. Deoarece numărul acesta poate fi foarte mare se cere restul împărţirii sale la 13007.

Dată fiind o succesiune de îndoituri aplicată unei foi de dimensiune N x N, scrieţi un program care să determine înălţimea, lăţimea şi grosimea obiectului obţinut.

Să considerăm o secvenţă de n substanţe chimice \( s= s_{1}, s_{2},…,s_{n} \). Substanţele sunt numerotate distinct de la 1 la n şi fiecare substanţă apare în secvenţa s o singură dată. Determinaţi pentru o secvenţă dată de substanţe, dacă în urma reacţiilor ce se pot produce conform regulilor din enunţ rezultă o substanţă stabilă.

Miruna şi partenerul ei de aventură, Pikachu, sunt în faţa unei noi provocări. Cele două personaje au ajuns lângă un lanţ muntos format din N vârfuri aşezate în linie dreaptă unul după altul. Pentru fiecare vârf muntos se cunoaşte înălţimea lui. Folosindu-se de puterile sale extraordinare, Pikachu este capabil sa scadă sau să crească înălţimea unui vârf muntos cu o unitate într-o secundă. Din motive necunoscute muritorilor de rând, cei doi prieteni vor să obţină cel puţin K vârfuri montane consecutive care au aceeaşi înălţime, într-un timp cât mai scurt. Determinaţi timpul minim în care Pikachu poate îndeplini această sarcină.

Zăhărel şi Sică s-au gândit să se reinventeze din punct de vedere spiritual. În prima fază, vor să se mute în oraşul Sala. Oraşul Sala conţine N case (numerotate de la 1 la N) unite prin M străzi bidirecţionale de lungimi egale. Ei au la dispoziţie fonduri limitate şi pot să se mute doar într-un cartier mărginaş format din X case. Fiindcă sunt buni prieteni cei doi vor să se mute în două case distincte, cât mai apropiate între ele. Determinaţi distanţa minimă dintre două case distincte din cele X din cartier.

Dintr-o regretabilă eroare, redactorul Vasile a şters toate spaţiile din textul la care lucra. Textul este scris într-o limbă necunoscută, numai cu litere mici ale alfabetului englez. Vasile ştie că un cuvânt trebuie să conţină cel puţin o vocală şi că nu poate avea lungimea mai mare de 20 de litere. De asemenea, fiind un tip meticulos, el ştie că în text erau (înainte de ştergerea spaţiilor) exact N cuvinte. Vasile trebuie să restaureze textul, inserând spaţii între cuvinte. Cum există numeroase modalităţi de restaurare a textului, Vasile a hotărât să aleagă varianta în care literele sunt distribuite în cuvinte într-un mod cât mai armonios. Pentru a măsura armonia, Vasile a calculat suma pătratelor lungimilor cuvintelor. Textul este cu atât mai armonios, cu cât suma obţinută este mai mică. Dat fiind textul fără spaţii, să se determine câte posibilităţi de restaurare există (în total, indiferent de armonia lor), precum şi cea mai armonioasă modalitate de restaurare.

Într-o bibliotecă se află C dulapuri identice aşezate unul lângă altul pe peretele unei încăperi, dulapurile fiind numerotate de la stânga spre dreapta cu numerele naturale de la 1 la C. Fiecare dulap conţine 1000 de rafturi, situate vertical unul deasupra altuia, rafturile fiecărui dulap fiind numerotate de la 1 la 1000 de jos în sus.

Fiecare dulap este prevăzut cu o scară cu care se poate ajunge la orice raft. Dacă bibliotecara urcă scara unui anumit dulap D până la un anumit nivel k, ea va putea aduna orice carte de pe rafturile 1 până la k inclusiv, din dulapul D şi din dulapurile învecinate (dulapul D-1 şi dulapul D+1).

Cunoscând dulapurile şi rafturile de unde trebuie luate cărţi, bibliotecara doreşte să adune toate cărţile cerute, dar suma înălţimilor până la care trebuie să urce să fie minimă.