Lista de probleme 3

Fie o matrice de dimensiuni 𝑁 × 𝑀 care conține numai valorile 0 și 1. Căsuțele marcate cu 0 sunt inaccesibile, în timp ce căsuțele marcate cu 1 sunt accesibile.

Gimi se va afla inițial într-o căsuță marcată cu 1 din această matrice, poziția ei nefiind însă cunoscută nouă. Lui Gimi îi putem da instrucțiuni de tipul: deplasează-te în căsuța (𝑥𝑑 , 𝑦𝑑). Regulile sunt următoarele:

• Gimi se poate deplasa numai în căsuțe marcate cu 1.
• Gimi se poate deplasa numai în căsuțe vecine cu cea în care se află. Căsuțele vecine cu (𝑥, 𝑦) sunt (cât timp sunt în matrice): (𝑥 − 1, 𝑦), (𝑥, 𝑦 + 1), (𝑥 + 1, 𝑦) și (𝑥, 𝑦 − 1).

Dacă Gimi poate respecta toate regulile, atunci acesta se va deplasa în căsuța (𝑥𝑑 , 𝑦𝑑). Altfel, va rămâne pe loc.

Scrieți un program care, cunoscând 𝑁 și 𝑀, respectiv matricea, determină:

Cerința 1. O serie de instrucțiuni pe care, dacă Gimi o urmărește, indiferent de poziția lui inițială, ne va garanta faptul că va trece prin căsuța (𝑥𝑡 , 𝑦𝑡) (marcată cu 1).
Cerința 2. O serie de instrucțiuni pe care, dacă Gimi o urmărește, indiferent de poziția lui inițială, ne va garanta faptul că va trece prin toate celelalte căsuțe marcate cu 1.
Cerința 3. Cel mai mic număr 𝑃 astfel încât, primind o serie de 𝑄 instrucțiuni pe care, dacă Gimi o urmărește, indiferent de poziția lui de start, ne va garanta faptul că va trece prin toate celelalte căsuțe marcate cu 1, fără să fie necesară executarea instrucțiunilor de la 𝑃 + 1 la 𝑄.

Se dau 𝑁 procese care trebuie rulate pe un calculator. Există 𝑀 variabile care pot fi accesate de către aceste procese, numerotate de la 1 la 𝑀. Fiecare proces 𝑖 (unde 1 ≤ 𝑖 ≤ 𝑁) accesează un interval continuu de variabile [𝑙[𝑖], 𝑟[𝑖]], iar timpul necesar de execuție al procesului 𝑖 este 𝑡[𝑖].

Cât timp un proces rulează, acesta își salvează pe stiva de execuție toate variabilele necesare, iar la finalizarea lui le elimină de pe stivă. Două procese pot rula în paralel dacă și numai dacă nu au nicio variabilă în comun.

Sistemul de operare va planifica procesele astfel încât timpul total necesar executării tuturor să fie minim. O astfel
de planificare, care atinge timpul minim posibil, poartă numele de scenariu optim de execuție.

O variabilă este considerată critică dacă există cel puțin un scenariu optim de execuție în care aceasta petrece cel mai mult timp pe stivă dintre toate variabilele (într-un scenariu pot exista mai multe variabile critice simultan).

Dat fiind un număr 𝐶 ∈ {1, 2, 3}, reprezentând tipul cerinței:

Cerința 1. Să se determine timpul minim necesar pentru a rula toate cele 𝑁 procese date.

Cerința 2. Pentru fiecare proces 𝑖 (de la 1 la 𝑁), presupunem că îl eliminăm din sistem. Fie 𝑇[𝑖] timpul minim necesar pentru a rula restul de 𝑁 − 1 procese. Să se calculeze și să se afișeze suma tuturor valorilor 𝑇[𝑖], pentru 𝑖 de la 1 la 𝑁.

Cerința 3. Pentru fiecare proces 𝑖 (de la 1 la 𝑁), presupunem că îl eliminăm din sistem. Fie 𝑉[𝑖] numărul de variabile critice în contextul celorlalte 𝑁 − 1 procese, conform definiției anterioare. Să se calculeze și să se afișeze suma tuturor valorilor 𝑉[𝑖], pentru 𝑖 de la 1 la 𝑁.

Ionuț s-a înscris recent într-o trupă de cercetași și se pregătește pentru prima sa expediție. Trupa din care face parte Ionuț este formată din 𝑁 membri, numerotați cu numere naturale de la 1 la 𝑁. Pentru expediție, trupa trebuie să se împartă în mai multe patrule, fiecare membru 𝑖 trebuie să facă parte din exact o patrulă. Între cercetașii din trupă există niște tensiuni, astfel cercetașul 𝑖 și cercetașul 𝑗 (cu 𝑖 ≠ 𝑗) pot face parte din aceeași patrulă doar dacă |𝑖 − 𝑗| ≥ 𝑟 (unde |𝑥| reprezintă valoarea absolută a numărului 𝑥).

Ionuț, fiind foarte pasionat de numere, se întreabă în câte moduri se pot forma patrule pentru expediție, știind că cercetaşul șef vrea ca trupa să se împartă în cel puțin 𝑎 patrule și cel mult 𝑏 patrule. Două moduri 𝐴 și 𝐵 de a forma patrulele se consideră diferite dacă au un număr diferit de patrule sau dacă există un cercetaș 𝑘 (cu 1 ≤ 𝑘 ≤ 𝑁) astfel încât ehipa din care face parte 𝑘 în modul 𝐴 este diferită de cea din modul 𝐵. Cum acest număr poate fi foarte mare, se cere afișarea lui modulo 109 + 7.