Lista de probleme 2

Tudor a primit un joc educaţional numit “Roboţel” cu ajutorul căruia va învăţa punctele cardinale Nord, Est, Sud, Vest. Jocul constă dintr-un roboţel care se deplasează pe o tablă de forma unei matrici pătratice, împărţită în R linii şi R coloane. Fiecare căsuţă, aflată la intersecţia dintre o linie şi o coloană, este fie căsuță „liberă”, fie căsuță „semnalizator”, caz în care este etichetată cu una din literele N, E, S, V, reprezentând 4 sensuri posibile de deplasare. Când roboțelul ajunge într-o „căsuţă semnalizator”, el îşi schimbă sensul de deplasare astfel:

• Dacă căsuţa este etichetată cu N atunci roboţelul se va deplasa în continuare de jos în sus;
• Dacă căsuţa este etichetată cu E atunci roboţelul se va deplasa în continuare de la stânga la dreapta;
• Dacă căsuţa este etichetată cu S atunci roboţelul se va deplasa în continuare de sus în jos;
• Dacă căsuţa este etichetată cu V atunci roboţelul se va deplasa în continuare de la dreapta la stânga.

Două căsuțe semnalizator formează o pereche „blocantă” dacă:

• Se află pe aceeași linie și conțin literele E și V, căsuța cu E are coloana mai mică decât a celei etichetate cu V și între ele, pe aceeași linie nu există alte căsuțe semnalizatoare.
• Se află pe aceeași coloană și conțin literele S și N, căsuța cu S are linia mai mică decât a celei etichetate cu N și între ele, pe aceeași coloană nu există alte căsuțe semnalizatoare.

În figura 1, de exemplu, sunt 2 perechi blocante: Perechea (1,2) (5.2) și perechea (2,3) (2,5).

Roboţelul porneşte din căsuţa (1,1), aflată pe prima linie și prima coloană şi dacă aceasta este liberă, se deplasează, în cadrul primei linii, de la stânga la dreapta. În cazul în care căsuța de pornire (1,1) este semnalizator, atunci roboțelul se va deplasa pe direcția indicată de litera cu care este etichetată. Considerând că roboțelul se deplasează pe tablă, el se oprește doar în următoarele situații:

• Roboţelul intră într-o căsuţă liberă aflată pe prima sau ultima linie, respectiv prima sau ultima coloană, caz în care dacă s-ar menține sensul deplasării actuale roboțelul ar părăsi tabla;
• Roboțelul intră într-o „căsuţă semnalizator” a unei perechi blocantă și se va opri în cealaltă căsuță a perechii.

De exemplu, în Figura 2, roboțelul ajunge în căsuța liberă (3,5) unde se oprește. În Figura 3, roboțelul se va opri în căsuța (4,1) deoarece dacă ar schimba sensul spre Est, ar reveni în ultima căsuță semnalizator vizitată, (4,3).
Roboțelul înaintează o căsuță într-un pas, în sensul de deplasare.

Scrieţi un program care, cunoscând numărul R de linii şi coloane și cele K căsuţe semnalizator, determină:

1. Toate perechile blocante de pe tablă;
2. Numărul de pași efectuați pe fiecare sens în parte: Nord, Est, Sud și Vest

Ionel și Georgel sunt colegi de clasă și doresc să facă schimb de fișiere prin email. Fiecare dintre ei își arhivează fișierele cu câte o parolă. Fiecare copil își construiește parola pe baza unui șir format din N numere naturale.

Numerele din șir care se folosesc efectiv pentru construirea parolelor sunt doar cele divizibile cu numerele din mulțimea {2,3,4,5,6,7,8,9,10,11,12,13,14,15}. Copiii numără câte din valorile din șir sunt divizibile cu fiecare din aceste numere.

Parola folosită de Ionel se obține prin însumarea numărului de valori din șir care sunt divizibile cu numerele din mulțimea {2,3,4,5,6,7,8,9}. Parola folosită de Georgel se obține prin însumarea numărului de valori din șir care sunt divizibile cu numerele din mulțimea {10,11,12,13,14,15}.

Scrieţi un program care citește șirul celor N numere și determină:

1. câte numere din șir nu se vor folosi în construirea parolelor celor doi copii;
2. parola construită de Ionel;
3. parola construită de Georgel.