Lista de probleme 3

Sala de concurs de la ONI 2026 poate fi reprezentată ca o matrice pătratică, în care liniile sunt numerotate de sus în jos de la 0 la 2𝑁, iar coloanele sunt numerotate de la stânga la dreapta de la 0 la 2𝑁. Fiecare element al matricii reprezintă o bancă. Poziția unei bănci va fi identificată prin numărul liniei și numărul coloanei pe care se află.

Pe marginea sălii (linia 0, linia 2𝑁, coloana 0 și coloana 2𝑁) se află profesorii supraveghetori (toate aceste locuri sunt considerate ocupate de la început). Astfel, elevii pot ocupa doar cele (2𝑁 − 1) × (2𝑁 − 1) bănci din interiorul sălii, situate pe linii și coloane cu numere de la 1 la 2𝑁 − 1.

Definim distanța dintre două bănci situate în pozițiile (𝐿1, 𝐶1) și (𝐿2, 𝐶2) ca fiind max(|𝐿1 − 𝐿2|, |𝐶1 − 𝐶2|), unde
cu |𝑥| s-a notat modulul numărului 𝑥 (|𝑥| = 𝑥, dacă 𝑥 ≥ 0, respectiv −𝑥, dacă 𝑥 < 0).

În acest an, așezarea elevilor în bănci se face într-un mod mai special. Elevii intră în sală pe rând pentru a susține proba și se așază în bănci exact în ordinea în care intră. Când un elev intră în sală, analizează fiecare bancă neocupată, pentru a determina cea mai mică dintre distant, ele de la aceasta până la fiecare bancă ocupată (fie de un supraveghetor, fie de alt elev). Apoi se așază într-o bancă neocupată pentru care această distanță este maximă. Dacă există mai multe bănci neocupate care respectă această condit, ie, elevul trebuie să se așeze în prima, adică cea care este situată pe linia cu numărul cel mai mic, iar în caz de egalitate a liniilor, cea situată pe coloana cu numărul cel mai mic.

Pentru ca profesorii supraveghetori să verifice rapid dacă elevii s-au așezat corect, au nevoie de un program care să răspundă la întrebări de forma 𝑁 𝐾, cu semnificația: “În ce bancă se va așeza al 𝐾-lea elev care intră într-o sală de concurs de dimensiune (2𝑁 + 1) × (2𝑁 + 1), respectând regulile de mai sus?”.

Scrieți un program care răspunde la 𝑄 întrebări de forma descrisă în enunț.

Jocul DJ (“Dublu sau Jumate”) este noua provocare pentru concurenții de la ONI 2026.

La începutul jocului primiți un șir de numere naturale.

Scopul jocului este de a egaliza valorile din șir, adică de a transforma șirul dat într-un șir cu toate elementele egale. Pentru aceasta, aveți la dispoziție două tipuri de operații:

1. se selectează un element 𝑥 din șir și se înlocuiește cu 𝑥 · 2 + 1;
2. se selectează un element 𝑥 din șir și se înlocuiește cu câtul împărțirii întregi dintre 𝑥 și 2.

Dat fiind un șir de numere naturale, scrieți un program care determină numărul total minim de operații necesare pentru egalizarea valorilor din șir.

Aurel s-a pregătit pentru ninsoare, dar zăpada care s-a așezat aseară tot i-a dat bătăi de cap. Aleea pe care trebuie să o deszăpezească Aurel este formată din 𝑛 dale pătrate, pozițiile acestora fiind numerotate în ordine, de la stânga la dreapta, de la 1 la 𝑛. Fiind un tip meticulos, înainte de a se apuca de treabă, Aurel a determinat cantitatea de zăpadă (exprimată în grame) care s-a așezat pe fiecare dintre cele 𝑛 dale și a notat cu z[𝑖] cantitatea de zăpadă existentă pe dala 𝑖 (1 ≤ 𝑖 ≤ 𝑛). Pentru a curăța aleea, el trebuie să mute toată zăpada de pe alee, în stânga sau în dreapta acesteia. Pentru simplitate, vom considera că zona din stânga aleii are poziția 0, iar zona din dreapta aleii are poziția 𝑛 + 1.

Pentru deszăpezire, Aurel a cumpărat 40 de lopeți speciale, numerotate de la 0 la 39. Cu lopata 𝑘 (0 ≤ 𝑘 ≤ 39) Aurel poate muta cel mult 2𝑘 grame de zăpadă de pe dala pe care se află aceasta pe o poziție alăturată, la stânga sau la dreapta, deci de pe poziția 𝑖 (1 ≤ 𝑖 ≤ 𝑛) pe poziția 𝑖 − 1 sau pe poziția 𝑖 + 1, pentru această acțiune consumând 𝑘 + 1 calorii.

Pentru a fi eficient, Aurel a decis să împartă aleea în două zone. Prima zonă conține toate dalele situate pe poziții mai mici sau egale cu 𝑥, iar a doua zonă conține toate dalele de poziții strict mai mari decât 𝑥. El va folosi lopețile
pentru a muta toată zăpada din prima zonă pe poziția 0 și toată zăpada din a doua zonă pe poziția 𝑛 + 1.

Cunoscând numărul de dale și zăpada acumulată pe fiecare dală, scrieți un program care să rezolve următoarele cerințe:

1. cunoscând valoarea 𝑥, determinați numărul total minim de calorii consumate de Aurel pentru a deszăpezi aleea;
2. determinați valoarea 𝑥 pentru care numărul total de calorii consumate de Aurel pentru deszăpezirea aleii este minim; dacă există mai multe astfel de valori, să se determine cea mai mică dintre acestea.