Clasa a VII-a lecția 23 - 20 feb 2020

Anunț

Deoarece olimpiada județeană bate la ușă voi organiza un concurs duminică 23 februarie la ora 15:00. Concursul va avea două probleme și va dura două ore. Succes!

Tema - rezolvări

• Avertisment lui Cadîr, care nu a rezolvat nici o problemă, nici măcar Read/Write, banală și scurtă.

Read/Write

Problema read/write este o aplicație banală a citirii și scrierii rapide, predate la curs. Cu toate acestea ați reușit cumva să luați și scoruri diferite de 100p. Pare că și utilizarea de cod este prea grea pentru unii dintre voi :-)

Comentarii generale

• În circa 19 de linii banale de program, cît ați avut de scris, ați reușit să găsiți moduri de a greși.
• Mulți nu ați trimis ultima implementare din curs, de citire/scriere, cea eficientă. Desigur că ați primit TLE.
• Mulți ați reușit să încîlciți și acest cod simplu (Ghica, Mocanu și alții).
• Unii din voi nu s-au prins că numerele scrise la ieșire sînt întregi. Drept care au simțit nevoia să modifice writeInt() în writeLongLong(). Rezultatul? Desigur TLE.

Dreptunghiuri

Problema dreptunghiuri este o aplicație a subsecvenței crescătoare de lungime maximă.

Comentarii generale

• Problema v-a dat de furcă. Ea nu este chiar banală, necesită idee (sortare după o ordine neclară).
• Unii din voi au modificat mult algoritmul de bază. Nu era necesar.
• Unii din voi și-au dorit mult să treacă toate testele (lăudabil) și ați scris un algoritm incorect. Interesant că ați făcut cu toții aceeași greșeală: Voicu T, Tatomir, alții. Surse colectate de prin ungherele întunecate ale webului sau luate de la olimpici, pe care nu le înțelegeți, ci le învățați pe din-afară. Din păcate chiar și cu greșeală treceți toate testele. Nu e ușor să creezi teste bune.
• Unii din voi nu au sortat corect vectorul. Cu toate acestea o parte din voi ați trecut toate testele. Teste defectuoase.

Subsecvența de sumă maximă

Problema subsecvența de sumă maximă este o aplicație a ceea ce am învățat la curs.

Comentarii generale

• Problema era banală, fiind nu doar simplă, ci și bine tratată în lecție.
• Cu toate acestea unii din voi v-ați complicat (Cojocariu, Ghica, Petcu, Petrescu și alții).
• Felicitări celor care au reușit o implementare minimală: Burac, posibil alții (nu am apucat să mă uit pe toate sursele).
• Constat o sursă comună cu mici modificări: Luca, Voicu T, Nicu și alții. Aveți o muză? :-)
• Mulți ați scris programe foarte încîlcite. La un algoritm de bază. Aceasta arată o lipsă a cunoștințelor de bază, a.k.a. dopaj.
• Unii ați modificat serios algoritmul de bază. Nu era cazul, vedeți mai jos.
• Unii ați copiat o soluție a mea, mai veche: Hossu și alții.
• Unii din voi au folosit vectori. Nenecesari.
• Unii din voi ați ținut morțiș să declarați un element minus infinit. Care nu există, în această problemă. Minimul este suma formată din primul element al vectorului.
• Mai grav, mulți dintre voi credeți că cel mai mic întreg posibil este egal cu cel mai mare întreg posibil dar cu semn schimbat. Mulți ați declarat #define INFINIT -2147483647. Numărul real este mai mic cu unu.
• Unii din voi ați lucrat pe long long. Nenecesar.
• Mulți uitați să includeți ctype.h pentru funcțiile isdigit() and Co.

Subșirul comun de lungime maximă

Problema subșirul comun de lungime maximă este o aplicație directă a problemei de la curs.

Cel mai lung subşir comun

Problema cel mai lung subşir comun este o aplicație directă a problemei de la curs.

Rezolvări aici [1].

Lecție

<html5media height="720" width="1280">https://www.algopedia.ro/video/2019-2020/2020-02-20-clasa-7-lectie-info-23-720p.mp4</html5media>

Programare dinamică, continuare

Problema rucsacului

Atenție: veți avea la temă ca aplicație problema rucsac1.

