Lista de probleme 3

Se consideră matricea 𝑇 cu 𝑛 linii (numerotate de la 1 la 𝑛) și 𝑚 coloane (numerotate de la 1 la 𝑚) ce conține numere întregi.

O submatrice a matricei 𝑇 este definită prin linia și coloana colțului stânga-sus (𝑥1, 𝑦1), respectiv linia și coloana colțului dreapta-jos (𝑥2, 𝑦2), cu 1 ≤ 𝑥1 ≤ 𝑥2 ≤ 𝑛 și 1 ≤ 𝑦1 ≤ 𝑦2 ≤ 𝑚 și conține toate elementele de pe pozițiile (𝑥, 𝑦) ale matricei pentru care 𝑥1 ≤ 𝑥 ≤ 𝑥2 și 𝑦1 ≤ 𝑦 ≤ 𝑦2. În particular, submatricea cu colțul stânga-sus în (1, 1) și colțul dreapta-jos în (𝑛,𝑚) este identică cu matricea 𝑇.

Pentru fiecare linie a unei submatrice date, se calculează suma pe linie prin adunarea elementelor aflate pe aceasta. Sumele obținute pentru fiecare dintre liniile acestei submatrice formează termenii unui șir, numit șirul 𝑆 al sumelor pe linii. Spunem că submatricea este aprogressive dacă 𝑥1 < 𝑥2 și 𝑦1 < 𝑦2 și șirul 𝑆 al sumelor pe linii poate fi rearanjat pentru a forma, cu toți termenii săi, o progresie aritmetică de rație nenulă 𝑟.

Forma comprimată a unei submatrice 𝑅 cu colțul stânga-sus (𝑥1, 𝑦1) și colțul dreapta jos (𝑥2, 𝑦2) se notează cu C(𝑅) și se definește astfel:

• dacă 𝑥1 = 𝑥2 (este o submatrice linie) sau dacă 𝑦1 = 𝑦2 (este o submatrice coloană) atunci forma sa comprimată este C(𝑅)= (𝑥1, 𝑦1, 𝑥2, 𝑦2, 0). În caz contrar,
• dacă 𝑅 este aprogressive, forma sa comprimată este C(𝑅)= (𝑥1, 𝑦1, 𝑥2, 𝑦2, 𝑟). În caz contrar,
• se împarte 𝑅 în 4 submatrice 𝐴, 𝐵, 𝐶, 𝐷 cu mulțimi disjuncte de elemente după cum este ilustrat în figura alăturată, unde submatricea 𝐴 are colțul stânga-sus în (𝑥1, 𝑦1), iar colțul dreapta-jos în \( \left( \left[ \frac{x1 + x2}{2} \right], \left[ \frac{y1 + y2}{2} \right] \right) \), \( \left[ x \right] \) reprezentând partea întreagă a numărului real 𝑥. Forma comprimată a submatricei 𝑅 este definită recursiv C(𝑅) =(C(𝐴), C(𝐵), C(𝐶), C(𝐷)).

Cunoscând dimensiunile și elementele matricei 𝑇 să se determine:

1. Indicii liniilor matricei 𝑇 pentru care suma elementelor aflate pe fiecare dintre acestea este maximă.
2. Indicii liniilor matricei 𝑇 pentru care elementele pot fi rearanjate astfel încât să formeze pe linia respectivă, o progresie aritmetică de rație nenulă.
3. Forma comprimată a matricei 𝑇.

Se consideră o pereche de șiruri de caractere, 𝑆 și 𝑇 , de lungime 𝑛, respectiv 𝑚, formate exclusiv din litere mici ale alfabetului englez. Pozițiile literelor sunt numerotate în șir începând de la 1.

Sunt două tipuri de operații ce se pot efectua asupra șirului 𝑇:

• 1 𝑝: se șterge litera de pe poziția 𝑝;
• 2 𝑠𝑡 𝑑𝑟 (cu 𝑠𝑡 ≤ 𝑑𝑟): se sortează crescător (alfabetic) literele din subsecvența ce corespunde intervalului de poziții [𝑠𝑡, 𝑑𝑟];

unde 𝑝, 𝑠𝑡 și 𝑑𝑟 sunt poziții ale unor litere din șirul 𝑇.

Inițial, toate literele șirului 𝑇 sunt necolorate. O operație de tip 2 poate fi realizată doar dacă toate literele din subsecvența corespunzătoare intervalului de poziții [𝑠𝑡,𝑑𝑟] sunt necolorate. După efectuarea sortării, toate literele din această subsecvență devin colorate.

Pentru fiecare dintre perechile de șiruri de tipul 𝑆 și 𝑇 date:

1. Să se afișeze literele distincte care apar în cel puțin unul dintre șiruri și, pentru fiecare dintre acestea, sim-
   bolul șirului (literele 𝑆 sau 𝑇) în care apare de mai multe ori. În caz de egalitate, se alege șirul 𝑇.
2. Să se determine o succesiune de operații de tipul 1 și/sau 2 ce pot fi aplicate șirului 𝑇, care să îl transforme
   într-un șir egal cu 𝑆. Să se afișeze DA în cazul în care există o astfel de succesiune de operații, sau NU în
   caz contrar.

În Tărâmul Magic al Insulelor, se desfășoară o vânătoare anuală de comori, unde echipele explorează insule fermecate, delimitate de apa ce le înconjoară. La ordinul regelui A., sunt ascunse comori pe fiecare insulă. Harta tărâmului este reprezentată sub forma unei matrice de dimensiune 𝑛 × 𝑚, ale cărei elemente codifică zone pătratice, cu latura de 1 metru. Acestea pot fi:

• zonă care conține apă, marcată cu −1;
• zonă care conține doar pământ, marcată cu 0; sau
• zonă care conține pământ și o singură comoară, marcată cu un număr natural nenul.

Două zone se consideră vecine dacă au o latură comună. Două zone aparţin aceleiaşi insule dacă ele sunt vecine sau dacă se poate ajunge de la o zonă la cealaltă pe un drum care parcurge o succesiune de zone, oricare două zone parcurse consecutiv fiind vecine. În acest an, căpitanul Poseidon dorește să facă o farsă regelui A., permutând comorile, astfel încât fiecare comoară să fie mutată într-o zona în care inițial a fost o altă comoară. Totuși, pentru a nu atrage atenția prea mult, comorile vor rămâne în cadrul insulei pe care se aflau inițial

Pentru început, căpitanul Poseidon își propune să rezolve următoarele cerințe:

1. Câte comori se găsesc pe insula pe care se află căpitanul Poseidon?
2. Câte soluții există pentru plasarea tuturor comorilor, astfel încât fiecare comoară să fie mutată în cadrul aceleiași insule, într-o zonă în care inițial a fost o altă comoară? Pentru că numărul de soluții poate fi foarte mare, răspunsul va fi afișat modulo 1 000 000 007.