Lista de probleme 215

Se dă o matrice cu 2 linii si n coloane care are k celule ocupate. Se dau q interogări de forma (x1, y1, x2, y2), cu următoarea semnificație: dacă se ocupă două celule libere distincte ale matricii inițiale, (x1, y1) și (x2, y2), se poate pava complet matricea cu piese de domino de dimensiuni 2 x 1 și 1 x 2? După efectuarea unei interogări celulele ocupate asociate acesteia vor deveni din nou libere (modificările aduse matricei nu persistă între interogări). Să se determine, pentru fiecare interogare, dacă este posibil ca matricea să fie pavată complet cu piese de domino de dimensiuni 2 x 1 și 1 x 2.

Profesorul de informatică trebuie să corecteze tezele a m elevi. Elevii au avut de rezolvat n probleme în teză, numerotate de la 1 la n. Fiecare elev a rezolvat toate problemele, deci profesorul are de corectat în total m x n probleme. La începerea corectării fiecărei teze, trebuie identificat numele elevului, proces care durează exact p secunde de fiecare dată, chiar dacă se revine la aceeași teză de mai multe ori.
După începerea corectării unei teze, căutarea fiecărei probleme durează k secunde. Corectarea primei probleme din submulțimea aleasă durează t[1] secunde, corectarea celei de-a doua probleme durează t[2] secunde ș.a.m.d. Se garantează că t[1] < t[2] < ... < t[n]. De fiecare dată când se revine la o anumită teză și se reîncepe corectarea ei cu o altă submulțime de probleme, corectarea primei probleme din submulțime va dura din nou t[1] secunde.
Să se determine timpul minim în care pot fi corectate cele m lucrări.

Considerăm numerele naturale N, X, Y, M[1], M[2], ..., M[N]. Șirul de numere naturale A[1], A[2], ..., A[N] este numit bun dacă următoarele condiții sunt satisfăcute simultan:

• A[1] OR A[2] OR ... OR A[N] = X, unde OR reprezintă operația sau pe biți.
• A[1] XOR A[2] XOR ... XOR A[N] = Y, unde XOR reprezintă operația sau exclusiv pe biți.
• A[i] AND M[i] = M[i], pentru 1 ≤ i ≤ N, unde AND reprezintă operația și pe biți.

Se dau N, X, Y și M[1], M[2], ..., M[N], cu semnificația din enunț. Să se determine dacă există șiruri bune, respectiv să se determine numărul de șiruri bune, modulo 1.000.000.007.

Fie a = (a[1], a[2], ..., a[n]) un șir de n numere întregi. Pentru fiecare k ∈ {1,2, ...,n}, definim min[k] = min{a[1], a[2], ... ,a[k]} și max[k] = max{a[1], a[2], ...,a[k]}. Astfel, asociem șirului a un alt șir de intervale închise minmax = ([min[1], max[1]], [min[2], max[2]], ..., [min[n], max[n]]). Vom spune că șirul a este un șir cromatic dacă și numai dacă elementele șirului minmax sunt distincte două câte două, adică nu există două intervale identice în șir. Dându-se un șir a, nu neapărat cromatic, să se determine:

• Numărul de șiruri cromatice NSC ce se pot forma prin rearanjarea elementelor șirului a. Întrucât acest număr poate fi foarte mare, se cere NSC modulo 1.000.000.007.
• Știind că șirul a este cromatic, să se determine poziția p ∈ {1, 2, ..., NSC} a șirului a în lista ordonată lexicografic a tuturor permutărilor cromatice ale lui a.
• Dat fiind q ∈ {1, 2, ..., NSC}, să se determine cel de-al q-lea șir cromatic în ordine lexicografică ce se poate obține prin rearanjarea elementelor șirului a.

Te-ai decis să ieși la o plimbare cu Opelozaurul pe un traseu care conține, la fiecare kilometru, un indicator cu numerele naturale din intervalul [1, N], în ordine crescătoare. Îți începi traseul în dreptul indicatorului cu numărul 1 și îl termini la indicatorul cu numărul N.

În mod normal, reușești să parcurgi orice kilometru cu mașina în 100 de secunde, dar, înainte să începi cursa, drumul a fost afectat de precipitații.

Prima dată a fost afectat de ninsori, fiecare ninsoare fiind descrisă printr-un triplet L R k, care arată că ninsoarea a afectat drumul în intervalul delimitat de indicatoarele L și R, iar acum, în acel interval, numărul de secunde necesare pentru a parcurge un kilometru crește cu k, indiferent de valoarea lui precedentă.

După ninsori, drumul este afectat de ploi, care sunt descrise și ele prin triplete L R k și limitează timpul în care mașina poate să parcurgă un kilometru în intervalul delimitat de indicatoarele L și R la k secunde.

Se dau Q numere întregi p din intervalul [1, N], iar pentru fiecare trebuie să determini numărul de secunde necesare să ajungi în dreptul panoului p.