Se dă o mulţime formată din N obiecte, fiecare avînd o greutate şi o valoare. Într-un rucsac putem încărca o greutate maxim G. Ne dorim să încărcăm rucsacul cu obiecte astfel încît să maximizăm valoarea totală.

Problema este una foarte practică, ne dorim să optimizăm raportul valoare/greutate, încărcînd obiecte cît mai valoroase, dar cît mai ușoare.

Exemplu

Să presupunem că avem următoarele obiecte:

Nr.	1	2	3	4	5	6
Greutate	3	3	1	1	2	1
Valoare	7	4	2	9	4	5

Rucsacul are mărime 10. Care este valoarea maximă a obiectelor ce pot fi încărcate în rucsac?

Singura posibilitate este să alegem obiectele { 1, 2, 4, 5, 6 }. Ele au greutatea totală 10 și valoarea totală 29.

Încercarea 1: după obiecte

Definirea problemei de programare dinamică nu este evidentă. Voi încerca să arăt un mod de gîndire posibil, care implică mai multe posibilități pe care le vom verifica și apoi elimina, ajungînd în final la o definire bună a problemei.

Să definim

V[i] = valoarea maximă ce se poate obține cu primele i greutăți, astfel încît greutatea totală să nu depășească G

Are V[i] proprietatea de optimalitate a subproblemelor?

Să considerăm o soluție optimă, V[i]. Ea va conține unele din primele i obiecte. Ultimul obiect este obiectul k ≤ i. Atunci este V[k] optimă?

Nu neapărat! Este posibil să găsim o soluție V[k] cu valoare mai mare, dar pe care să nu o putem folosi în construcția problemei V[i] deoarece am depăși greutatea.

Concluzie: nu putem folosi programarea dinamică cu o astfel de definire a problemei.

Încercarea 2: după greutatea totală

Să facem o altă încercare. Să definim

V[g] = valoarea maximă ce se poate obține într-un rucsac de mărime g

Are V[g] proprietatea de optimalitate a subproblemelor?

Să considerăm o soluție optimă, V[g]. Ea va conține unele obiecte, a căror sumă a greutăților nu depășește g. Fie ultimul obiect folosit obiectul k ce are greutate G_k. Este V[g-G_k] optimă?

Răspunsul este: nu, deoarece s-ar putea ca optimul să includă V[g] (pe care nu avem voie să o folosim de două ori).

Concluzie: nu putem folosi programarea dinamică nici cu această definire a problemei.

Încercarea 3: după obiecte și greutate totală

Să încercăm să combinăm cele două încercări de mai sus. Să definim

V[i][g] = valoarea maximă ce se poate obține cu primele i greutăți într-un rucsac de mărime g

Are V[i][g] proprietatea de optimalitate a subproblemelor?

Să considerăm o soluție optimă V[i][g]. Fie ultimul obiect folosit obiectul k ce are greutate G_k. Este V[k][g-G_k] optimă? Să presupunem că nu ar fi. Atunci am putea găsi o valoare mai mare, folosind primele k obiecte ce vor încăpea în greutatea g-G_k. Putem folosi această valoare pentru a obține o valoare mai mare pentru problema originală, V[i][g].

Concluzie: putem folosi programarea dinamică cu această definiție a problemei.

Construim formula de recurență. Pentru a calcula V[i][g] avem două variante:

• Fie nu folosim greutatea G_i, caz în care vom obține valoarea V[i-1][g] (aceeași greutate, dar folosind primele i-1 obiecte).
• Fie folosim greutatea G_i, caz în care vom obține valoarea V[i-1][g-G_i] + P_i (greutatea este cea care rămîne în rucsac după ce folosim G_i, și apoi putem folosi primele i-1 obiecte).

$V[i][g]={\begin{cases}0,&{\mbox{dacă }}i=0{\mbox{ sau }}g=0\\max(V[i-1][g],V[i-1][g-G_{i}]+P_{i})&{\mbox{în caz contrar}}.\end{cases}}$

Unde (G_i, P_i) sînt greutatea, respectiv valoarea obiectului i.

Răspunsul la problemă este elementul V[N][G].

Exemplu

Fie obiectele din exemplul de mai sus:

Nr.	1	2	3	4	5	6
Greutate	3	3	1	1	2	1
Valoare	7	4	2	9	4	5

Vom completa, pe linii, următorul tabel:

