Lista de probleme 3

În laboratoarele Marii Ghilde, ucenicul Jean Carapace are pe masa de lucru N eprubete asezate in linie. Eprubetele sunt numerotate de la stanga la dreapta cu indici de la 1 la N. Fiecare eprubetă i conține inițial o cantitate de Esență Primordială, V[i] , număr natural nenul. Definim o „Pereche Pură” ca fiind două eprubete vecine ale căror cantități sunt reprezentate prin numere prime între ele, adică cmmdc(V[i] , V[i+1]) = 1. O proprietate esențială a configurației inițiale este că se garantează existent, a a cel puțin unei astfel de perechi.

Scopul lui este să obțină „Scara Perfectă”, adică o configurație în care cantitatea de esență din fiecare eprubetă este
egală cu indicele ei:

Eprubeta ₁ = 1, Eprubeta ₂ = 2, …, Eprubeta _N = N.

Pentru a modifica nivelul substanței, el poate folosi doar fenomenul de Rezonanță între două eprubete vecine. Mai exact, operațiile se aplică pe două eprubete situate la indicii A și B, cu condiția ca |A − B| = 1. Operațiile permise sunt:

• adun A B ⇒ V[A] ← V[A] + V[B] (Eprubeta A câștigă o cantitate de esență egală cu valoarea din eprubeta B)
• scad A B ⇒ V[A] ← V[A] − V[B] (Eprubeta A pierde o cantitate de esență egală cu valoarea din eprubeta B)

La aplicarea operațiilor, trebuie respectate următoarele reguli:

1. La fiecare operație, doar eprubeta cu indicele A își modifică valoarea. Eprubeta cu indicele B rămâne neschimbată.
2. Cantitatea de esență din orice eprubetă trebuie să se mențină în intervalul de siguranță [1, 10sup>5] în orice moment (inclusiv intermediar).
3. Numărul total de operații nu poate depăși 106.

Se cunosc C (numărul cerinței, 1 sau 2), N numărul de eprubete, precum și valorile V[i]. Determinați:

1. Secvența de lungime maximă din șir în care oricare două eprubete alăturate formează o Pereche Pură, dacă C = 1. Dacă există mai multe astfel de secvențe, se va afișa cea cu indicele de început minim.
2. O succesiune de operații care transformă șirul inițial în Scara Perfectă, respectând toate regulile de mai sus, dacă C = 2.

Înainte de finala campionatului regional de fotbal, antrenorul echipei „Șahtior Maramu’”, domnul Andrei, împreună cu analiștii echipei, John și Bob, au analizat formația de joc. Pentru aceasta, ei au așezat pe teren N jucători în linie.

Fiecare jucător poartă un tricou pe care este imprimată o singură cifră (de la 0 la 9). Întrucât bugetul echipei este unul restrâns, mai mulți jucători pot purta tricouri cu același număr. Privind de la stânga la dreapta, cifrele de pe tricourile jucătorilor formează un număr natural.

Analiștii John și Bob au observat că pentru a stabili tactica de joc pentru finala campionatului, domnul Andrei respectă următorii pași:

• Din cei N jucători chemați în teren inițial, el trebuie să elimine exact K jucători (K < N), cerându-le să meargă pe banca de rezerve. Jucătorii rămași în teren se vor apropia unul de celălalt, păstrându-și ordinea inițială;
• Pentru a asigura succesul echipei, Andrei va elimina cei K jucători astfel încât numărul format din cifrele de pe tricourile jucătorilor rămași în teren să fie cel mai mare număr posibil. Acest număr reprezintă valoarea tactică a echipei;
• Apoi, pentru înscrierea în sistemul electronic al federației, Andrei trebuie să calculeze stabilitatea echipei, definită de cel mai mare număr natural X, al cărui pătrat nu depășește valoarea tactică V a echipei (X2 ≤ V).

La unele meciuri, din cauza numărului foarte mare de jucători chemați pe teren, echipa nu dispune de suficiente tricouri cu cifre diferite. În aceste situații speciale, toți jucătorii poartă tricouri pe care sunt imprimate doar cifrele 0 sau 1. În acest caz (în care cifrele de pe tricouri sunt doar valori de 0 și 1), valoarea tactică este interpretată în baza 2. De exemplu, dacă în teren rămân jucătorii cu tricourile 1, 1, 1, valoarea tactică este 111 (în baza 2), adică numărul 7 (în baza 10).

Cum timpul până la marea finală este limitat, John și Bob vă roagă să îl ajutați pe antrenorul Andrei să înscrie echipa în sistemul electronic al federației.

Se cunosc C (numărul cerinței, 1 sau 2), N numărul inițial de jucători, K numărul de jucători ce trebuie eliminați, precum și cele N cifre de pe tricourile jucătorilor. Ajutați-l pe antrenorul Andrei să determine:

1. Valoarea tactică a echipei, dacă C = 1.
2. Stabilitatea echipei, dacă C = 2.

Pentru a descoperi ieșirea din Marele Labirint, exploratorul trebuie să descifreze o hartă antică. Harta este reprezentată sub forma unui tablou bidimensional cu 𝑁 linii și 𝑀 coloane, cu elemente numere naturale nenule. Liniile sunt numerotate de la 1 la 𝑁 (de sus în jos), iar coloanele de la 1 la 𝑀 (de la stânga la dreapta).

Definim un mapat ca fiind un pătrat descris de o poziție (𝑖,𝑗) numită colț principal și o latură de lungime 𝐿, unde 1 ≤ 𝐿 ≤ min(𝑖, 𝑗). Mapatul acoperă toate celulele având indicii (𝑥,𝑦), unde 𝑖 − 𝐿 + 1 ≤ 𝑥 ≤ 𝑖 și 𝑗 − 𝐿 + 1 ≤ 𝑦 ≤ 𝑗, adică este un pătrat de 𝐿 × 𝐿 celule al cărui colt, dreapta-jos este chiar (𝑖,𝑗).

Valoarea unui mapat se calculează astfel:

1. Se determină suma tuturor elementelor din pătrat, notată cu 𝑆.
2. Valoarea mapatului este produsul dintre 𝑆 și valoarea de la poziția (𝑖,𝑗).

Fixând o lungime 𝐿 și o linie 𝑖 (cu 𝑖 ≥ 𝐿), pentru fiecare coloană 𝑗 ≥ 𝐿, notăm cu 𝐴[𝑗] valoarea mapatului cu colțul principal la coordonatele (𝑖,𝑗) și latura de lungime 𝐿. O secvență de mapate situate pe linia i este determinată de doi indici, 𝑠𝑡 și 𝑑𝑟. Definim suma secvenței de mapate ca fiind 𝐴[𝑠𝑡] + 𝐴[𝑠𝑡 +1] + ··· + 𝐴[𝑑𝑟] , cu 𝐿 ≤ 𝑠𝑡 ≤ 𝑑𝑟 ≤ 𝑀.

Se dau 𝑞 întrebări de tipul 1 și 𝑝 întrebări de tipul 2.

1. Întrebare de tipul 1. Cunoscându-se trei valori 𝐿, 𝑖 și maxVal, determinați lungimea maximă a unei secvențe de mapate cu latura de lungime 𝐿, situate pe linia 𝑖 și având suma secvenței de mapate mai mică sau egală cu maxVal.
2. Întrebare de tipul 2. Cunoscându-se patru valori 𝐿, 𝑖, minVal și maxVal, determinați numărul secvențelor de mapate cu latura de lungime 𝐿, situate pe linia 𝑖 și având suma secvenței de mapate cuprinsă între minVal și maxVal.