Lista de probleme 1058

Se dă o rețea de N * M calculatoare, dispuse sub forma unei matrici cu N linii și M coloane, numerotate începând cu 1, între care se pot transfera informații.

Fiecare calculator funcțional are asociat un cod, număr natural. Calculatoarele defecte sunt marcate cu -1 și nu pot participa la transferul de informație.

Transferul de informație între două calculatoare funcționale se face direct, dacă acestea sunt vecine, sau indirect, prin intermediul altor calculatoare funcționale. Două calculatoare sunt vecine dacă se află pe aceeași linie și coloane adiacente sau pe aceeași coloană și linii adiacente, adică calculatorul de la poziția (i, j) este vecin cu cel de la pozițiile: (i + 1, j), (i - 1, j), (i, j + 1) sau (i, j - 1).

Costul transferului de informație între două calculatoare vecine funcționale este 0, dacă cele două coduri diferă prin cel mult un bit în reprezentarea binară, respectiv 1, în caz contrar. Costul transferului de informație între două calculatoare care nu sunt vecine este suma costurilor transferurilor directe intermediare.

Scrieți un program care să determine costul minim necesar pentru transferul informației de la calculatorul de pe poziția (1, 1) la cel de pe poziția (N, M).

Ira iubește să se joace pe telefon. Atât de mult, încât părinții au luat decizia să îi blocheze telefonul pentru a se concentra la școală. Fiind fată isteață, ea a descoperit cum poate debloca telefonul de una singură.

Pe ecranul telefonului îi apar mai multe informații:

• un număr natural N
• un șir A cu N numere naturale, numerotate de la 1 la N
• un număr natural K
• un număr natural Q, apoi Q numere x, reprezentând un indice din șirul dat.

Pentru a-și putea continua jocul ea trebuie sa răspundă corect la toate cele Q întrebări de tipul: Care este diferența între cel mai mare și cel mai mic element din secvență care începe la poziția x și are lungime k?

Scrieți un program care citește datele și răspunde corect la toate cele Q întrebări. Ira abia așteaptă să se joace din nou pe telefon!

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

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

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.

Se dă următorul algoritm misterios, care are ca date de intrare numerele naturale N și K, precum și un șir de N numere naturale A (A[1], A[2], …, A[N]), iar ca date de ieșire termenii șirului B (B[1], B[2], …, B[N]). De asemenea, algoritmul utilizează și un șir auxiliar T (T[0], T[1], …, T[N−1]).

1: 	x ← 0
2: 	y ← −1
3: 	pentru i ← 1, N execută
4:		cât timp x ≤ y și A[i] > T[y] execută
5:			y ← y−1
6:		sfârșit cât timp
7:	  	dacă x ≤ y și i − K ≥ 1 și T[x] = A[i−K] atunci
8:		  	x ← x + 1
9:		sfârșit dacă
10:		y ← y + 1
11:		T[y] ← A[i]
12:		B[i] ← y − x + 1
13:	sfârșit pentru

Dându-se N , K și cei N termeni ai unui șir B, să se determine termenii unui șir A, cu 1 ≤ A[i] ≤ N, pentru orice i de la 1 la N , care ar trebui citiți ca date de intrare în cadrul algoritmului misterios, astfel încât în urma executării acestuia să se obțină ca date de ieșire termenii șirului B dat. Dacă există mai multe soluții, oricare dintre acestea este considerată validă.

