Olimpiade Sains Provinsi (OSP) 2025 - Komputer, Nomor 17–20

Apabila Pak Dengklek tidak dapat memangkas bambu-bambunya (dengan kata lain, nilai K = 0) dan setiap ikat bambu harus terdiri dari setidaknya 3 bilah bambu, manakah dari 5 skenario berikut yang memungkinkan Pak Dengklek untuk menjual seluruh bambunya dan dengan banyaknya ikat bambu yang dijual paling banyak?

1. Pak Dengklek akan menjual 14 bilah bambu dengan panjang [1, 2, 3, 4, 5, 6, 7, 7, 6, 5, 4, 3, 2, 1]
2. Pak Dengklek akan menjual 14 bilah bambu dengan panjang [2, 3, 4, 2, 3, 4, 2, 3, 4, 2, 3, 4, 2, 3]
3. Pak Dengklek akan menjual 14 bilah bambu dengan panjang [5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8]
4. Pak Dengklek akan menjual 14 bilah bambu dengan panjang [8, 7, 8, 7, 8, 7, 8, 7, 8, 7, 8, 7, 8, 7]
5. Pak Dengklek akan menjual 14 bilah bambu dengan panjang [1, 1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 6, 6]

BENAR atau SALAH: Pada kasus-kasus yang memungkinkan Pak Dengklek untuk menjual seluruh bambu, maka untuk memaksimumkan banyaknya ikat bambu yang dapat Pak Dengklek jual, setiap ikat bambu pasti terdiri dari kurang dari 2 × M bilah bambu.

Pak Dengklek akan menjual 18 bilah bambu dengan panjang sebagai berikut:

[1, 1, 3, 3, 4, 5, 6, 7, 8, 9, 9, 13, 13, 14, 14, 14, 15, 16]

Apabila Pak Dengklek dapat memangkas bambu-bambunya agar panjangnya berkurang paling banyak 2 satuan, maka berapakah banyaknya ikat bambu maksimum yang dapat Pak Dengklek jual jika setiap ikat bambu harus terdiri dari setidaknya 3 bilah bambu dan Pak Dengklek harus menjual seluruh bambunya?

Jika ternyata tidak mungkin menjual seluruh bambunya, jawablah dengan -1.

Tuliskan jawaban dalam bentuk ANGKA.

TEBAS TEBANG BAMBU

Tulislah sebuah program dengan bahasa C++ sesuai deskripsi cerita dengan format dan batasan sebagai berikut. Perhatikan bahwa untuk setiap kasus uji berlaku time limit selama 3 detik dan memory limit sebanyak 256 MB.

Format Masukan:
Masukan diberikan dalam format berikut:

N M K
A_1 A_2 ... A_N

Format Keluaran:
Keluarkan sebuah baris berisi sebuah bilangan bulat yang menyatakan banyaknya ikat bambu maksimum yang dapat Pak Dengklek jual apabila harus menjual seluruh bambunya. Jika Pak Dengklek tidak mungkin menjual seluruh bambunya, keluarkan -1.

Contoh Masukan dan Keluaran:

9 3 0
2 5 3 5 6 5 3 5 2

-1

9 3 1
2 5 3 5 6 5 3 5 2

2

9 3 3
2 5 3 5 6 5 3 5 2

3

Penjelasan Contoh

Pada contoh pertama, Pak Dengklek tidak dapat memangkas bambu-bambunya. Alhasil, ia hanya dapat membuat 1 ikat bambu saja berisikan 3 atau 4 bilah bambu dengan panjang 5. Namun, Pak Dengklek tidak dapat menjual seluruh bambunya karena bambu-bambu lainnya tidak dapat membentuk ikat bambu. Oleh karena itu, keluarannya adalah -1.

Pada contoh kedua, Pak Dengklek dapat memangkas bambu ke-3, ke-5, dan ke-7 sehingga panjang tiap bambu secara berturut-turut menjadi [2, 5, 2, 5, 5, 5, 2, 5, 2]. Pak Dengklek kemudian dapat membuat 2 ikat bambu: satu berisikan 4 bilah bambu dengan panjang 2, dan satu lagi berisikan 5 bilah bambu dengan panjang 5. Perhatikan bahwa dengan menjual 2 ikat bambu tersebut, Pak Dengklek akan menjual seluruh bambunya.

Pada contoh ketiga, Pak Dengklek bisa saja memangkas bambu ke-2 hingga ke-8 sehingga panjang tiap bambu secara berturut-turut menjadi [2, 4, 2, 2, 4, 4, 2, 2, 2]. Pak Dengklek kemudian dapat membuat 3 ikat bambu: dua ikat masing-masing berisikan 3 bilah bambu dengan panjang 2, dan satu lagi berisikan 3 bilah bambu dengan panjang 4.

Batasan

• 2 ≤ M ≤ N ≤ 200 000
• 0 ≤ K ≤ 10⁹
• 1 ≤ A_i ≤ 10⁹

Batasan Tambahan untuk Subsoal 1 (Mudah)

• M ≤ 20

Batasan Tambahan untuk Subsoal 2 (Sulit)

Tidak ada batasan tambahan pada subsoal ini.