Olimpiade Sains Provinsi (OSP) 2017 - Komputer, Nomor 12

Saya perjelas dulu maksud soalnya
Saat mengambil 7 tanaman, akan terdapat loncatan terpendek. Kita ingin loncatan terpendek ini semaksimal mungkin.

Sebagai contoh, saya tunjukkan 3 kemungkinan pengambilan (kemungkinan pengambilan seluruhnya ada 15C7 = 6435 kemungkinan)

Pada pengambilan pertama, loncatan terpendek = 7
Pada pengambilan kedua, loncatan terpendek = 5
Pada pengambilan ketiga, loncatan terpendek = 22
Pada tiga kemungkinan tersebut, loncatan terpendek yang paling maksimal adalah 22

Kita ingin mencari loncatan terpendek yang paling besar dari semua kemungkinan.

Agar loncatan terpendeknya semaksimal mungkin, maka Cici perlu loncat sejauh mungkin. Tetapi karena pengambilan pertama dibatasi oleh tanaman paling kiri, dan pengambilan terakhir dibatasi tanaman paling kanan, maka agar maksimal kita perlu membuat loncatannya se-rata mungkin.

Rata-rata dari 6 loncatan dari ujung kiri ke ujung kanan adalah

Sehingga kita usahakan loncatannya mendekati

Dengan mengambil secara greedy yaitu dengan melakukan loncatan dari ujung kiri dan ujung kanan dengan mengusahakan panjang loncatan >= 48.5 tapi tidak terlalu jauh, kita akan dapatkan loncatan seperti ini :

Dari cara greedy ini diperoleh loncatan terpendeknya adalah 38. Hasil ini cukup besar. Tapi apakah ini yang terbesar?
Untuk membuktikannya kita perlu menunjukkan bahwa tidak mungkin membuat loncatan terpencek 39. Caranya adalah lakukan loncatan-loncatan dengan jarak >= 39. Pada loncatan terakhir tidak mungkin dibuat loncatan dengan jarak >= 39. Dan artinya, terbukti secara kontradiksi bahwa 39 tidak mungkin diperoleh dan jelas di atas 39 juga tidak mungkin. Sehingga 38 adalah paling maksimal.

Jawaban = 38

Untuk membuktikan dengan program, kita buat program brute force untuk menghitung loncatan terpendek untuk semua kemungkinan, cari yang terbesar
https://ideone.com/LBfjmC