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. 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) deci graful real ar trebui sa aiba ~min² muchii. Complexitatea finala este O(min²).

Renovare

Plan

Numar de Divizori