Lista de probleme 100

Fie un vector v sortat crescător cu N elemente naturale nenule distincte pe care nu le cunoaştem, dar pe care ne propunem să le determinăm. Având la dispoziţie acest vector v, cu ajutorul următorului algoritm de căutare binară putem răspunde la queryuri de forma: Dându-se un număr X şi un interval [a, b] se cere să se determine cel mai mic element mai mare decât X aflat în intervalul determinat de indicii a şi b, interval din vectorul v. Se cunosc paşii pe care algoritmul de cautare binară i-a urmat pentru diferite valori ale tripletului (X, a, b).
Dându-se N (lungimea vectorului), Q (numărul de query-uri apelate) şi cele Q query-uri, să se determine vectorul iniţial. Dacă există mai multe soluţii se va afişa soluţia minim lexicografică. Dacă nu există soluţie se va afişa valoarea -1.

Zizi îşi va petrece concediul în această vară într-o frumoasă staţiune de la Marea Neagră. Acolo va sta N zile. Zilele
sunt numerotate de la 1 la N. În fiecare dintre cele N zile de concediu, ea intenţionează să facă plajă un număr cât
mai mare de unităţi de timp. Va trebui să ţină seama totuşi de prognoza meteo, care este nefavorabilă în K dintre cele N zile, respectiv în zilele z[1], z[2], …, z[k]. În fiecare dintre aceste K zile va ploua sau va fi prea mult soare, iar Zizi va trebui să-şi limiteze timpii de plajă la cel mult t[1], t[2], …, t[k] unităţi de timp. De asemenea, din motive de confort fizic, Zizi doreşte ca diferenţa în valoare absolută a timpilor de plajă între oricare două zile consecutive să nu depăşească T.
Cunoscând zilele z[1], z[2], …, z[k] în care există limitările t[1], t[2], …, t[k] pentru timpul de plajă şi valoarea T, să se determine numărul maxim de unităţi de timp pe care Zizi le poate petrece la plajă într-o singură zi dintre cele N zile de concediu.

Stațiunea Xoni de pe insula Ixos are N magazine de înghețată, așezate unul lângă altul, pe aceeași parte a străzii pietonale. Acestea sunt numerotate cu valori naturale de la 1 la N , în ordinea așezării pe stradă.

Magazinele sunt deținute de K acționari (numerotați de la 1 la K ), fiecare dintre aceștia fiind proprietarul unor magazine numerotate consecutiv. Un magazin poate avea mai mulți acționari.

Odată cu venirea verii, începe și perioada concediilor, toți acționarii luându-și concediul împreună, timp de M zile. Înainte de a pleca în concediu, ei au discutat cu Transportel pentru a se ocupa de aprovizionarea cu înghețată a magazinelor lor. Acesta a decis, singur, să facă în fiecare dintre cele M zile aprovizionarea unor magazine, numerotate și acestea cu numere consecutive.

Determinați, pentru fiecare acționar numărul de magazine deținute de către acesta care nu au fost aprovizionate cu înghețată în nicio zi din concediu.

Împăratul cel bătrân vrea să împartă sacii cu galbeni din vistieria palatului celor K feciori ai săi, numerotați de la 1 la K în ordinea vârstei. Feciorul cu numărul 1 este cel mai mare, iar mezinul are numărul K. În vistierie sunt N saci plini cu galbeni, așezați în linie, atât de grei încât nu li se poate schimba ordinea, iar pe fiecare sac este scris numărul de galbeni pe care îi conține. Împăratul îl cheamă pe unul dintre feciori și îi spune: “Fiule, a ta este averea primilor x1 saci!”. Feciorul ia sacii și pleacă fericit. Apoi, împăratul cheamă alt fecior și îi spune: “Fiule, a ta este averea primilor x2 saci dintre cei rămași!”. Și așa mai departe, până ajunge la ultimul fecior chemat, căruia îi dă toți sacii rămași.
El nu are o ordine anume în care își cheamă feciorii dar are grijă să cheme fiecare fecior exact o dată. Totodată, pentru a evita certurile între ei, este atent ca fiecare fecior să primească cel puțin un sac cu galbeni, dar să NU primească în total mai mulți galbeni ca un frate mai mare decât el. Cel mai mic dintre feciorii împăratului este și cel mai viteaz, așa că împăratul ar vrea să îi dea lui o sumă de bani cât mai mare, fără a-i supăra pe ceilalți feciori ai săi. Cum ar putea împărți împăratul sacii?

Un număr natural n se numește putere dacă există două numere naturale a, b, a ≥ 1, b ≥ 2 astfel încât \(n = a^b\). De exemplu, numerele 32 , 169 , 1 sunt puteri (\(32 = 2^5\) , \(169 = 13^2\) , \(1 = 1^2\) ), iar 72 , 2000 și 31 nu sunt puteri.
Se citesc numerele naturale N , M și un șir de N numere naturale \(x_1, x_2, …, x_N\) din intervalul [1,M].

