Lista de probleme 1030

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.

Se consideră șirul de litere mici ale alfabetului englez A[1], ..., A[N].

Fie succesiunea de caractere alăturate din șir A[x], A[x + 1], ..., A[y], unde 1 ≤ x ≤ y ≤ N, pe care o notăm cu A[x, y]. Pentru oricare literă mică a alfabetului englez l, definim range(l) ca fiind 0, dacă l apare cel mult o dată în A[x, y]. Altfel, valoarea range(l) este egală cu diferența dintre cea mai mare și cea mai mică poziție pe care litera l apare în A[x, y].
Șirul suport asociat lui A[x, y] este șirul de caractere minim lexicografic ce conține fiecare literă l de range(l) ori. Asupra șirului se efectuează două tipuri de operații:

• Actualizare: dându-se litera c și poziția poz, se înlocuiește A[poz] cu c.
• Generare: dându-se perechea x, y, se generează șirul suport al lui A[x, y].

• Dacă C = 1: determinați șirul suport minim lexicografic dintre cele obținute în urma tuturor operațiilor de generare.
• Dacă C = 2: pentru fiecare operație de generare dată, determinați numărul de anagrame distincte ale șirului suport obținut, modulo 1999999973.

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.

Privit din satelit, Golful Biscayne (Florida) este format din n × m celule pătratice, fiecare celulă fiind umplută fie cu pământ, fie cu apă. Celulele umplute cu pământ sunt grupate în insule: două celule umplute cu pământ fac parte din aceeași insulă dacă și numai dacă se poate ajunge de la una la cealaltă prin deplasare (în sus, jos, stânga sau dreapta) doar pe pământ.

Golful poate fi văzut, astfel, ca o matrice A cu n linii și m coloane (numerotate de la 1), unde A[i][j] = 1 dacă celula de pe linia i și coloana j este umplută cu pământ și A[i][j] = 0 dacă este umplută cu apă.

Spunem că o insulă se află la stânga unei coloane c dacă și numai dacă toate celulele ce intră în alcătuirea insulei sunt strict la stânga coloanei c, adică sunt situate pe coloane strict mai mici decât c. Analog, stabilim dacă o insulă se află la dreapta unei coloane c, respectiv deasupra sau dedesubtul unei linii l. De exemplu, în desenul de mai sus, insulele A, B și C sunt la stânga coloanei 7, insula E este la dreapta coloanei 7, iar insula D nu este nici la stânga, nici la dreapta coloanei 7. De asemenea, insulele A și B sunt deasupra liniei 3, iar insulele C, D și E sunt dedesubtul liniei 4. Mai mult, insulele C, D și E nu sunt nici deasupra, nici dedesubtul liniei 5.

Problema are trei cerințe, cerința de rezolvat fiind dată de T ∈ {1, 2, 3}.

• T = 1. Determinați numărul de celule din golf ce sunt umplute cu pământ.
• T = 2. Determinați numărul de insule din golf ce conțin un număr maxim de celule. Dacă nu există nicio insulă, atunci valoarea acestui număr este 0.
• T = 3. Se dau, în ordine, Q interogări, fiecare fiind descrisă printr-o literă și un număr natural
  nenul p. Determinați valoarea produsului a × b, știind că:
  • Dacă litera este C, atunci a reprezintă numărul de celule din toate insulele ce se află la stânga coloanei p (1 ≤ p ≤ m) și b numărul de celule din toate insulele ce se află la dreapta coloanei p.
  • Dacă litera este L, atunci a reprezintă numărul de celule din toate insulele ce se află deasupra liniei p (1 ≤ p ≤ n) și b numărul de celule din toate insulele ce se află dedesubtul liniei p.

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.

Andrei este managerul unei librării care dorește să mențină o evidență exactă a prețurilor cărților din inventar. Emanuel, administratorul librăriei, implementează planuri de marketing care implică modificări repetate ale prețurilor (operații de modificare de preț), iar deciziile sale se pot schimba ulterior. Pentru a maximiza profitul obținut în funcție de cerere, în fiecare zi, Emanuel efectuează o serie de operații (modificări, anulări și refaceri), iar la sfârșitul fiecărei zile, Andrei trebuie să vadă starea finală a prețurilor din librărie.

Alina, managerul unui lanț de magazine, este responsabilă de gestiunea tranzacțiilor bancare din cadrul acestora. Ea lucrează cu conturi bancare și cunoaște sumele de bani (soldul) existente în fiecare dintre acestea. Se cunosc N, numărul tranzacțiilor și N numere întregi nenule a[1], a[2], …, a[N], reprezentând, în această ordine, sumele de tranzacționat (un număr pozitiv indică o sumă care urmează a fi depusă, iar un număr negativ reprezintă o sumă care urmează a fi retrasă). După procesarea celor N tranzacții, ajutați-o pe Alina să determine:
1) numărul de conturi rămase active.
2) soldul maxim care se găsește într-un cont dintre cele rămase active.

Pentru a îmbunătăţi aptitudinile logico-matematice ale elevilor săi, profesorul Vasile a implementat un joc. Pe ecranul principal al jocului se afişează un şir de N scaune, numerotate de la stânga spre dreapta începând cu 1, pe fiecare scaun fiind așezat câte un copil. Fiecare copil poartă un tricou pe care este scris, de asemenea, câte un număr de la 1 la N. Numerele de pe tricouri sunt distincte și sunt scrise pe spate, deci nu sunt vizibile. Scopul jocului este de a descoperi numărul scris pe tricoul fiecărui copil. Pentru aceasta, pe ecran mai este afişat un triunghi de numere T, care ne dă informaţii ajutătoare. Triunghiul arată ca o matrice în care liniile sunt numerotate de sus în jos de la 1 la N, iar coloanele de la stânga la dreapta de la 1 la N. Numărul scris în triunghi pe linia i şi coloana j (1 ≤ i ≤ j ≤ n) reprezintă numărul scaunului pe care stă copilul având cel mai mic număr pe tricou dintre toţi copiii situaţi pe scaune cu numere cuprinse între i şi j (inclusiv i şi j). Observaţi că poziţiile din triunghi de pe linia i şi coloana j cu 1 ≤ j < i ≤ N nu sunt completate. Cunoscând numărul de copii şi triunghiul de numere:
1. determinați o soluţie posibilă; dacă există mai multe soluţii posibile se va afişa cea mai mică din punctul de vedere lexicografic;
2. determinați numărul de soluţii posibile.

RAU-Gigel își serbează ziua alături de colegii săi de la clubul de informatică și vrea să le împartă bomboane. El are un număr dat de bomboane și ar vrea să știe dacă îi ajung și, dacă da, în câte moduri le poate împărți. Dar nu își amintește câți colegi are la cerc, are însă o informație care ar putea să îl ajute.

În urma petrecerii de ziua lui RAU-Gigel, copiii au primit atâtea bomboane încât au câștigat o energie debordantă – așa că l-au provocat pe RAU-Gigel la un concurs de … numărat!

Acestora li se dă o matrice cu N linii și M coloane, în care fiecare element este un număr natural nenul. Obiectivul lor este să determine câte submatrice (sub-dreptunghiuri formate din linii și coloane contigue) conțin exact K valori distincte.