Banyak Cara Tukar Koin
Hitung banyaknya kombinasi koin yang membentuk jumlah tertentu.
Celengan Bayu berisi koin Rp100, Rp200, Rp500, dan Rp1000 dalam jumlah tak terbatas. Ada berapa cara mengambil koin yang totalnya tepat sejumlah tertentu? Urutan pengambilan tidak dibedakan.
Masukan
Baris pertama berisi N (1 sampai 20) dan jumlah J (0 sampai 20000). Baris kedua berisi N nilai koin yang berbeda, masing-masing 1 sampai 10000.
Keluaran
Banyaknya kombinasi, dibagi 1000000007 lalu diambil sisanya.
Contoh masukan dan keluaran
Contoh 1
Masukan
4 1000 100 200 500 1000
Keluaran
11
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Ini mirip soal Partisi Bilangan, hanya saja nilai bagiannya dibatasi pada jenis koin yang ada.
Petunjuk 2
Proses koin satu per satu di perulangan luar, lalu totalnya di perulangan dalam. Kalau perulangannya ditukar, urutan pengambilan ikut terhitung.