Lista de probleme 17

După ce a primit de la Simonet, profesorul său de studii sociale, tema pentru proiect, tânărului Trevor i-a venit ideea jocului “Pay it forward”. Pentru cei care nu știu acest joc, el constă în ajutarea de către Trevor a oamenilor aflați la ananghie. Aceștia la rândul lor vor ajuta alți oameni și așa mai departe. Fiecare participant (inclusiv Trevor) trebuie să realizeze câte k fapte bune prin care să ajute oamenii. Vârstnicii și tinerii își îndeplinesc în mod diferit această sarcină. Vârstnicii au nevoie de zv zile pentru a introduce în joc o altă persoană, iar tinerii au nevoie de zt zile. Astfel dacă un vârstnic, respectiv un tânăr, intră în joc în ziua i, el va introduce la rândul lui în joc prima persoană în ziua i+zv, respectiv în ziua i+zt tânărul, a doua persoană în ziua i+2*zv, respectiv în ziua i+2*zt tânărul și așa mai departe. Astfel numărul de persoane care participă la joc poate fi diferit în funcție de cum sunt alese persoanele vârstnice și cele tinere. Trevor dorește ca în joc să fie realizate în total cât mai multe fapte bune, dar fiecare participant să aducă în joc maximum (k+1)/2 tineri și maximum (k+1)/2 vârstnici. Participanții pot aduce mai puține persoane de un anumit tip, dar nu au voie să depășească numărul de (k+1)/2 persoane de același tip. Care este numărul fb de fapte bune care mai sunt de realizat, după trecerea a n zile, de către persoanele intrate deja în joc, astfel încât numărul total de fapte bune așteptate (și cele realizate și cele nerealizate) să fie maxim?

După ce au mers împreună prin lume, Păcală și Tândală au strâns o căruță plină de bănuți de aur, iar acum îi răstoarnă pe toți în curtea casei și îi împart în N grămezi. Păcală numără bănuții din fiecare grămadă și îi dictează lui Tândală N numere naturale pe care acesta trebuie să le scrie în ordine pe o tăbliță. După ore bune de muncă, Păcală constată că Tândală a scris pe un singur rând, în ordine, de la stânga la dreapta, toate numerele dictate de el, dar lipite unul de altul. Acum pe tăbliță e doar un șir lung de cifre. Ce să facă Păcală acum?

Cunoscând cele N numere naturale dictate de Păcală, scrieți un program care să determine:
1. numărul cifrelor scrise pe tăbliță de Tândală;
2. ce-a de-a K-a cifră de pe tăbliță, în ordine de la stânga la dreapta;
3. cel mai mare număr ce se poate forma cu exact P cifre alăturate de pe tăbliță, considerate în ordine de la stânga la dreapta.

Sindbad a descoperit un recipient care conține o poțiune magică și o inscripție care descrie cum se poate deschide poarta unui templu. Urmând instrucțiunile din inscripție, Sindbad a ajuns la un tunel acoperit cu dale pătrate, aliniate astfel încât formează linii și coloane. Tunelul are mai multe linii, iar pe fiecare linie sunt câte N dale. Dalele din tunel sunt numerotate începând cu 1, astfel încât, parcurgându-le linie cu linie și fiecare linie de la stânga la dreapta, se obține un șir strict crescător de numere naturale consecutive.
Sindbad se află la intrare, înaintea primei linii. Pentru a deschide poarta templului, el trebuie să ajungă pe dala numerotată cu P, călcând pe un număr minim de dale. Dacă există mai multe astfel de soluții, o va alege pe cea pentru care consumul total de picături de poțiune magică este minim.

Scrieți un program care citește valorile N și P și rezolvă următoarele cerințe:
1. afișează numărul minim de dale pe care trebuie să calce pentru a deschide poarta;
2. afișează numărul natural T, reprezentând numărul minim de picături de poțiune magică necesare pentru deschiderea porții.

Alex vrea să își usuce rufele pe balcon. El a spălat K tricouri și o șosetă. Uscătorul lui Alex are N niveluri, iar fiecare nivel are M locuri unde poate atârna câte un singur obiect de îmbrăcăminte. Alex usucă hainele într-un mod specific: începe prin a pune șoseta pe nivelul A, locul B, iar apoi aduce coșul de rufe cu cele K tricouri și le așază pe rând, mereu alegând o poziție liberă cât mai depărtată de locul unde a pus șoseta. Metrica pe care o găsește ca fiind cea mai potrivită când vine vorba de uscatul rufelor este distanța Manhattan, astfel încât distanța de la nivelul r1, locul c1 la nivelul r2, locul c2 are valoarea expresiei |r1 – r2| + |c1 - c2|. Aflați distanța dintre poziția unde a atârnat ultimul tricou și poziția unde se usucă șoseta.

Se dă un arbore cu N noduri, numerotate de la 1 la N. Arborele se va transforma astfel: la oricare etapă fiecare nod de gradul 1 diferit de rădăcină din arborele actual se înlocuiește cu un arbore identic cu cel dat inițial, iar la următoarea etapă procedeul se va relua pentru arborele obținut, formându-se astfel un arbore infinit. În imagini se prezintă un exemplu de arbore dat inițial, arborele obținut după prima etapă de prelungire a frunzelor și arborele obținut după două etape de prelungire a frunzelor. Să se determine câte noduri se află la distanță D de rădăcina arborelui infinit.

Se dă o matrice A cu N linii și M coloane, cu valori cuprinse între 1 și N∙M inclusiv, nu neapărat distincte. O operație constă în selectarea a două linii sau două coloane consecutive și interschimbarea acestora (swap). O matrice yin-yang este o matrice în care A[ i ] [ j ] ≥ A[ i ][ j – 1], pentru orice pereche (i, j) cu 1 ≤ i ≤ N și 2 ≤ j ≤ M și A[ i ][ j ] ≥ A[ i – 1][ j ], pentru orice pereche (i, j) cu 2 ≤ i ≤ N și 1 ≤ j ≤ M.

Să se determine numărul minim de operații necesare pentru a transforma matricea dată într-o matrice yin-yang.

Fie un graf neorientat cu N noduri și M muchii, care NU este conex. Să i se adauge grafului un număr minim de muchii, astfel încât acesta să devină conex. Fie extrai numărul de muchii nou-adăugate care sunt incidente cu nodul i, iar max_extra cea mai mare dintre valorile extra1, extra2,… , extraN. Mulțimea de muchii adăugate trebuie să respecte condiția ca valoarea max_extra să fie minimă.