Lista de probleme 6

Dan este un mare pasionat al fructelor, printre preferatele sale fiind strugurii şi pepenii. Însă recent şi-a descoperit și pasiunea pentru legume, în special pentru roşii, dar mai ales roşiile mici. Spre norocul lui, grădina bunicului este plină de roşii. Grădina are forma unei matrice cu N linii și M coloane cu elemente numere naturale, nu neapărat distincte, unde fiecare element din matrice reprezintă dimensiunea unei roşii. Matricea are proprietatea că oricare coloană are valorile ordonate crescător de sus în jos, adică de la prima spre ultima linie. Bunicul său îi cere să rezolve Q sarcini. Pentru fiecare sarcină, Dan primeşte un număr natural x şi trebuie să găsească o submatrice de arie maximă care începe de pe linia 1 a matricei care reprezintă grădina şi are toate elementele mai mici sau egale decât x. Pentru determinarea submatricei cerute, Dan are voie să mute toate valorile unei coloane în fața oricărei alte coloane. De asemenea, îi este permis să facă oricâte mutări de tipul acesta.
Să se calculeze aria maximă a unei submatrice care respectă specificațiile din enunț, pentru fiecare din cele Q sarcini date de către bunic.

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.

Se dă o matrice A cu N linii și M coloane cu elemente numere naturale nu neapărat distincte. Pentru o submatrice definim mex-ul acesteia ca fiind cea mai mică valoare naturală nenulă care nu apare în aceasta.
Să se calculeze produsul mex-urilor tuturor submatricelor având K linii și L coloane ale matricei A.

Se consideră următoarea structură de date. În vârful structurii se găsește fracția 1/1. Din fiecare vârf în care se găsește fracția p/q se formează alte două fracții trasând câte două segmente de dreaptă astfel: către stânga fracția p/(p+q) și către dreapta fracția (p+q)/q.
Cunoscând numărătorul, respectiv numitorul a două fracții ireductibile diferite din structură, determinați numărul minim de segmente de dreaptă cu care putem conecta în structura dată, cele două fracții.

În matematică factorialul unui număr natural nenul K este notat cu K! și este egal cu produsul numerelor naturale nenule mai mici sau egale cu K.
Orice număr natural N poate fi descompus cu ajutorul numerelor factoriale astfel:
N = 1! • f[1] + 2! • f[2] + 3! • f[3] + ... + m! • f[m]
unde coeficienții f[i], cu 1 ≤ i ≤ m sunt numere naturale și în plus f[m] ≠ 0.
Dintre toate aceste descompuneri posibile există o singură descompunere, numită descompunere în bază factorială care respectă suplimentar condițiile 0 ≤ f[i] ≤ i, cu 1 ≤ i < m și 0 < f[m] ≤ m.
1. Să se determine descompunerea în bază factorială a unui număr natural X dat.
2. Cunoscând o descompunere oarecare a unui număr natural Y să se determine descompunerea în bază factorială a acestuia.