Lista de probleme 3

Pe o tablă de joc cu N linii și M coloane se află un roboțel pe poziția 1,1. El știe să meargă doar pe conturul tablei (prima și ultima linie, respectiv prima și ultima coloană). Robotul dorește să ajungă pe poziția N, M dar nu este așa simplu. Pe tabla de joc se află Q bare de lungimi infinite. Barele sunt fixate în colțul din dreapta jos a unor căsuțe. La început, o bară se poate afla fie în poziție verticală, fie în poziție orizontală. Robotul poate schimba orientarea acestor bare din poziție verticală în poziție orizontală și invers. El nu poate trece printr-o bară.
De exemplu, dacă avem N=4, M=4, Q=1 și bara se află la coordonatele 3,3 în poziție verticală, robotul nu poate ajunge la căsuțele de pe coloana 4. Dar dacă el învârte bara poate merge pe coloana 4, apoi pentru a merge pe linia 4 poate să învârtă bara din nou.

Această soluție nu este optimă deoarece robotul putea ajunge în poziția 4,4 învârtind o singură dată bara. Mai întâi se poziționează pe linia 4, apoi învârte bara și se duce pe coloana 4.

Să se afle numărul minim de rotiri ale barelor pentru ca robotul să ajungă din poziția 1,1 în poziția N,M, mergând numai în dreapta și în jos.

Războiul intergalactic a început, iar extratereștrii au invadat deja planeta noastră. Misiunea ta este să salvezi toți locuitorii planetei cât mai repede cu putință!

Într-un hambar vechi, ai găsit un robot proiectat special pentru amplasarea de bombe nucleare și totodată o hartă a planetei sub formă de dreptunghi împărțită în N x M zone pătratice dispuse pe N linii și M coloane, de dimensiune 1. Pe hartă sunt reprezentate și pozițiile extratereștrilor (xi,yi), unde xi reprezintă indicele de linie, iar yi reprezintă indicele de coloană al extraterestrului i. De asemenea, robotul poate amplasa bombe în orice poziție de pe hartă, iar la declanșarea lor, acestea distrug orice extraterestru de pe aceeași linie sau de pe aceeași coloană cu ele.

Din păcate, robotul nu este echipat decât cu o singură bombă. Datoria ta este să-i transmiți robotului coordonatele x y unde să amplaseze bomba, astfel încât toți extratereștrii să fie distruși. Poți să salvezi planeta? Timpul se scurge! Tic, tac, tic, tac…

Cătălin este cel mai important general din armata țării sale, care are N membri (soldați și ofițeri), numerotați de la 1 la N (Cătălin are numărul 1). Un ofițer este un soldat care are în subordinea sa alți soldaţi. Conform ierarhiei militare, Cătălin și toți ceilalți ofițeri primesc inițial 3 subalterni (soldații cu numerele 2, 3 şi 4). Fiecare dintre cei trei, primește la rândul lui alți 3 subalterni, după următoarea regulă: ofițerul cu numărul x primește subalternii 3 * x – 1, 3 * x, 3 * x + 1 (dacă aceștia există în armată).

S-a descoperit că în această armată există trădători. Mai exact, toți cei numerotați cu numere prime sunt dovediți trădători, iar Cătălin știe bine asta, asa că ia măsuri radicale: decide să îi elimine pe rând pe toți acești misei, începând chiar cu subalternul său cu numărul 2. Dacă ofițerul cu numărul X este eliminat, toți subalternii săi devin subalternii comandantului său. Eliminându-l pe 2, subalternii acestuia devin subalternii comandantului lui 2, adică ai lui Cătălin. După trista eliminare a lui 2, Cătălin trece mai departe și elimină pe rând pe cei cu numerele 3, 5, 7, 11, 13 … Subalternii lui 3, 5, 7 devin subalternii lui 1, cei ai lui 11 devin ai lui 4 și tot așa.

După măcel, Cătălin trebuie să răspundă la Q întrebări ale împăratului care dorește să afle câți subalterni are un membru x al armatei sale. Dacă x a fost eliminat, Cătălin va transmite pentru acesta răspunsul -1.