Lista de probleme 4

Se dau două numere naturale N și M. Se consideră un șir de numere de lungime N indexat de la 0 căruia trebuie să i se atribuie valori astfel încât să se respecte M restricții de forma:

0 i val1 val2 - elementul i poate avea doar valoarea val1 sau val2
1 i j val – fix unul dintre elementele de pe pozițiile i și j trebuie să aibă valoarea val
2 i j – elementele de pe pozițiile i și j trebuie să aibă valori diferite
3 i j – elementele de pe pozițiile i și j trebuie să aibă aceeași valoare

Determinați o atribuire de valori asupra șirului astfel încât acesta să respecte cele M restricții.

Peste un mic râu care se varsă într-un mare râu, într-un oraș din inima munților, există N pietre, numerotate de la 1 la N. Un grup de copii obișnuiește să nu aleagă calea ușoară, așa că trebuie să sară peste cele N pietre, pentru a ajunge pe partea cealaltă.

Pentru fiecare dintre aceste pietre, se cunoaște înălțimea sa, notată în continuare cu h[i]. Prietenii pot să aleagă să sară anumite pietre, pentru a minimiza efortul necesar traversării râului. Formal, de pe piatra cu indicele i aceștia pot să ajungă pe toate pietrele numerotate cu indicii i + 1, i + 2, …, min(N,i + K). Efortul necesar pentru a sări de pe piatra i pe piatra j este dat de formula \( \left[ \sqrt[ 3 ]{h[i]-h[j]} \right] + C \), unde C este o constantă.

Să se calculeze efortul minim de a ajunge de la prima piatră la ultima.

Se dau două numere N și T urmate de un șir de caractere S de lungime N. Se dau apoi T operații de trei tipuri:
1. Se adaugă un caracter la sfârșitul șirului S;
2. Se adaugă șirul S în mulțimea M doar dacă acesta nu există deja în mulțime;
3. Se cere numărul de șiruri din mulțimea M care sunt sufixe ale șirului S;
Afișați răspunsul tuturor operațiilor de tip 3.

Se dau două numere N și M urmate de un șir de numere întregi nenule S de lungime impară N indexat de la 0. Asupra acestuia se vor efectua fix M operații de swap. O operație reprezintă selectarea la întâmplare a doi indici (nu neapărat distincți) din intervalul [0, N – 1] și interschimbarea elementelor de pe pozițiile respective. Se consideră că șirul este alternant dacă nu există elemente alăturate având același semn. Determinați probabilitatea ca la finalul celei de-a M-a operații, șirul să fie alternant. (Se garantează că există cel puțin o aranjare a șirului astfel încât acesta să fie alternant). Se poate demonstra că probabilitatea cerută se poate reprezenta sub forma P / Q unde P si Q sunt prime între ele.