Olimpiade Sains Provinsi (OSP) 2025 - Komputer, Nomor 13–16
Deskripsi Untuk Soal Nomor 13 dan 16
Studi Kasus D. Telur Kemasan Balado
Setelah menjadi juragan telur, Pak Dengklek ingin mengembangkan usahanya untuk berjualan telur rebus kemasan. Ada dua varian telur milik Pak Dengklek: varian Asli yakni telur tanpa bumbu apa pun, dan varian Balado yang merupakan telur dengan bumbu pedas.
Pak Dengklek sudah memproduksi N telur yang ditata dari kiri ke kanan. Penataan tersebut dapat direpresentasikan sebagai sebuah string S sepanjang N yang hanya terdiri dari huruf ‘A’ dan ‘B’. Huruf ‘A’ menunjukkan telur varian Asli, sedangkan huruf ‘B’ menunjukkan telur varian Balado.
Suatu hari, Pak Dengklek mendapatkan kabar bahwa Raja Bebek ingin memborong seluruh telur milik Pak Dengklek. Namun, Raja Bebek hanya ingin membeli telur varian Balado saja. Alhasil, Pak Dengklek ingin menyembunyikan nol atau lebih telur dengan operasi berikut:
Pak Dengklek akan memilih telur terkiri (sebut saja telur pada posisi l) dan telur terkanan (sebut saja telur pada posisi r) yang akan disembunyikan.
Pak Dengklek akan menyembunyikan seluruh telur yang berada pada rentang tersebut (dari posisi l hingga r inklusif).
Pak Dengklek akan menata ulang telur-telur sisanya menjadi satu kesatuan dari kiri ke kanan tanpa mengubah urutannya.
Dengan waktu yang tersisa, Pak Dengklek dapat melakukan operasi di atas paling banyak sebanyak K kali (mungkin saja tidak sama sekali). Pada akhirnya, Pak Dengklek harus menjamin bahwa seluruh telur yang tersisa adalah telur varian Balado.
Bantulah Pak Dengklek untuk menentukan paling banyak telur varian Balado yang mungkin dapat Raja Bebek borong!
13.
Apabila Pak Dengklek hanya boleh melakukan operasi penyembunyian paling banyak 1 kali, manakah dari 5 pilihan string S berikut yang memungkinkan Raja Bebek memborong telur varian Balado paling banyak?
- “BBBBB”
- “BBAABBBB”
- “AAAAABBBB”
- “BABBBBBBBBAB”
- “AABBBAABABBBABBB”
14.
Apabila penataan telur direpresentasikan dengan string “BAABBBAAAABBBBAAABBA”, dengan melakukan operasi penyembunyian paling banyak 2 kali, berapakah banyaknya telur varian Balado terbanyak yang mungkin dapat Raja Bebek borong?
Tuliskan jawaban dalam bentuk ANGKA.
15.
Apabila penataan telur direpresentasikan dengan string “BAABBBAAAABBBBAAABBA”, dengan melakukan operasi penyembunyian paling banyak 3 kali, berapakah banyaknya telur varian Balado terbanyak yang mungkin dapat Raja Bebek borong?
Tuliskan jawaban dalam bentuk ANGKA.
16.
TELUR KEMASAN BALADO
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 2 detik dan memory limit sebanyak 256 MB.
Format Masukan:
Masukan diberikan dalam format berikut:
N K
SFormat Keluaran:
Keluarkan sebuah baris berisi sebuah bilangan bulat yang menyatakan banyaknya telur varian Balado terbanyak yang mungkin dapat Raja Bebek borong.
Contoh Masukan dan Keluaran:
| Contoh Masukan | Contoh Keluaran |
|---|---|
14 2 BBABAAAABABBB | 6 |
14 4 BBABAAAABABBB | 7 |
4 1000000000 BBBB | 4 |
4 1000000000 AAAA | 0 |
Penjelasan Contoh
Pada contoh pertama, Pak Dengklek dapat melakukan penyembunyian telur seperti pada deskripsi cerita agar Raja Bebek dapat memborong 6 telur varian Balado.
Pada contoh kedua, Pak Dengklek dapat melakukan penyembunyian telur sebagai berikut:
- Dari “BBABAAAABABBB”, sembunyikan telur di posisi 6 hingga 7, tersisa “BBABAABAABBB”.
- Dari “BBABAABAABBB”, sembunyikan telur di posisi 5 hingga 6, menyisakan “BBABBAABBB”.
- Dari “BBABBAABBB”, sembunyikan telur di posisi 3 hingga 3, menyisakan “BBBBBAABBB”.
- Dari “BBBBBAABBB”, sembunyikan telur di posisi 5 hingga 6, menyisakan “BBBBBBB”.
Pada contoh ketiga, karena seluruh telur merupakan varian Balado, Pak Dengklek tidak perlu menyembunyikan telur apa pun.
Pada contoh keempat, karena seluruh telur merupakan varian Asli, Pak Dengklek hanya dapat menyembunyikan seluruhnya sehingga Raja Bebek tidak dapat memborong apa pun.
Batasan
- 1 ≤ N ≤ 200 000
- 1 ≤ K ≤ 109
- S memiliki panjang N dan hanya terdiri dari huruf ‘A’ dan ‘B’
Batasan Tambahan untuk Subsoal 1 (Mudah)
- N ≤ 16
- K ≤ 2
Batasan Tambahan untuk Subsoal 2 (Sulit)
Tidak ada batasan tambahan pada subsoal ini.
0 jawaban
Masuk untuk menulis jawaban