Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-09-11 12:56:53.
Revizia anterioară   Revizia următoare  

Solutii runda 1

Banuti

Notam cu min valoarea minima. Se observa ca pentru o suma oarecare s, daca toate sumele din intervalul (s,s+min] pot fi obtinute, atunci toate sumele > s pot fi obtinute la randul lor. (Pentru a va convinge, in caz ca aveti neclaritati, simulati un knapsack). Se construieste un graf cu min noduri, nodul x semnificand restul x la impartirea cu min. Se defineste cost[x], suma minima care poate fi obtinuta (s), cu proprietatea ca s%min=x (restul impartirii sumei la min este x); cost[0]=0. Se observa ca daca putem obtine o suma s, atunci putem obtine toate sumele s+k*min (care au acelasi rest), unde k>0. In acest graf fiecare bancnota (de valoare v), formeaza o muchie intre nodul y si nodul (y+v)%min, cu costul v, unde y apartine [0,min). Daca acest graf nu este conex atunci nu avem solutie. Daca este conex, atunci solutia se afla in max(cost[x]), x apartine [0,min), care poate fi aflata cu Dijkstra. Mentionez faptul ca graful ar avea teoretic N*min muchii. Pe cazul general, N>min, deci unele muchii sunt in plus (conform principiului cutiei). Graful pe care se face rezolvarea ar trebui sa aiba ≈min2 muchii. Complexitatea finala este O(min2).

Renovare

Vom reduce problema la flux maxim de cost minim astfel: pentru fiecare muchie a b c cst cu semnificatia din enunt vom adauga 2 muchii in fisierul de intrare, una de capacitate c si cost 0 si inca una de capacitate infinit si cost cst. De asemenea vom conecta nodul 1 la o sursa auxiliara printr-o muchie de capacitate x si cost 0. Apoi se rezolva facand flux maxim de cost minim in reteaua noua.

Plan

Construim graful componentelor tare conexe si in continuare ne vom referi numai la acest graf.
Plasam in multimea X nodurile cu grad de intrare 0, iar in multimea Y gradurile cu nod de iesire 0. Vom gasi in continuare un mod de a construi max(cardX, cardY) sosele si este clar ca acest numar e minim deoarece din fiecare nod din X trebuie sa intre macar o muchie, iar din fiecare nod din Y trebuie sa iasa macar o muchie. In continuare ne vom construi un set maximal (atentie, maximal != maxim) de perechi (x1, y1), (x2, y2) ... (xk, yk) astfel incat x1, x2 .. xk apartin lui X iar y1, y2.. yk apartin lui Y. Mai mult exista drum in graf de la xi la yi. Adaugam muchie de la y1 la x2, y2 la x3 ... yk la x1.
In continuare adaugam muchii de la fiecare nod ramas din Y la un nod din X pana cand vom avea noduri doar in X sau doar in
Y. Pentru acele noduri adaugam o muchie de la ele la x1 sa zicem, sau de la x1 la ele in functie daca sunt din X sau din Y.
Am adaugat cate muchii ne-am propus, acum sa vedem daca respecta proprietatea ca avem un drum de la orice nod la orice nod.
Dupa ce am construit acel set maximal si practic am construit un ciclu adaugand muchiile, nodurile care au mai ramas din
multimea X au drum de la ele la un nod din ciclu, iar cele din multimea Y ramase au drum de la un nod din ciclu la ele.
Deci cand consideram doua noduri A si B, cu A din X si B din Y dintre cele care au ramas dupa alegerea nodurilor din setul
maximal, si tragem muchie de la B la A vom avea drum de la nodurile din ciclu la A, la B si de la ele la nodurile din ciclu.

Numar de Divizori