Deskripsi Untuk Soal Nomor 14 dan 16
DESKRIPSI CERITA
Pohon kelapa Pak Dengklek sedang mengalami masa pertumbuhan. Masa pertumbuhannya berlangsung dari hari 0 sampai dengan hari N. Pada akhir hari 0, tinggi pohon kelapa adalah M satuan. Pada awal masing-masing hari d (d > 0), tinggi pohon kelapa sama dengan K satuan lebih tinggi dari tingginya pada akhir hari d - 1.
Pak Dengklek mempunyai N botol berisi air ajaib yang dinomori dari 1 sampai N. Setiap botol mempunyai nilai Ai. Selama masing-masing hari d (d > 0), Pak Dengklek harus menyirami pohon kelapanya dengan salah satu botol air ajaibnya hingga habis. Jika Pak Dengklek menyirami dengan air dari botol i pada suatu hari dan tinggi pohon kelapa pada awal hari itu adalah h, maka tingginya akan berubah menjadi max(h, Ai) pada akhir hari tersebut. Setelah sebuah botol dihabiskan, botol itu tidak bisa digunakan lagi untuk menyiram pada hari-hari selanjutnya.
Perhatikan bahwa terdapat dua jenis pertambahan tinggi, yaitu pertambahan tinggi sebesar K satuan pada setiap pergantian hari dan pertambahan tinggi akibat penyiraman yang terjadi di dalam setiap hari.
Suatu botol air ajaib dikatakan berguna jika dan hanya jika menyiram air dari botol tersebut membuat tinggi pohon kelapa bertambah pada hari itu. Berapa maksimum banyaknya botol air ajaib yang berguna jika Pak Dengklek bisa menentukan urutan botol yang digunakan pada urutan penyiraman?
Diberikan N = 4, M = 3, K = 2, dan urutan penyiramannya adalah sebagai berikut:
Berapa banyaknya botol air ajaib yang berguna?
Diberikan N = 4, M = 4, K = 1, dan nilai-nilai masing-masing botol air ajaib adalah 10, 6, 9, dan 11. Berapa maksimum banyaknya botol air ajaib yang berguna jika Pak Dengklek bisa menentukan urutan botol yang digunakan pada urutan penyiraman?
Buatlah program menggunakan bahasa C/C++ sesuai deskripsi cerita di atas untuk menentukan maksimum banyaknya botol air ajaib yang berguna jika Pak Dengklek bisa menentukan urutan botol yang digunakan pada urutan penyiraman, dengan ketentuan sebagai berikut:
Format Masukan:
Baris pertama berisi tiga buah bilangan: N (banyaknya botol air ajaib), M (tinggi pohon kelapa pada akhir hari 0), dan K (seberapa besar tinggi pohon kelapa bertambah untuk setiap pergantian hari). Baris berikutnya berisi N buah bilangan bulat yang menyatakan nilai-nilai A1, A2, A3, …, AN (nilai masing-masing botol air ajaib).
Format Keluaran:
Sebuah baris berisi sebuah bilangan bulat yang menyatakan maksimum banyaknya botol air ajaib yang berguna jika Pak Dengklek bisa menentukan urutan botol yang digunakan pada urutan penyiraman.
Contoh Masukan dan Keluaran:
| Contoh Masukan | Contoh Keluaran |
|---|---|
6 3 2 9 10 10 6 18 16 | 3 |
2 65 0 2 65 | 0 |
Penjelasan Contoh:
Pada contoh pertama, salah satu cara Pak Dengklek bisa membuat supaya terdapat 3 botol air ajaib berguna adalah dengan melakukan hal berikut:
Batasan:
Untuk semua kasus uji berlaku:
Subtask 1 (20%)
Subtask ini hanya berisi satu kasus uji, yaitu sebagai berikut:
10 37 11 107 83 61 140 152 98 72 183 78 41 |
Subtask 2 (30%)
Pada subtask ini, dijamin bahwa:
Subtask 3 (50%)
Tidak ada batasan tambahan.
Masuk untuk menulis jawaban