Obiect	0	1	2	3	4	5	6	7	8	9	10
0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	7	7	7	7	7	7	7	7
2	0	0	0	7	7	7	11	11	11	11	11
3	0	2	2	7	9	9	11	13	13	13	13
4	0	9	11	11	16	18	18	20	22	22	22
5	0	9	11	13	16	18	20	22	22	24	26
6	0	9	14	16	18	21	23	25	27	27	29

Analiză

Acest algoritm are complexitate O(N·G). Memoria folosită este O(G) dacă memorăm doar o linie din matrice. Dacă dorim să aflăm și o soluție maximală (obiectele din componența soluției), nu doar mărimea ei, vom avea nevoie de memorie O(N·G), precum vom vedea mai jos.

Există un algoritm care reduce necesarul de memorie la O(G).

Reconstrucția soluției

Dorim să aflăm nu doar valoarea maximă, ci și obiectele selectate. Cum procedăm?

Pentru a putea reconstrui soluția vom memora în fiecare căsuță, direcția din care provine ea, adică din care am calculat acel maxim. Direcția poate fi spre stînga-sus sau spre în sus. Apoi vom porni din elementul V[N][G] și vom urma aceste direcții pînă ce ieșim din matrice. De fiecare dată cînd urmăm o diagonală reținem obiectul selectat, care este chiar rîndul curent. Astfel, descoperirea obiectelor se face în ordine inversă.

Distanța edit (Levenshtein)

Atenție: veți avea această problemă la temă.

Se dau două șiruri de caractere, X și Y. Putem efectua trei operațiuni asupra șirului X:

• Inserare caracter la orice poziție
• Ștergere caracter la orice poziție
• Suprascriere - înlocuire a unui caracter cu un alt caracter

Care este numărul minim de operații asupra șirului X care îl transformă în șirul Y?

Definim distanța edit ca fiind acest număr minim de operații. Deoarece operațiile sînt unele frecvente într-un editor de texte, de aici vine și denumirea de distanță edit.

Exemplu

Acest exemplu este inspirat de la wikipedia.

Fie șirurile:

X: KITTEN

Y: SITTING

Numărul minim de operații pentru a transforma X în Y este 3. De exemplu:

1. Înlocuim K cu S: KITTEN → SITTEN
2. Înlocuim E cu I: SITTEN → SITTIN
3. Adăugăm la final un G: SITTIN → SITTING

Soluție

Problema este aproape identică cu subsecvența maximală comună a două șiruri. Vom defini:

D(i, j) = numărul minim de operații ce transformă șirul X[1..i]] în șirul Y[1..j]

Nu voi face demonstrația optimalității subproblemelor, deoarece este similară cu ce de la subsecvența maximală comună a două șiruri.

Obținem relația de recurență:

$\qquad \operatorname {D} _{X,Y}(i,j)={\begin{cases}\max(i,j)&{\text{ dacă }}\min(i,j)=0,\\\min {\begin{cases}\operatorname {D} _{X,Y}(i-1,j)+1\\\operatorname {D} _{X,Y}(i,j-1)+1\\\operatorname {D} _{X,Y}(i-1,j-1)+X_{i}\neq Y_{j}\end{cases}}&{\text{ în caz contrar.}}\end{cases}}$

Distanța edit între cele două șiruri este D(m, n).

Analiză

Acest algoritm are complexitate O(m·n), unde m și n sînt lungimile șirurilor. Memoria folosită este O(min(m, n)) dacă memorăm doar o linie din matrice. Dacă dorim să aflăm și operațiile efectuate, nu doar numărul lor, vom avea nevoie de memorie O(m·n), precum vom vedea mai jos.

Există un algoritm care reduce necesarul de memorie la O(min(m, n)) chiar și cu reconstrucția soluției.

Reconstrucția soluției

Dorim să aflăm nu doar distanța dintre cele două șiruri, ci și o secvență de operații. Cum procedăm? În mod similar cu subsecvența maximală comună.

Pentru a putea reconstrui soluția vom memora în fiecare căsuță din matrice direcția din care provine ea, adică din care am calculat acel maxim. Direcția poate fi spre stînga, spre sus, sau în diagonală stînga-sus. Apoi vom porni din elementul D[m][n] și vom urma aceste direcții pînă ce ieșim din matrice. Astfel:

