Olimpiade Sains Provinsi (OSP) 2024 - Komputer, Nomor 9–12

Asumsikan terdapat 20 pohon dengan ketinggian sebesar 1, 2, 3, dan seterusnya hingga 20. Apabila Pak Dengklek menebang dengan batas ketinggian maksimum sebesar 7, maka berapa jumlah panjang potongan pohon yang ditebang oleh Pak Dengklek?

Tuliskan jawaban dalam bentuk ANGKA.

BENAR atau SALAH: Untuk setiap kemungkinan pohon-pohon di belakang rumah Pak Dengklek, apabila Pak Dengklek dapat membangun sebuah kandang jika ia menebang dengan batas ketinggian maksimum sebesar Z dengan Z > 0, maka Pak Dengklek juga pasti dapat membangun sebuah kandang jika ia menebang dengan batas ketinggian maksimum sebesar Z – 1.

Asumsikan terdapat 10 pohon dengan ketinggian sebesar 10, 20, 30, dan seterusnya hingga 100. Apabila Pak Dengklek membutuhkan minimal jumlah panjang potongan pohon yang ditebang sebesar 111, berapakah batas ketinggian maksimum yang paling tinggi yang dapat dipilih oleh Pak Dengklek?

Tuliskan jawaban dalam bentuk ANGKA.

TEBAS TEBANG POHON

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

Format Masukan:

N M
A1 A2 ... AN

Format Keluaran:
Keluarkan sebuah baris berisi sebuah bilangan bulat yang menyatakan batas ketinggian maksimum yang paling tinggi yang dapat dipilih oleh Pak Dengklek sehingga ia tetap dapat membangun sebuah kandang untuk bebek-bebeknya. Jika Pak Dengklek tidak mungkin dapat membangun sebuah kandang untuk bebek-bebeknya berapa pun batas ketinggian maksimum yang ia pilih, keluarkan -1.

Contoh Masukan dan Keluaran:

10 25
4 2 9 9 5 3 6 7 2 10

3

5 5
2 7 2 9 5

5

5 25
2 7 2 9 5

0

5 125
2 7 2 9 5

-1

Penjelasan Contoh:

Pada contoh pertama, penebangan pohon Pak Dengklek dapat disimak kembali pada ilustrasi pada deskripsi cerita. Jumlah panjang potongan adalah 1+6+6+2+3+4+7 = 29 sehingga cukup bagi Pak Dengklek untuk membangun kandang.

Pada contoh kedua, Pak Dengklek dapat memilih batas ketinggian maksimum sebesar 5, sehingga ia akan menebang pohon ke-2 dan mendapatkan sebuah potongan sepanjang 7 – 5 = 2 serta menebang pohon ke-4 dan mendapatkan sebuah potongan sepanjang 9 – 5 = 4. Jumlah panjang potongan adalah 2+4 = 6 sehingga cukup bagi Pak Dengklek untuk membangun kandang.

Pada contoh ketiga, perhatikan bahwa Pak Dengklek bisa saja memilih batas ketinggian maksimum sebesar 0, yang artinya Pak Dengklek akan menebang habis seluruh pohon untuk membangun kandang.

Pada contoh keempat, bagaimana pun Pak Dengklek menebang pohon-pohon di belakang rumahnya, ia tetap tidak dapat membangun sebuah kandang untuk bebek-bebeknya.

Batasan:

Untuk seluruh kasus uji berlaku:

• 1 ≤ N ≤ 100 000
• 1 ≤ M ≤ 10¹²
• 1 ≤ A_i ≤ 1 000 000

Batasan Tambahan untuk Subsoal 1 (Mudah)
Pada subsoal ini, untuk seluruh kasus uji berlaku:

• N ≤ 1000
• A_i ≤ 1000

Batasan Tambahan untuk Subsoal 2 (Sulit)
Tidak ada batasan tambahan pada subsoal ini.

Peringatan: Untuk dapat menjawab pertanyaan ini dengan benar, Anda mungkin perlu menggunakan tipe data long long untuk dapat menyimpan data dengan nilai yang besar. Tipe data int saja mungkin tidak cukup!