Pentru fiecare din cele N numere \(x_i\) determinați câte un număr natural \(r_i\) din intervalul [1,M], cu proprietatea că \(r_i\) este o putere și pentru orice altă putere p din intervalul [1,M] este îndeplinită condiția \(|x_i – r_i| ≤ |x_i – p|\), unde |x| reprezintă valoarea absolută a lui x (modulul).
Dacă există două puteri egal depărtate de \(x_i\) se va alege puterea cea mai mică. De exemplu pentru numărul 26, dintre puterile 25 și 27 va fi ales numărul 25.

Privită din spațiu, harta insulei din povestea noastră are forma unui caroiaj pătratic cu L linii și L coloane. Liniile și coloanele sunt numerotate de la 1 la L. În fiecare dintre cele L*L celule se află câte un far. Inițial cel de la poziția 1,1 este aprins și toate respectă regula: orice far are farurile vecine (pe linie și coloană, deci maximum 4) în starea opusă față de starea sa. În urma unei furtuni, s-au întâmplat lucruri ciudate: fulgerele au lovit unul după altul și au afectat starea unor faruri. Sunt trei tipuri de fulgere. Prin schimbarea stării unui far înțelegem că acesta se aprinde dacă este stins și se stinge dacă este aprins.
Se dau date despre fulgere, în ordinea în care acestea acționează. Se cere ca la finalul furtunii să se indice care este starea anumitor faruri, aflate la coordonate precizate de pe insulă.

Pasionat de informatică și de puzzle-uri, Dorel a construit o matrice A de dimensiunea N × M lipind mai multe piese dreptunghiulare de diferite dimensiuni. Fiecare piesă este compusă din elemente de dimensiunea 1 × 1 și rețin o aceeași valoare. Matricea rezultată nu are spații libere, iar piesele din care este compusă nu se suprapun. Nu există două piese cu aceeași valoare.
Deși inițial părea că acest design este unul inedit, nu a durat mult până când Dorel s-a plictisit. Astfel, acum el dorește să “upgradeze” matricea construită. Dorel alege o submatrice delimitată de coordonatele (x1,y1) – colțul stânga-sus, (x2,y2) – colțul dreapta-jos (1 ≤ x1 ≤ x2 ≤ N, 1 ≤ y1 ≤ y2 ≤ M), unde crește toate valorile elementelor submatricei cu valoarea V.
Dorel efectuează în ordine Q operații de upgrade, operații numerotate de la 1 la Q. La finalizarea celor Q operații de upgrade, toate elementele din matrice au valoarea mai mare sau egală cu K. După o operație de upgrade, structura inițială a matricei se modifică.
Cum priceperea lui Dorel este proverbială, trebuie să îl ajutați în rezolvarea următoarelor cerințe:
1) determinarea coordonatelor piesei cu număr maxim de elemente înainte ca Dorel să efectueze operațiile de upgrade;
2) determinarea numărului minim de operații de upgrade după care toate elementele matricei au valoarea mai mare sau egală cu K.

În grădina lui Cosmin se află un măr cu număr nelimitat de mere. Cei N prieteni ai lui Cosmin, numerotați de la 1 la N, vor culege mere timp de T zile, după următoarea regulă:
În dimineața zilei Ti, prietenii lui Cosmin vor forma o coadă la intrarea în grădina, începând cu prietenul Xi. Așadar, coada va arăta sub forma Xi, Xi+1, …, XN, X1, …, Xi-1. În acea zi se vor culege Yi mere. Fiecare prieten Xi va intra în grădină, va culege un măr și se va întoarce în coadă.
În ziua T + 1, Cosmin alege aleatoriu K prieteni (Q1, …, Qk) și dorește să afle câte mere a cules fiecare. Scrieţi un program care să găsească numărul de mere culese de fiecare dintre cei K prieteni selectați de Cosmin.

După o zi plină, trei băieți se joacă cu numere. În fiecare seară, unul dintre ei alege un număr x, iar altul un număr y mai mare sau egal cu x. Al treilea propune ceva mai interesant. Astfel, el alege să le spună aproape instantaneu suma pătratelor perfecte de la x și y. Voi trebuie să rezolvați ceva asemănător, doar că știți numai ce zice primul și ultimul băiat. Pentru a-i verifica dacă greșesc la calcule, în schimb, trebuie să găsiți numărul pe care l-ar putea spune al doilea. Să se calculeze pentru fiecare întrebare p minimum, pentru care relația este satisfăcută.

Se dă o instalație de N * M lumini. Fiecare lumină este dată prin culoare, în format RGB. Astfel, un element din matrice poate fi considerat un triplet (xR , xG , xB). Fiecare valoare este de la 0 la 255.
1) Câte perechi există în matrice, pentru care conexiunea lor ar determina culoarea negru?
2) Pentru o astfel de instalație dată, care este numărul maxim P, pentru care instalația nu se blochează?