• Direcția spre stînga înseamnă o inserare de caracter.
• Direcție spre sus înseamnă o ștergere de caracter.
• Direcția diagonală înseamnă:
  • O suprascriere dacă caracterele respective sînt diferite.
  • Nimic (nici o operație) dacă caracterele sînt egale.

Înmulțirea optimală a unui șir de matrice

Se dă un produs matricial de N matrice. Înmulțirea matricelor este asociativă, deci nu contează în ce ordine efectuăm înmulțirile. Dar numărul de operații elementare va diferi în funcție de ordine. Să se găsească o ordine de înmulțire care minimizează numărul de înmulțiri elementare.

Vom discuta pe scurt această problemă, deoarece matematica necesară depășește nivelul clasei a șaptea.

Cei interesați pot rezolva problema:

• pdm

ca aplicație.

Numărare optime prin programare dinamică

Cîte soluții distincte posibile admite o problemă de programare dinamică?

Orice problemă de programare dinamică admite un optim. Soluția optimă nu este, de obicei, unică. Putem, deci, pune întrebarea:

• Care este numărul de soluții optime ale unei probleme de programare dinamică?

Răspunsul se poate da foarte ușor, folosind același tabel cu care calculăm subproblemele. Vom memora, pe lîngă valoarea maximă (sau minimă) și numărul de moduri în care se poate ajunge la ea.

Exemplu: subsecvența crescătoare de lungime maximă

Să luăm exemplul de data trecută:

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

Avem formula de recurență:

L[i] = max(L[j]+1), j > i și V[j] ≥ V[i]

Vom calcula și MAX[i] ca fiind suma tuturor MAX[j] pentru acei indecși j unde relația de maxim este satisfăcută.

Exemplu:

V	0	8	4	12	2	10	6	14	1	9	5	13	3	11	7	15
L	6	4	5	3	5	3	4	2	4	3	3	2	3	2	2	1
MAX	4	7	2	2	2	3	2	1	7	2	3	1	2	1	1	1

Avem, deci, patru secvențe crescătoare de lungime maximală, anume 6. Toate încep cu elementul 0. Două dintre ele continuă cu elementul 4, celelalte două cu elementul 2.

Explicație: elementul curent se poate atașa oricărei secvențe maximale anterior găsite. Dacă o secvență anterioară avea k posibilități de formare, atunci și noile secvențe formate vor fi tot în număr de k. Dacă avem mai multe posibilități de secvențe anterioare, toate vor contribui în egală măsură. De aceea le însumăm.

Discuție: problema rucsacului

Discuție despre cum calculăm numărul de soluții posibile în cazul problemei rucsacului: pe baza relației de recurență calculăm numărul de soluții. El se poate "transfera" de la elementul generator. Sau, în caz că ambele moduri de generare duc la același profit vom însuma numărul de soluții.

Probleme suprapuse (numărare soluții neoptimale)

Există unele probleme care nu cer să se determine un optim, ci să se numere soluții. Ele nu se rezolvă prin programare dinamică, deoarece nu se cere optimul. Ele sînt adesea confundate cu probleme de programare dinamică.

În realitate ele sînt probleme de numărare, folosind structura de probleme suprapuse.

Să luăm cîteva exemple.

Rucsac

Atenție: veți avea această problemă la temă.

Problema rucsac cere să se calculeze cîte subsecvențe distincte (necontigue) au suma egală cu un număr dat.

Problema este echivalentă cu cea a rucsacului: numerele de la intrare reprezintă atît greutatea cît și valoarea obiectelor. Însă trebuie să selectăm obiecte astfel încît suma greutăților să fie exact K, numărul dat.

Exemplu

Fie numerele:

8 3 6 5 2

și numărul dat K = 11.

Vom avea trei subsecvențe distincte a căror sumă este 11:

8 3

3 6 2

6 5

Soluție

Observație importantă:

• Nu putem folosi definiția anterioară a problemei, deoarece ea admite soluții care nu "umplu" exact rucsacul. Aceste soluții nu sînt admisibile.

Vom defini problema ușor diferit:

V[i][g] = valoarea maximă ce se poate obține cu primele i greutăți într-un rucsac de mărime g complet umplut. Valoarea va fi zero dacă nu putem umple greutatea g.

În cazul nostru, deoarece valoarea este egală cu greutatea acea valoare va fi chiar greutatea g. Problema se transformă în există un mod de a forma o greutate g cu primele i obiecte? Răspunsul este unu dacă este afirmativ, sau zero dacă nu se poate forma o greutate. Matricea va fi o matrice de zero și unu.

