Xırda Pul Dəyişimi
Orta
Dynamic ProgrammingGreedy
3000 ms
256 MB
Fərqli nominallı sikkələr (istənilən sayda istifadə edilə bilər) və amount məbləği verilib. amount məbləğini toplamaq üçün lazım olan minimum sikkə sayını tapın, mümkün deyilsə -1 çap edin.
Giriş verilənləri
Birinci sətirdə n (sikkə növlərinin sayı) və amount. İkinci sətirdə n müsbət tam ədəd (sikkə nominalları).
Çıxış verilənləri
Minimum sikkə sayını (və ya -1) çap edin.
1Nümunə 1:
Giriş:
3 11
1 2 5
Çıxış:
3
İzah:11 = 5+5+1 → 3 sikkə
2Nümunə 2:
Giriş:
1 3
2
Çıxış:
-1
İzah:3-ü 2-lərlə toplamaq mümkün deyil → -1
Məhdudiyyətlər
1 ≤ n ≤ 20
1 ≤ amount ≤ 5000
1 ≤ nominal ≤ amount
REDAKTOR
Giriş edin
Kodu yoxlamaq üçün "Göndər" düyməsinə basın
Giriş:
3 11
1 2 5
Çıxış:
3