19:I[83391,["/_next/static/chunks/01ctw1akxhipf.js","/_next/static/chunks/0es-u.8d.mnrl.js","/_next/static/chunks/0dy1a2.mvnkkn.js","/_next/static/chunks/1490m.ueos6wm.js","/_next/static/chunks/0e0r8s6q6rqo3.js","/_next/static/chunks/06ql-volcxfrm.js"],"ProblemWorkspace",1] 1d:I[27201,["/_next/static/chunks/01xlw8hd842-c.js","/_next/static/chunks/0-mla.nmfqw.d.js"],"IconMark"] 1a:T419,Consideram urmatorul algoritm lacom de acoperire a unei sume de bani, folosind bancnotele disponibile: Cat timp suma este neacoperita si exista o bancnota de valoare mai mica sau egala cu suma ramasa, se alege cea mai mare astfel de bancnota, se scoate din portofel, si suma ramasa se reduce cu valoarea ei. Daca algoritmul se incheie cu suma 0, a reusit, altfel a esuat. Pentru o configuratie de tipuri de bancnote disponibile (fiecare tip putand fi folosit de oricate ori), poate exista o suma S pentru care algoritmul lacom esueaza, desi exista o combinatie de bancnote care acopera exact suma S (adica exista o solutie cu mai putine bancnote decat gaseste algoritmul lacom, sau algoritmul lacom se blocheaza complet). O astfel de suma se numeste contraexemplu. Se citesc k tipuri de bancnote (intre care se afla obligatoriu si valoarea 1) si un numar M. Fie S_min cea mai mica suma de acoperit care constituie un contraexemplu pentru algoritmul lacom, folosind exact aceste tipuri de bancnote. Determinati restul lui S_min la impartirea cu M.1b:T413,#include using namespace std; const int LIMIT = 3000; int main(){ int k; long long M; cin >> k >> M; vector denom(k); for (int i = 0; i < k; i++) cin >> denom[i]; sort(denom.begin(), denom.end()); const long long INF = 4000000000LL; vector optim(LIMIT + 1, INF); optim[0] = 0; for (int s = 1; s <= LIMIT; s++) { for (int i = 0; i < k; i++) { if (denom[i] <= s && optim[s - denom[i]] + 1 < optim[s]) { optim[s] = optim[s - denom[i]] + 1; } } } long long sMin = -1; for (int s = 1; s <= LIMIT; s++) { long long remaining = s; long long greedyCount = 0; for (int i = k - 1; i >= 0; i--) { while (remaining >= denom[i]) { remaining -= denom[i]; greedyCount++; } } if (greedyCount != optim[s]) { sMin = s; break; } } cout << (sMin % M) << "\n"; return 0; } 1c:T413,#include using namespace std; const int LIMIT = 3000; int main(){ int k; long long M; cin >> k >> M; vector denom(k); for (int i = 0; i < k; i++) cin >> denom[i]; sort(denom.begin(), denom.end()); const long long INF = 4000000000LL; vector optim(LIMIT + 1, INF); optim[0] = 0; for (int s = 1; s <= LIMIT; s++) { for (int i = 0; i < k; i++) { if (denom[i] <= s && optim[s - denom[i]] + 1 < optim[s]) { optim[s] = optim[s - denom[i]] + 1; } } } long long sMin = -1; for (int s = 1; s <= LIMIT; s++) { long long remaining = s; long long greedyCount = 0; for (int i = k - 1; i >= 0; i--) { while (remaining >= denom[i]) { remaining -= denom[i]; greedyCount++; } } if (greedyCount != optim[s]) { sMin = s; break; } } cout << (sMin % M) << "\n"; return 0; }