Lista de probleme 1033

Dealul Bucium este cunoscut pentru tradiția de sute de ani a cultivării viței de vie. Acolo au fost plantați demult butuci de vie de soi nobil și de soi hibrid, pe un teren de formă dreptunghiulară. Din păcate, în anii ploioși, via este atacată de o boală fungică numită plasmopara, care afectează doar soiurile hibride. În fiecare nouă zi ploioasă, plasmopara atacă butucii învecinați (la nord, est, sud și vest) cu butuci deja infectați. Butucii atacați în prima zi ploioasă sunt cei din colțurile terenului, fiind cei mai expuși. Cunoscând numărul de rânduri de viță de vie și numărul de butuci de pe fiecare rând, cunoscând numărul de zile ploioase și dispunerea soiurilor pe teren, să se determine:
1. numărul butucilor de soi hibrid care au rămas neafectați de plasmopara
2. ziua în care au fost afectați cei mai mulți butuci (dacă niciun butuc nu a fost afectat, rezultatul va fi 0; dacă sunt mai multe zile cu număr maxim de butuci afectați, se va determina prima dintre acestea).

A devenit o obișnuință ca orice competiție să aibă un număr de sponsori. De exemplu, JBOI 2022, Balcaniada de Informatică pentru juniori, desfășurată în România, la Botoșani, a beneficiat de sprijinul a șapte importanți sponsori. Lista acestor sponsori este publicată în orice material publicitar care se referă la competiția respectivă. Și competiția noastră OMI 2025 beneficiază de sprijinul a N sponsori. Parcurgând lista de sponsori, am constat că, selectând anumiți sponsori din listă și aranjându-i într-o anumită ordine, primele litere din numele sponsorilor selectați formează cuvintele “OLIMPIADADE”, iar ultimele litere cuvântul “INFORMATICA”. Scrieți un program care să determine numărul de posibilități de selectare din lista de sponsori a acelora care respectă această proprietate, precum și soluția minimă lexicografic.

Echipa de fotbal Liverpool se antrenează intens pentru a câștiga campionatul, iar antrenorul Arne Slot, urmărește pasele jucătorilor în timpul antrenamentelor. Fiecare pasă este codificată astfel:

• P: pasă precisă, executată corect;
• G: pasă greșită, executată incorect.

Antrenorul le oferă jucătorilor șansa să corecteze cel mult două pase greșite, transformându-le în pase precise. Ajută-l pe Arne Slot să determine, dintr-un șir de N pase:
1. Cea mai lungă secvență continuă de pase precise care se poate obține după corectarea a cel mult două pase greșite.
2. Indicele de început al acestei secvențe (începând de la 1).
Să se scrie un program care determină și afișează lungimea maximă a unei secvențe de pase precise, precum și indicele de început al acestei secvențe. Lungimea celei mai lungi pase se stabilește după corectarea a cel mult două pase greșite.

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.