Formula de recurență se modifică și ea, puțin:

$V[i][g]={\begin{cases}0,&{\mbox{dacă }}i=0{\mbox{ și }}g>0\\1,&{\mbox{dacă }}g=0\\or(V[i-1][g],V[i-1][g-G_{i}])&{\mbox{în caz contrar}}.\end{cases}}$

unde or(x, y) este 1 dacă măcar unul dintre x, y este 1, sau zero în caz contrar.

Pe ultima linie a matricei V vom avea 1 pentru greutățile ce se pot obține.

Acum: cum modificăm soluția să calculeze nu doar dacă o greutate se poate obține, ci în cîte moduri distincte?

Vom calcula:

NSOL[i][g] = numărul de moduri în care putem forma greutatea g folosind primele i numere. Acest număr va fi zero dacă greutatea nu se poate obține.

Formula de recurență este aproape identică cu cea anterioară.

$NSOL[i][g]={\begin{cases}0,&{\mbox{dacă }}i=0{\mbox{ și }}g>0\\1,&{\mbox{dacă }}g=0\\NSOL[i-1][g]+NSOL[i-1][g-G_{i}]&{\mbox{în caz contrar}}.\end{cases}}$

Numărul de moduri în care putem alege numere de sumă K este NSOL[N][K], elementul din colțul din dreapta-jos al matricei NSOL.

Exemplu

Pentru exemplul anterior, avem numerele:

8 3 6 5 2

și numărul dat K = 11.

Vom calcula tabelul:

	0	1	2	3	4	5	6	7	8	9	10	11
0	1	0	0	0	0	0	0	0	0	0	0	0
1	1	0	0	0	0	0	0	0	1	0	0	0
2	1	0	0	1	0	0	0	0	1	0	0	1
3	1	0	0	1	0	0	1	0	1	1	0	1
4	1	0	0	1	0	1	1	0	2	1	0	2
5	1	0	1	1	0	2	1	1	3	1	2	3

Avem, deci, trei moduri de a obține suma 11.

Analiză

Algoritmul are aceeași complexitate în timp și memorie ca și problema originală, anume O(N·K) timp și O(K) memorie, dacă memorăm doar o linie a matricei.

Cifreco

Atenție: veți avea această problemă la temă.

Problema cifreco a fost dată la ONI 2012 baraj gimnaziu. Deși se poate rezolva cu alte metode, ea are o rezolvare foarte eficientă și simplu de implementat folosind numărarea prin probleme suprapuse.

Problema cere ca, dîndu-se două numere x și y, să se găsească cîte numere există între aceste valori cu proprietățile:

• Au N cifre, tot atîtea cifre cîte au și numerele x și y.
• Suma cifrelor lor este N+8 (la fel ca și x și y).

Soluție

Să ne propunem mai întîi să rezolvăm o problemă mai simplă: cîte numere de N cifre au suma cifrelor N+8? Cu alte cuvinte nu vom ține cont de valorile x și y.

Descompunerea în subprobleme suprapuse nu este foarte evidentă. Vom introduce o dimensiune auxiliară: vom varia suma cifrelor. Astfel, definim:

NSOL[N][S] = numărul de numere de N cifre a căror sumă este S.

Ce formulă de recurență avem?

Cum se poate forma un număr de N cifre? Punînd pe prima poziție toate cifrele permise și apoi formînd un număr cu N-1 cifre. Vom avea, deci:

NSOL[N][S] = NSOL[N-1][S-1] + NSOL[N-1][S-2] + ... + NSOL[N-1][N-1]

Astfel:

• Primul termen este numărul de numere care încep cu 1
• Al doilea termen este numărul de numere care încep cu 2
• ...
• Ultimul termen este numărul de numere care încep cu S - N + 1, aceasta fiind cea mai mare cifră pentru care cifrele rămase mai pot forma suma N-1.

Am putea să pornim la implementare. Însă mai putem face o optimizare. Să observăm că, conform definiției:

NSOL[N][S-1] = NSOL[N-1][S-2] + ... + NSOL[N-1][N-1]

De aici rezultă o formulă mai simplă de calcul pentru NSOL[N][S]:

NSOL[N][S] = NSOL[N-1][S-1] + NSOL[N][S-1]

