Solutii probleme ProSoft @ NT editia 2016
Asteptare
Prof. Ene Dumitru – Colegiul Naţional de Informatică Piatra Neamţ
O aşteptare poate fi privită ca o permutare a mulţimii numerelor 1,2,3,…,n*n.
Pe exemplul dat prima aşteptare generează permutarea 1,2,6,7,5,3,4,8,9.
Fie p1, p2, …, pn*n permutarea obţinută la prima aşteptare.
Ştim că fiecare permutare se descompune în produs de cicluri, deci permutarea
p1, p2, …, pn*n o descompunem în produs de cicluri de lungimi L1, L2, …, Lr.
Evident că numărul minim de aşteptări este C.M.M.M.C(L1, L2, …, Lr);
În exemplul dat permutarea (1,2,6,7,5,3,4,8,9)=(1)(2)(3,6)(4,7)(5)(8)(9) de lungimi
L1=1, L2=1, L3=2, L4=2, L5=1, L6=1, L7=1, de unde rezultă C.M.M.M.C(1,1,2,2,1,1,1)=2.
Secvente3
Paul Diac,
Facultatea de Informatica, Iasi
Au fost luate în vedere următoarele soluţii:
~20 pct: Se generează într-un vector termini şirului Ai astfel încât să nu se depasească limita de memorie. Pentru fiecare întrebare se pleacă de la Ast şi se scade pe rând din S: Ast, Ast+1, etc până când S devine negativ. Răspunsul dr este poziţia anterioară.
~40 pct: Recalculăm şirul Ai pentru fiecare întrebare, fară să îl reţinem în memorie. Rămane aproximativ aceeaşi complexitate timp O(M×D) dar complexitatea memorie se reduce la O(1); unde D = max(dr).
~60 pct: Ne folosim de faptul că şirul Ai este periodic. Calculăm această perioadă şi suma elementelor ei şi ne folosim de ele pentru a răspunde mai rapid la o întrebare. Timp: O(M × Perioada + [M / Perioada])
~80 pct: Putem împărti şirul Ai în secvente de lungimi egale puse cap la cap. Reţinem pentru fiecare secvenţă suma şi valoarea primului element. Ne folosim de ele pentru a răspunde la întrebări. Complexitatea timp devine O(M×sqrt(D)) iar limita de memorie permite alocarea O(sqrt(D)).
~100 pct: Sortăm întrebarile crescator dupa .st. Parcurgem elementele Ai fară sa le reţinem dar calculam suma stânga până la (exclusive) orice pozitie .st în ordinea sortării. Adăugăm aceste sume la valorile S corespuzătoare. Acum întrebările sunt echivalente cu întrebări de forma: care este poziţia dr pentru care suma de la primul element A1, A2, etc până la această poziţie depăşeste valoarea S?
Folosim aceeaşi idee, sortand crescător întrebările dupa noul S. Iterăm iar elementele şirului de la început iar când suma stanga curentă depăşeste un S pentru o întrebare cunoastem răspunsul la întrebarea respectivă (poziţia curentă -1). Întrebările cu S-uri mai mici au fost deja răspunse, iar cele cu S mai mari urmează pentru poziţii mai mari. (similar cu interclasarea reţinem doar un indice peste vectorul de întrebări sortat). La final trebuie să răspundem dar în ordinea iniţială a întrebărilor, care se poate reţine usor.
Complexitate timp O(M×logM + D), Memorie O(M).
Vecini2
Soluţie problema Vecini
Prof. Gh. Manolache – Colegiul Naţional de Informatică Piatra Neamţ
Problema se rezolvă prin metoda greedy. Pentru a obţine b1 sortez literele din b crescător obţinând astfel un sir bx. Dacă bx>a atunci b1 nu există iar b2=bx. Pentru b2, sortez descrescător literele din b obţinând by. Dacă by<a atunci b2 nu există iar b1=by. În cazul în care bx < a < by există şi b1 şi b2 care sunt permutări consecutive lexicografic şi se obţin simplu. Se pune în b1 literele disponibile din b care reprezintă cel mai lung prefix posibil a lui a. Dacă mai exista cel putin o literă mai mică decât cea care urmeaza în a, selectez cea mai mare astfel de literă şi apoi restul literelor în ordine descrescătoare. Se poate construi similar b2. Mai simplu, aleg b2 ca următoarea permutare a lui b1. Dacă după construcţia prefixului nu există litera mai mică decât cea care urmează în a, atunci obţin b2 din restul de litere din b crescător. În acest caz generez permutarea precedentă din b2 şi obţin b1.
Un caz particular este atunci când a şi b au aceleaşi litere. În acest caz generăm din a permutarile următoare/precedentă dacă este posibil ( nu va fi posibil dacă literele din a sunt deja sortate crescător sau descrescător). Ca implementare simplă se poate utiliza next_permutation şi previuos_permutation din STL.
Valentin
Prof. Szabo Zoltan – Liceul Tehnologic “Petru Maior” Reghin
Solutia 1 soluţia brută,
pentru n<=20, complexitate O(2^n), 30 de puncte
Generăm toate submulţimile calculând suma maximă şi numărul soluţiilor distincte.
Soluţia 2-3 cu sortare,
pentru n<=1000, complexitate O(n^2), 45 de puncte
pentru n<=50000, complexitate O(nlogn), 60 de puncte
Sortăm şirul pentru a avea acces mai uşor la elementele pozitive, nule şi maximul elementelor negative.
Pentru a putea accesa şi număra valorile maxime ale numerelor negative pare şi impare, respectiv valorea minimului numerelor pozitive, vom sorta şirul special:
- numere negative în formă de şir deal: elementele pare în ordine descrescătoare, urmate de elementele impare în ordine crescătoare
- la mijloc numerele nule
- urmate de elementele impare în formă de şir munte: numerele impare în ordine crescătoare şi numerele pare în ordine descrescătoare
Pentru a calcula suma maximă a unui subşir avem nevoie de următoarele variabile:
- sum_par_poz: suma numerelor pare pozitive
- sum_impar_poz: suma numerelor impare pozitive
- nr_zero: numărul zerourilor
- nr_par_poz: numărul numerelor pare pozitive
- nr_impar_poz: numărul numerelor impare pozitive
- min_impar_poz: minimul numerelor impare pozitive
- nr_min_impar_poz: numărul de apariţii al minimului numerelor impare pozitive
- max_impar_neg: maximul numerelor impare negative
- nr_max_impar_neg: numărul de apariţii al maximului numerelor impare negative
- max_impar_neg2: a doilea cel mai mare element impar negativ (poate fi egal cu max_impar_neg)
- nr_max_impar_neg2: numărul de apariţii celui de al doilea cel mai mare număr impar negativ
(are relevanţă doar dacă max_impar_neg != max_impar_neg2)
- max_par_neg: maximul numerelor pare negative
- nr_max_par_neg: numărul de apariţii al maximului numerelor impare negative
| cazul | conditiile | suma maxima | numarul solutiilor |
|---|---|---|---|
| 1 | nr_par_poz>0 nr_impar_poz=2k>0 | sum_par_poz+ sum_impar_poz | 2^nr_zero |
| 2 | nr_par_poz>0 nr_impar_poz=0 | sum_par_poz | 2^nr_zero |
| 3 | nr_par_poz>0 nr_impar_poz=2k+1 min_impar_poz+max_impar_neg>0 | sum_par_poz+ sum_impar_poz+ max_impar_neg | nr_max_impar_neg* 2^nr_zero |
| 4 | nr_par_poz>0 nr_impar_poz=2k+1 min_impar_poz+max_impar_neg=0 | sum_par_poz+ sum_impar_poz+ max_impar_neg | (nr_max_impar_neg+ nr_min_impar_poz)* 2^nr_zero |
| 5 | nr _par_poz>0 nr_impar_poz=2k+1 min_impar_poz+max_impar_neg<0 | sum_par_poz+ sum_impar_poz- min_impar_poz | nr_min_impar_poz* 2^nr_zero |
| 6 | nr_par_poz=0 nr_impar_poz=2k>0 | sum_impar_poz | 2^nr_zero |
| 7 | nr_par_poz=0 nr_impar_poz=0 nr_zero>0 | 2^nr_zero-1 | |
| 8 | nr_par_poz=0 nr_impar_poz=0 nr_zero=0 nr_par_neg>0 nr_impar_neg=0 | max_par_neg | nr_max_par_neg |
| 9 | nr_par_poz=0 nr_impar_poz=0 nr_zero=0 nr_par_neg>0 nr_impar_neg>0 max_par_neg>max_impar_neg1+ max_impar_neg2 | max_par_neg | nr_max_par_neg* 2^nr_zero |
| 10 | nr_par_poz=0 nr_impar_poz=0 nr_zero=0 nr_par_neg>0 nr_impar_neg>0 max_par_neg=max_impar_neg1+ max_impar_neg2 nr_maxim_par_neg=1 | max_par_neg | nr_max_par_neg+ nr_max_impar_neg2 |
| 11 | nr_par_poz=0 nr_impar_poz=0 nr_zero=0 nr_par_neg>0 nr_impar_neg>0 max_par_neg=max_impar_neg1+ max_impar_neg2 nr_max_impar_neg>1 | max_par_neg | nr_max_par_neg+ comb(nr_max_impar_neg,2) |
| 12 | nr_par_poz=0 nr_impar_poz=0 nr_zero=0 nr_par_neg>0 nr_impar_neg>0 max_par_neg<max_impar_neg+ max_impar_neg2 nr_max_impar_neg=1 | max_impar_neg+ max_impar_neg2 | nr_max_impar_neg2 |
| 13 | nr_par_poz=0 nr_impar_poz=0 nr_zero=0 nr_par_neg=0 nr_impar_neg>0 nr_max_impar_neg=1 | max_impar_neg+ max_impar_neg2 | nr_max_impar_neg2 |
| 14 | nr_par_poz=0 nr_impar_poz=0 nr_zero=0 nr_par_neg=0 nr_impar_neg>0 nr_max_impar_neg>1 | 2*max_impar_neg | comb(nr_max_impar_neg,2) |
| 15 | nr_par_poz=0 nr_impar_poz=0 nr_zero=0 nr_par_neg>0 nr_impar_neg>0 max_par_neg<max_impar_neg+max_impar_neg2 nr_max_impar_neg>1 | 2*max_impar_neg | comb(nr_max_impar_neg,2) |
| 16 | nr_par_poz=0 nr_impar_poz=2k+1 nr_zero=0 nr_impar_neg=0 | sum_impar_poz- min_impar_poz | nr_min_impar_poz |
| 17 | nr_par_poz=0 nr_impar_poz=2k+1 nr_zero>0 nr_impar_neg=0 | sum_impar_poz- min_impar_poz | nr_min_impar_poz* 2^nr_zero |
| 18 | nr_par_poz=0 nr_impar_poz=2k+1 nr_zero=0 nr_impar_neg>0 min_impar_poz+max_impar_neg>0 | sum_impar_poz+ max_impar_neg | nr_max_impar_neg |
| 19 | nr_par_poz=0 nr_impar_poz=2k+1 nr_zero>0 nr_impar_neg>0 min_impar_poz+max_impar_neg>0 | sum_impar_poz+ max_impar_neg | nr_max_impar_neg* 2^nr_zero |
| 20 | nr_par_poz=0 nr_impar_poz=2k+1 nr_zero=0 nr_impar_neg>0 min_impar_poz+max_impar_neg=0 | sum_impar_poz+ max_impar_neg | (nr_max_impar_neg+ nr_min_impar_poz) |
| 21 | nr_par_poz=0 nr_impar_poz=2k+1 nr_zero>0 nr_impar_neg>0 min_impar_poz+max_impar_neg=0 | sum_impar_poz+ max_impar_neg | (nr_max_impar_neg+ nr_min_impar_poz)* 2^nr_zero |
| 22 | nr_par_poz=0 nr_impar_poz=2k+1>2 nr_zero=0 nr_impar_neg=0 min_impar_poz+max_impar_neg<0 | sum_impar_poz- min_impar_poz | nr_min_impar_poz |
| 23 | nr_par_poz=0 nr_impar_poz=2k+1>2 nr_zero>0 nr_impar_neg=0 min_impar_poz+max_impar_neg<0 | sum_impar_poz- min_impar_poz | nr_min_impar_poz* 2^nr_zero |
| 24 | nr_par_poz=0 nr_impar_poz=1 nr_zero=0 min_impar_poz+max_impar_neg> max_par_neg | min_impar_poz+ max_impar_neg | nr_max_impar_neg |
| 25 | nr_par_poz=0 nr_impar_poz=1 nr_zero=0 min_impar_poz+max_impar_neg= max_par_neg | min_impar_poz+ max_impar_neg | nr_max_impar_neg+ nr_max_par_neg |
| 26 | nr_par_poz=0 nr_impar_poz=1 nr_zero=0 min_impar_poz+max_impar_neg< max_par_neg | max_par_neg | nr_max_par_neg |
| 27 | nr_par_poz=0 nr_impar_poz=1 nr_zero>0 min_impar_poz+max_impar_neg>0 | min_impar_poz+ max_impar_neg | nr_max_impar_neg |
| 28 | nr_par_poz=0 nr_impar_poz=1 nr_zero>0 min_impar_poz+max_impar_neg=0 | (nr_max_impar_neg+1)* 2^nr_zero-1 | |
| 29 | nr_par_poz=0 nr_impar_poz=1 nr_zero>0 min_impar_poz+max_impar_neg<0 | 2^nr_zero-1 |
Solutia 4: calcul liniar,
pentru n<=600000, complexitate O(n), 100 de puncte
memorie O(n) sau O(1)
Toate valorile mai sus menţionate se pot calcula şi cu ocazia unei singure parcurgeri, în plus nu avem nevoie memorarea elementelor şirului. Fiecare element se poate prelucra în momentul citirii.
