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.
- Date de intrare
- Pe prima linie se citesc doua numere naturale k si M. Pe a doua linie se citesc k numere naturale distincte, reprezentand valorile bancnotelor disponibile (printre care se afla intotdeauna valoarea 1).
- Date de iesire
- Se afiseaza un singur numar intreg, restul lui S_min la impartirea cu M.
- Restrictii
- 2 <= k <= 10 1 <= valoare bancnota <= 1000 Valoarea 1 se afla intotdeauna printre bancnotele date. Se garanteaza ca S_min exista si este cel mult 3000.
Exemple
Exemplul 1
Intrare
3 97 1 4 6
Iesire
8
Exemplul 2
Intrare
3 1000 1 3 4
Iesire
6