Lista de probleme 160

Dându-se un vector cu elemente întregi, care este numărul minim de iterații ale unui algoritm dat astfel încât să sorteze vectorul descrescător?

După ce Le Quack și-a pierdut toți banii dați de mama lui să cumpere pâine la Blackjack, acesta a decis să își
creeze propriul joc de cărți unde își poate bate prietenii și să câștige banii înapoi.

Ana şi Bogdan au inventat un nou joc, pe care l-au denumit Strips. Este un joc de strategie, dar şi de antrenare a memoriei, deoarece se joacă pe o tablă care nu este vizibilă pentru cei doi jucători în timpul jocului.
Scrieţi un program care citeşte lungimea tablei de joc, numărul de benzi colorate pe care le are fiecare jucător la începutul jocului, lungimea benzilor, precum şi poziţiile specificate de jucători pe parcursul jocului şi rezolvă următoarele două cerinţe:
- determină numărul de puncte de penalizare pentru fiecare dintre cei doi jucători;
- determină pentru fiecare jucător care este lungimea maximă a unei zone de pe tabla de joc colorată în culoarea sa la sfârşitul jocului.

Se dau N triplete de numere naturale (ai, bi, ci), unde ai ≠ 0 și 1 ≤ i ≤ N, fiecare reprezentând câte un număr rațional qi egal cu: $\frac{(-1{)}^{a_i}{b}_i}{c_i}$. Găsiți un subșir nevid al șirului q1, q2, …, qN al cărui produs al valorilor să fie maxim posibil.

Ultimul sezon rece a fost unul cu multa zăpadă căzută în zona montană, prin urmare magazinul de articole sportive din stațiunea de schi Semenic a avut vânzări mari, mai ales de clăpari (bocanci speciali pentru schiat). Acum fiind sfârșit de sezon, angajații magazinului constată că le-au rămas N cutii goale în care au fost ambalate perechile de clăpari vândute. Aceste cutii au forma unui paralelipiped dreptunghic la care fața superioară constituie capacul. Cunoscând N (numărul de cutii din magazin), ordinea în care cutiile sunt așezate în turn, iar pentru fiecare cutie latura capacului, înălțimea cutiei și dacă are capac sau, în cazul în care capacul lipsește, dacă cutia este așezată cu golul în sus sau cu golul în jos determinați:

• înălțimea turnului astfel format;
• numărul de cutii ale căror fețe laterale sunt vizibile dacă se privește turnul din lateral.

Pasionați de geografie, Alex și Răzvan joacă online Geoguessr. Harta lumii este alcătuită din N locații numerotate de la 1 la N, fiecare desemnând un punct în plan de coordonate (X[i], Y[i]). Alex a studiat atent toate cele N locații și a determinat o listă de L caracteristici de interes pentru locațiile date, numerotate de la 1 la L. De exemplu, caracteristica 1 ar putea fi “se află respectiva locație în Europa?”, iar caracteristica 2 ar putea fi “se vorbește limba spaniolă în locația respectivă?”, și așa mai departe.
Se dă un număr C ∈ {1, 2}. Pentru C = 1 să se afișeze răspunsul la prima întrebare a lui Alex pentru fiecare din cele Q runde. Pentru C = 2 să se afișeze răspunsul la a doua întrebare a lui Alex pentru fiecare din cele Q runde.

Giovani, sătul să piardă atât de mult la șah mutând pionii din fața regelui, incearcă să se orienteze spre alte activități și se înscrie la concursul anual de alergare dintre satul său natal, Păpucești și satul rival, Băbana. Competiția constă în a alerga cea mai mare distanță într-un anumit timp T fixat, cronometrat de comisia sătenilor. Pentru a face asta, comisia sătenilor dispune de un cronometru care pornește de la T. Odată activat, cronometrul va scădea cu câte o unitate de timp. Considerăm că la fiecare decrementare a cronometrului Giovani parcurge o unitate de lungime. Cum nu este nici un mare sportiv, Giovani îi cere ajutorul prietenului său, hackerul Cosminel. Cosminel îi spune că poate opri cronometrul comisiei, dar doar la anumite intervale de timp [li, ri], nu neapărat disjuncte, pentru a nu ridica suspiciuni. Afișați distanța cea mai mare pe care o poate parcurge Giovani până când cronometrul ajunge la 0 considerând că acesta poate trage de timp până la orice moment de pornire al cronometrului (număr natural) și că timpul începe de la momentul 1.

La începutul anului 2023, Gosu și-a creat o listă de rezoluții. Printre cele mai importante lucruri pe care Gosu își dorește să le realizeze anul acesta se numără cititul a N cărți pe care le are pe raftul bibliotecii. Fiecare carte are asociată un scor acordat de un critic, număr întreg strict pozitiv. Fiind o persoană analitică și realistă, Gosu își imaginează M scenarii de forma “După primele q cărți citite, care va fi suma maximă a scorurilor acestora, după un număr nelimitat de interschimbări între cărți din genul literar p?”.
Acestea sunt situații ipotetice, deci ordinea cărților pe raft nu este modificată în realitate pe parcursul interogărilor. Aflați răspunsurile în cazul acestor situații, reprezentate prin interogări independente de forma (p, q).

Se consideră o curte de dimensiuni $n\times m$. Curtea trebuie pavată cu dale identice de dimensiuni $a\times b$, unde $a$ și $b$ sunt numere întregi. O dală costă $\mathrm{\$}1$, iar bugetul nostru este de $\mathrm{\$}B$. Câte perechi $(a,b)$ există, astfel încât putem pava curtea cu dale de dimensiuni $a\times b$ și costul total al dalelor necesare nu depășește $\mathrm{\$}B$?

Chris a scris pe un caiet foarte multe numere de două sau trei cifre, toate divizibile cu 7. Interesant este că aceste numere conțineau doar cifrele 1, 2 sau 4. Mădălina a făcut curățenie în casă și a aruncat caietul. Acum Chris este foarte supărat că și-a pierdut numerele. Ca să îl înveselească, Mădălina i-a spus lui Chris: “Numerele tale conțineau exact U cifre de 1, D cifre de 2 și P cifre de 4”. Bucuros, Chris a venit la concurenții de la ONIGim și i-a rugat să îi regăsească numerele. Experți în programare, concurenții s-au apucat de treabă, dar imediat și-au dat seama că este posibil să existe mai multe moduri de a reconstitui numerele. Din fericire Chris se mulțumește cu oricare reconstituire și a promis 100 de puncte pentru fiecare concurent care îi va oferi o soluție validă. Cunoscând cele trei numere U, D și P cu semnificația din enunț, să se determine numere de două sau trei cifre, divizibile cu 7 astfel încât în numerele determinate să se regăsească exact U cifre de 1, D cifre de 2 și P cifre de 4.