Soluții trimise

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ț.