Lista de probleme 3

Se consideră șirul S = S[1], S[2], ..., S[N] format din N mulțimi de numere naturale cuprinse între 1 și M. De asemenea, se consideră două șiruri de câte M numere întregi A = A[1], A[2], ..., A[M] și B = B[1], B[2], ..., B[M]. Numim secvență de mulțimi (i, j) (1 ≤ i ≤ j ≤ N) succesiunea de mulțimi S[i], S[i+1], ..., S[j]. Pentru o secvență de mulțimi (i, j) (1 ≤ i ≤ j ≤ N), se determină factorul de succes pe baza șirului A, respectiv factorul de insucces, pe baza șirului B în modul următor:
1) se efectuează reuniunea mulțimilor din secvența de mulțimi (i, j);
2) factorul de succes al secvenței de mulțimi (i, j) este suma valorilor din șirul A situate pe pozițiile date de elementele reuniunii;
3) factorul de insucces al secvenței de mulțimi (i, j) este suma valorilor din șirul B situate pe pozițiile date de elementele reuniunii.
Determinați factorul de succes al unei secvențe câștigătoare.

Pentru a îmbunătăţi aptitudinile logico-matematice ale elevilor săi, profesorul Vasile a implementat un joc. Pe ecranul principal al jocului se afişează un şir de N scaune, numerotate de la stânga spre dreapta începând cu 1, pe fiecare scaun fiind așezat câte un copil. Fiecare copil poartă un tricou pe care este scris, de asemenea, câte un număr de la 1 la N. Numerele de pe tricouri sunt distincte și sunt scrise pe spate, deci nu sunt vizibile. Scopul jocului este de a descoperi numărul scris pe tricoul fiecărui copil. Pentru aceasta, pe ecran mai este afişat un triunghi de numere T, care ne dă informaţii ajutătoare. Triunghiul arată ca o matrice în care liniile sunt numerotate de sus în jos de la 1 la N, iar coloanele de la stânga la dreapta de la 1 la N. Numărul scris în triunghi pe linia i şi coloana j (1 ≤ i ≤ j ≤ n) reprezintă numărul scaunului pe care stă copilul având cel mai mic număr pe tricou dintre toţi copiii situaţi pe scaune cu numere cuprinse între i şi j (inclusiv i şi j). Observaţi că poziţiile din triunghi de pe linia i şi coloana j cu 1 ≤ j < i ≤ N nu sunt completate. Cunoscând numărul de copii şi triunghiul de numere:
1. determinați o soluţie posibilă; dacă există mai multe soluţii posibile se va afişa cea mai mică din punctul de vedere lexicografic;
2. determinați numărul de soluţii posibile.

Pentru avea succes la Olimpiada de Jocuri pe Internet (OJI), Vasilică a cumpărat de la Baba Yaga un talisman norocos. Talismanul norocos este un șir care îndeplineşte următoarele două condiţii:

• toate elementele șirului sunt cifre mai mici sau egale cu magicul 7;
• oricare două elemente aflate pe poziții consecutive în șir au cel puţin un divizor comun strict mai mare decât 1.

1. determinaţi numărul minim de cifre care trebuie să fie eliminate din șirul V, astfel încât acesta să devină talisman norocos;
2. determinaţi talismanul norocos minim lexicografic, care se obţine eliminând din șirul V un număr minim de cifre.