Lista de probleme 3

Pe o zonă în formă de dreptunghi cu laturile de lungimi N și M se găsesc NxM pătrate de latură 1. În centrul fiecărui pătrat se găsește înfipt câte un ac de grosime neglijabilă. Fiecare ac este descris de înălțimea sa. Această zonă se poate reprezenta ca un tablou bidimensional de dimensiuni N și M, iar fiecare element din matrice reprezintă înălțimea (număr natural nenul) fiecărui ac. În centrul pătratului (N,M) există o cameră de luat vederi de ultimă generație, mobilă, care se poate roti cu 360⁰ în orice plan, situată la nivelul solului. Dimensiunile camerei sunt neglijabile.

Pentru direcția N, camera va vedea acul de coordonatele (3,4) – în totalitate, iar acul (2,4) se va vedea doar parțial . Acul (1,4) nu se vede pentru că este acoperit total de (2,4). În direcția V, camera va vedea doar acul (4,3), deoarece (4,2) și (4,1) sunt acoperite total de (4,3). Pentru celelalte direcții se vor vedea parțial sau în totalitate acele (3,3), (3,2), (3,1), (2,3), (1,3), (2,2), (2,1), (1,2). Acul (1,1) nu se vede din cauza acului (2,2), care îl acoperă total. Acul (2,2) se vede doar parțial, pentru că o parte din el este acoperit de acul (3,3).

1. Câte ace vede camera de luat vederi dacă se poate roti în plan vertical, doar în direcțiile N și V?
2. Câte ace vede camera de luat vederi dacă se poate roti în orice plan și în orice direcții?

Ștefan a împlinit 15 ani. Fiind un pasionat membru al Clubului de Robotică, familia i-a dăruit de ziua lui foarte mulți roboți, fiecare dotat cu o armă de o anumită putere. El a așezat toți roboții în jurul său, pe circumferința unui cerc imaginar, în sensul acelor de ceasornic. Aceste dispozitive inteligente pot comunica între ele, unindu-și puterile armelor.

Cunoscând numărul de roboți, precum și puterea fiecăruia, să se scrie un program care determină:
1. Dimensiunea celei mai lungi secvențe de roboți pentru care puterile armelor lor formează un șir strict crescător.
2. O aranjare a roboților pe cerc, astfel încât suma produselor de câte două puteri vecine să fie maximă. Dacă există mai multe modalităţi de aranjare astfel încât să se obţină aceeaşi sumă maximă, se va determina cea minimă din punct de vedere lexicografic.

Să ne imaginăm faptul că la un anumit liceu există doar două clase per generație: una de Real și una de Uman. În prezent au loc înscrierile pentru clasa a IX-a. Cele două clase au fiecare câte M locuri disponibile, atât la Real, cât și la Uman. Dacă lista de elevi înscriși la o anumită clasă conține mai mult de M elevi, vor fi admiși acei M elevi care au notele cele mai mari. Ambele clase au deja M elevi înscriși, iar pentru fiecare se știe nota cu care a fost înscris la clasa respectivă.

Mai există însă N elevi, singurii încă neînscriși, care sunt privilegiați în acest proces (fiindcă au terminat gimnaziul la acest liceu). Privilegiul lor constă în următorul fapt: ei se pot înscrie acum, după ce înscrierile publice au fost încheiate, și se cunosc notele de înscriere la ambele clase. Fiecare din cei N elevi are câte două note: nota cu care ar fi înscris la Real și nota cu care ar fi înscris la Uman (acestea pot fi diferite, deoarece examenele de admitere de la cele două clase diferă). Fiecare din cei N elevi va alege să se înscrie în maxim o clasă. Ei își vor coordona alegerile astfel încât să maximizeze numărul de elevi admiși. Deoarece calculele devin destul de complicate, aceștia s-ar putea folosi de ajutorul vostru. Ei doresc răspunsul la două întrebări.

(1) Care este numărul maxim de elevi privilegiaţi care pot fi admiși dacă se pune restricția suplimentară ca toți elevii privilegiați admiși să fie admiși la aceeași clasă?
(2) Care este numărul maxim de elevi privilegiaţi care pot fi admiși dacă aceștia se pot înscrie la clase diferite?