În clasa lui Ionuț sunt N elevi numerotați cu numere naturale de la 1 la N așezați în ordinea din catalog. Fiecare elev i (1 ≤ i ≤ N ) are ceea ce se numește un coeficient de popularitate \(A_i\) , un număr natural nenul. Fiecare elev din clasă are un grup de simpatizanți. Grupul de simpatizanți ai elevului i, notat cu \(G_i\) este reprezentat de cea mai lungă secvență de elevi din șirul dat în catalog, care îl conține pe elevul i, astfel încât coeficientul de popularitate al fiecărui elev j din secvență, \(A_j\) , să fie divizor al lui \(A_i\) . Lungimea secvenței, deci numărul elevilor din grupul de simpatizanți ai lui i, se notează cu \(|G_𝑖|\). Evident, elevul i face parte din propriul său grup de simpatizanți. Dacă elevul i face parte din grupul de simpatizanți ai elevului j, atunci nu este neapărat necesar ca și j să facă parte din grupul de simpatizanți ai elevului i.

După ore, unii elevi își invită la cofetărie grupul de simpatizanți, pentru câte o înghețată. Pentru un grup de simpatizanți \(G_i\) , elevul i merge și îi cere vânzătoarei exact \(|G_i|\) înghețate, dar vânzătoarea are o fire năstrușnică și îi spune că este disponibil doar un anumit număr de arome k, mereu cel mult egal cu numărul de înghețate cerute (\(1 ≤ 𝑘 ≤ |G_𝑖|\)). Elevii, creativi, calculează numărul de moduri în care se poate cumpăra înghețată pentru grup, astfel încât să achiziționeze fiecare sortiment cel puțin o dată; pentru grupul \(G_i\) , acest număr se notează cu \(v_i(k)\).

1. Determinați numărul de ordine din catalog al elevului care are cel mai numeros grup de simpatizanți. Se garantează că există un singur astfel de elev.
2. Lui Ionuț îi place foarte mult să analizeze vânzările magazinelor de înghețată și vă lansează Q întrebări de tipul: (i, st, dr) (cu \(1 ≤ i ≤ N\) și \(1 ≤ st ≤ dr ≤ |G_i|\)); pentru fiecare determinați valoarea expresiei: \(v_i(st) + v_i(st + 1) + \cdots + v_i(dr)\); cum valoarea poate fi foarte mare, luați în considerare restul împărțirii ei la \(10^9 + 7\).

Se consideră un şir format din M x N termeni a căror valoare poate fi 0 sau 1, cele Q poziţii în care se găsesc termenii egali cu 1 fiind P1, P2, …, PQ. Termenii şirului sunt memorați într-o matrice inițială cu M linii și N coloane, astfel încât șirul se obține dacă se parcurge matricea linie cu linie, în ordine, de sus în jos, și fiecare linie de la stânga la dreapta. Pentru un număr K dat, se obține o matrice nouă, cu M • K linii și N coloane, prin scrierea matricei inițiale de K ori, de sus în jos, astfel încât fiecare copie este plasată sub cea de la pasul anterior. Un grup-1 în matrice este format din una sau mai multe valori 1 și se consideră că două valori egale cu 1 fac parte din acelaşi grup-1 dacă se poate ajunge de la una la cealaltă parcurgând matricea pe un traseu format doar din elemente egale cu 1. Se cere numărul grupurilor-1 din matricea cu M •K linii şi N coloane formată.

Natașa este o pisică foarte vorbăreață: ea poate pronunța toate vocalele (a, e, i, o, u) și consoana m. Am observat că mesajul pe care Natașa încearcă să mi-l transmită este o secvență dintr-o “frază” scrisă în limbaj pisicesc, care are un număr maxim de apariţii în frază. Dacă există mai multe secvențe cu număr maxim de apariții, mesajul este secvența cu lungimea cea mai mare. Scrieți un program care citește un șir de caractere, ce reprezintă o frază în limbaj pisicesc și rezolvă următoarele cerințe:
1. determină numărul de vocale distincte existente în frază;
2. determină de câte ori apare secvența mau în frază;
3. determină mesajul transmis de Natașa, conform regulilor de mai sus.

Se dă un vector val[a], …, val[z]. Să se construiască un program minishell care folosește cât mai puține atribuiri constante și care, prin rularea sa, face ca variabilele a, …, z să conțină valorile val[a], …, val[z].