Lista de probleme 14

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.

Se dă un șir cu N elemente ce conține numerele naturale de la 1 la K, în această ordine, acestea putând fi separate de elemente egale cu 0. De exemplu, pentru N = 9, șirul poate fi 0, 1, 2, 3, 0, 0, 4, 0, 5. Acest șir poate fi completat succesiv cu câte un element după următoarea regulă: dacă printre ultimele N elemente din șir se află un număr impar de elemente nenule, atunci elementul care se adaugă este succesorul celui mai mare element nenul din șir, în caz contrar se va adăuga elementul 0. Pentru exemplul anterior, după adăugarea a încă 4 elemente, șirul va deveni 0, 1, 2, 3, 0, 0, 4, 0, 5, 6, 0, 7, 8. Să se răspundă la Q întrebări de forma: pentru două numere date l și r, care este valoarea sumei elementelor din șir de la indicele l la indicele r, inclusiv acestea?

Împăratul Tiberius Claudius Caesar Augustus Germanicus, pasionat de luptele de gladiatori, a decis să organizeze cele mai mari jocuri care s-au organizat vreodată în Roma Antică. Pentru a măsura cât de spectaculoase sunt jocurile, împăratul a inventat un număr, numit “coeficientul de entuziasm”. Acest număr este egal cu 0 înainte să înceapă jocurile. În urma unei bătălii coeficientul de entuziasm crește cu diferența dintre nivelul de faimă al celor doi gladiatori. Ajutați-l pe Împăratul Tiberius și spuneți-i care este cel mai mare coeficient de entuziasm pe care îl poate obține atunci când se termină jocurile.

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).

Rapunzel, plictisită de modul în care arată castelul ei, doreşte să facă nişte modificări. Astfel, ea a comandat un nou mozaic pentru a îl pune la intrare. Meşterii palatului, ştiind cât de nehotărâtă este prinţesa, au decis să vină cu cât mai multe modele posibile. Mozaicul comandat este unul simplu, alcătuit din două benzi suprapuse de lungime N. Pentru a-l realiza, meşterii dispun de un număr infinit de plăcuţe dreptunghiulare cu lungimi variabile si lăţimi egale cu lăţimea unei benzi. Oricare două plăcuţe de lungimi diferite au şi modele diferite. Pentru a nu încărca prea mult mozaicul, o bandă o să conţină acelaşi model de plăcuţă. Deoarece materialele sunt scumpe, meşterii doresc să folosească integral fiecare plăcuţă, fără sa depăseaşcă lungimea mozaicului.

Înainte să se apuce de treabă, meşterii doresc să ştie lungimea plăcuţelor ce ar putea fi utilizate în crearea mozaicului.
Să se determine numărul de modele pe care prinţesa o să le primească de la meşteri.

Dorel este pasionat de studiul pătratelor perfecte. El doreşte să afle răspunsul la Q cerinţe de forma: dacă se dau numerele naturale l, r, a, b, cu l ≤ r, să se afle câte numere naturale x cuprinse între l şi r (inclusiv acestea) au proprietatea că x+a şi x+b sunt simultan pătrate perfecte.

Fie un șir de caractere S format din litere mici ale alfabetului englez, indexat de la 0. Aflați pentru fiecare i ≥ 2 cel mai mare l pentru care există 0 < j < i − l + 1 unde stringurile \( [{s}_{0}{s}_{1}…{s}_{l-1}] \), \( [{s}_{j}{s}_{j+1}…{s}_{j+l-1}] \) și \( [{s}_{i-l+1}{s}_{i-l+2}…{s}_{i}] \) sunt egale. Dacă nu există un astfel de l, afișați valoarea 0.

Să considerăm un calculator cuantic cu N qubiți setați inițial la |q1⟩|q2⟩..|qN⟩. Asupra acestor qubiți se poate efectua un singur tip de operații: se inversează toți qubiții (|0⟩ devine |1⟩ și viceversa) dintr-o subsecvență (qubiți aflați pe poziții consecutive). Aflați numărul minim de operații necesare pentru a seta toți qubiții la |1⟩ în situațiile:
1. Operațiile se pot efectua asupra subsecvențelor de orice lungime
2. Operațiile se pot efectua doar asupra subsecvențelor de lungime K

Fie un șir de caractere S format din litere mici ale alfabetului englez, indexat de la 1. Trebuie să răspundeți la Q query-uri de forma x, y – calculați câte inversiuni se află în intervalul [x, y]. O inversiune este o pereche de indici (i, j), 1 ≤ i < j ≤ N, pentru care este adevărată relația Si > Sj.

Satul Binăreni se află în pericol în urma incendiilor provocate în ultima lună. Acesta este reprezentat printr-o matrice binară cu N linii și M coloane. Toate celulele care au luat foc sunt reprezentate prin valoarea 0. Toate celulele în care nu este produs un incendiu, reprezentate prin valori de 1, conțin, inițial, câte o casă a unui sătean. Gosu, cel mai renumit pompier din sat, își dorește să salveze toate casele care nu se află în celule "safe", folosindu-și superputerea: acesta poate stinge o singură dată focul din toate celulele care au luat foc pe o linie x și toate celulele care au luat foc pe o coloană y, plasându-se la intersecția acestora, în celula (x, y). Acesta se poate plasa atât pe o celulă cu incendiu, cât și pe o celulă care conține o casă. Având în vedere că Gosu își poate folosi superputerea o singură dată, aflați toate perechile de coordonate (x, y) posibile pe care se poate plasa acesta, astfel încât să salveze toate casele care sunt în pericol.