Vom completa acest tabel pentru valori maxime. Astfel vom putea răspunde în O(1) la întrebări de forma:

• Cîte numere de N cifre au suma S?

Acum revenim la problema noastră. Trebuie să calculăm cîte numere de N cifre au suma N+8 între x și y. Cum o rezolvăm?

Ne propunem să calculăm cîte numere sînt mai mici sau egale cu k. Fie, de exemplu, k = 623. Vom proceda astfel:

• Vom calcula cîte numere încep cu 1 și au suma cifrelor 11. Ele sînt toate mai mici strict ca 623. Vom folosi NSOL[2][10].
• Vom calcula cîte numere încep cu 2 și au suma cifrelor 11. Vom folosi NSOL[2][9].
• ...
• Vom calcula cîte numere încep cu 5 și au suma cifrelor 11. Vom folosi NSOL[2][6].

În acest moment ne-au rămas doar numere care încep cu 6. Cîte vor fi ele? Atîtea cîte numere există mai mici ca 23, a căror sumă a cifrelor să fie 5. Reluăm, deci, problema de mai sus cu alți parametri, continuînd să adunăm.

Putem acum calcula

NN(k) = numărul de numere mai mici sau egale cu un număr k.

Pentru a răspunde la problemă vom calcula:

NN(x, y) = NN(y) - NN(x) + 1

Ce complexitate are această soluție?

• Calculul tabelului este O(N·Σ) - un număr foarte mic, circa 162. Mărimea tabelului va fi aceeași.

• Calculul răspunsului necesită o plimbare prin cifre, efectuată pentru fiecare cifră a numărului x sau y. Este, deci O(suma cifrelor) = O(N) - un număr și mai mic, circa 54.

Aveți această problemă la temă.

Atenție! Calculul numărului de numere mai mici sau egale cu k se poate face mai ușor pornind de la cea mai din dreapta cifră, în loc de cea mai din stînga. Ideea este aceeași, doar ordinea de calcul se inversează.

Șir2

Problema șir2 este o problemă tipică de numărare folosind probleme suprapuse. Ne vom ocupa doar de al doilea subpunct care cere să se calculeze în cîte feluri se poate scrie un număr N ca sumă de M numere nenule. Ordinea termenilor contează.

Vom avea o recurență similară cu cea de la cifreco:

NSOL[M][S] = numărul de secvențe de numere nenule de lungime M a căror sumă este S.

Recurența nu este foarte grea. Similar cu cifreco avem:

NSOL[M][S] = NSOL[M-1][S-1] + NSOL[M-1][S-2] + ... + NSOL[M-1][M-1]

Astfel:

• Primul termen este numărul de secvențe care încep cu 1.
• Al doilea termen este numărul de secvențe care încep cu 2.
• ...
• Ultimul termen este numărul de secvențe care încep cu S-M+1, aceasta fiind cel mai mare număr pentru care cifrele rămase mai pot forma suma M.

La fel ca la cifreco, putem reduce această recurență la una mai simplă:

NSOL[M][S] = NSOL[M-1][S-1] + NSOL[M][S-1]

Soluția problemei va fi elementul NSOL[M][N].

Observații:

• Aveți grijă la calcule, ele trebuie făcute modulo 104729.
• Din toate elementele unei sume putem scădea 1. Obținem un șir de elemente naturale, posibil nule, a căror sumă echivalentă trebuie micșorată cu M.
• Astfel, problema se simplifică dacă:
  • Considerați că numerele pot fi nule
  • Reduceți suma cerută, N, înlocuind-o cu N-M.
  • Numărul de posibilităti rămîne același, dar tabelul se simplifică.

Ce complexitate are acest algoritm?

El este O(M·(N-M)) ca timp și memorie.

Tema

• Tema 23 clasa a 7^a
  • rucsac1 ca aplicație la problema rucsacului.
  • șiruri2 ca aplicație la distanța edit.
  • rucsac ca aplicație de numărare cu probleme suprapuse
  • cifreco dată la ONI 2012 baraj gimnaziu, ca aplicație de numărare cu probleme suprapuse
• Cele două probleme de la concurs se vor adăuga la temă
• Opţional: Tema 23 clasa a 7^a opţională
  • pdm ca aplicație la înmulțirea optimală de matrice
  • cutii problemă simpatică

Rezolvări aici [2]