Olimpiade Sains Provinsi (OSP) 2025 - Komputer, Nomor 21–24
Deskripsi Untuk Soal Nomor 21 dan 24
Studi Kasus F. Kandang Ayam Kandang Bebek
Selain beternak bebek, Pak Dengklek juga sekarang beternak ayam. Seluruh ayam dan bebek tersebut berada di dalam pekarangan yang sama berbentuk segiempat berukuran 2 baris dan N kolom. Baris atas dinomori 1 dan baris bawah dinomori 2. Dari kiri ke kanan, kolom-kolom pekarangan dinomori dari 1 hingga N. Petak pada baris x dan kolom y direpresentasikan dengan (x, y).
Kondisi hewan di pekarangan dinyatakan dengan dua buah string, S1 dan S2, sepanjang N yang masing-masing hanya terdiri dari karakter ‘A’, ‘B’, dan ‘.’ (titik). Karakter ke-j pada Si menunjukkan hewan yang mungkin ada pada petak (i, j). Karakter ‘A’ menunjukkan seekor ayam, karakter ‘B’ menunjukkan seekor bebek, dan karakter ‘.’ menunjukkan ketiadaan hewan.
Selain itu, kondisi lahan pekarangan juga dinyatakan dengan sebuah matriks M berukuran 2 × N berisi bilangan bulat positif. Mi,j menyatakan nilai kebecekan lahan pada petak (i, j).
Pak Dengklek juga memiliki sebuah kandang ayam dan sebuah kandang bebek tepat di sebelah kiri pekarangan. Untuk mudahnya, kandang ayam dapat dianggap terletak pada petak (1, 0) dan kandang bebek terletak pada petak (2, 0). Kandang ayam cukup besar untuk menampung seluruh ayam. Kandang bebek pun cukup besar untuk menampung seluruh bebek.
Pada malam hari, seluruh ayam harus pulang ke kandang ayam dan seluruh bebek pun harus pulang ke kandang bebek. Setiap hewan dapat bergerak 4 arah dari posisinya di petak (i, j): ke atas yakni petak (i − 1, j), ke bawah yakni petak (i + 1, j), ke kiri yakni petak (i, j − 1), atau ke kanan yakni petak (i, j + 1). Perhatikan bahwa mereka tidak boleh keluar dari pekarangan (kecuali ke kandang). Rute yang ditempuh oleh seekor hewan didefinisikan sebagai seluruh petak yang dilaluinya termasuk posisi awal hingga sesaat sebelum masuk kandang, yakni ayam diakhiri dengan petak (1, 1) dan bebek diakhiri dengan petak (2, 1).
Karena ayam dan bebek Pak Dengklek belum akur, apabila ada petak yang pernah dilalui oleh setidaknya seekor ayam dan setidaknya seekor bebek, maka akan terjadi perselisihan.
Sebagai contoh, berikut ini adalah ilustrasi kepulangan hewan yang tidak mengakibatkan perselisihan.
Sedangkan berikut ini adalah ilustrasi kepulangan hewan yang mengakibatkan perselisihan karena terdapat 3 petak yang pernah dilalui oleh setidaknya seekor ayam dan setidaknya seekor bebek.
Setiap hewan memiliki nilai kerisihan yang didefinisikan sebagai jumlahan nilai-nilai kebecekan pada seluruh petak yang dilalui oleh rute hewan tersebut. Berapakah total nilai kerisihan paling kecil yang mungkin untuk seluruh hewan pulang ke kandang dengan syarat tidak terjadi perselisihan?
21.
Asumsikan pekarangan Pak Dengklek berukuran 2 baris dan 5 kolom. Manakah dari 5 kondisi hewan di pekarangan berikut yang (mau tidak mau) pasti terjadi perselisihan ketika seluruh hewan pulang ke kandang?
- Ayam berada di petak (1, 5) dan bebek berada di petak (2, 1)
- Ayam berada di petak (1, 2) dan bebek berada di petak (1, 4)
- Ayam berada di petak (2, 5) dan bebek berada di petak (2, 4)
- Ayam berada di petak (1, 2) dan bebek berada di petak (2, 4)
- Ayam berada di petak (1, 4) dan bebek berada di petak (1, 2)
22.
Asumsikan pekarangan Pak Dengklek berukuran 2 baris dan 1000 kolom. Diketahui juga bahwa hanya terdapat tepat 1 ekor ayam dan tepat 1 ekor bebek. Apabila pada petak (2, 500) terdapat seekor ayam, maka ada berapa banyak posisi awal bebek yang mungkin tidak mengakibatkan perselisihan ketika kedua hewan pulang ke kandang?
Tuliskan jawaban dalam bentuk ANGKA.
23.
Asumsikan pekarangan Pak Dengklek berukuran 2 baris dan 6 kolom. Diketahui pula bahwa kondisi lahan pekarangan direpresentasikan dengan matriks M berikut:
Apabila terdapat seekor ayam pada pekarangan tersebut di petak (1, 1) lalu juga ada 4 ekor bebek yang memenuhi kolom 5 hingga 6, atau dengan kata lain berada di petak (1, 5), (1, 6), (2, 5), dan (2, 6); maka berapakah total nilai kerisihan paling kecil yang mungkin untuk kelima hewan pulang ke kandang dengan syarat tidak terjadi perselisihan?
Tuliskan jawaban dalam bentuk ANGKA.
24.
KANDANG AYAM KANDANG BEBEK
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
S_1
S_2
M_1,1 M_1,2 ... M_1,N
M_2,1 M_2,2 ... M_2,NFormat Keluaran:
Keluarkan sebuah baris berisi sebuah bilangan bulat yang menyatakan total nilai kerisihan paling kecil yang mungkin untuk seluruh hewan pulang ke kandang dengan syarat tidak terjadi perselisihan. Jika ternyata pasti terjadi perselisihan, keluarkan -1.
Contoh Masukan dan Keluaran:
| Contoh Masukan | Contoh Keluaran |
|---|---|
6 A..... .B.... 6 3 2 1 3 7 8 5 1 9 1 4 | 19 |
6 A..... .B..B. 6 3 2 1 3 7 8 5 1 9 1 4 | 40 |
6 .A.A... .B..B. 6 3 2 1 3 7 8 5 1 9 1 4 | 54 |
6 A.A... .A..B. 6 3 2 1 3 7 8 5 1 9 1 4 | -1 |
Penjelasan Contoh
Pada contoh pertama, ayam dapat pulang ke kandang dengan hanya bergerak ke kiri sehingga rute yang dilaluinya hanyalah melewati petak (1, 1) dengan nilai kerisihan 6. Untuk bebek, ia dapat pulang ke kandang dengan bergerak ke kiri dua kali sehingga rute yang dilaluinya adalah melewati petak (2, 2) dan (2, 1) dengan nilai kerisihan 5 + 8 = 13. Total nilai kerisihan dari seluruh hewan adalah 6 + 13 = 19.
Pada contoh kedua, terdapat seekor bebek tambahan dari contoh pertama. Untuk mendapatkan kerisihan terkecil, bebek tambahan ini secara berturut-turut akan bergerak ke atas, kiri, kiri, bawah, kiri, dan kiri untuk pulang ke kandang. Dapat dihitung bahwa nilai kerisihan bebek tersebut adalah 1 + 3 + 1 + 2 + 1 + 5 + 8 = 21, sehingga total nilai kerisihan dari seluruh hewan menjadi 40.
Pada contoh ketiga, dapat dibuktikan bahwa total nilai kerisihan paling kecil adalah 54 dengan seluruh hewan hanya bergerak ke kiri saja. Perhatikan bahwa rute yang dilalui bebek pada petak (2, 5) tidak sama dengan yang ada pada contoh kedua karena dapat mengakibatkan perselisihan.
Pada contoh keempat, perhatikan bahwa rute yang dilalui bebek pasti akan pernah bersilangan dengan rute ayam sehingga terjadi perselisihan.
Batasan
- 1 ≤ N ≤ 100 000
- S1 dan S2 masing-masing memiliki panjang N dan hanya terdiri dari karakter ‘A’, ‘B’, dan ‘.’
- Dijamin bahwa terdapat setidaknya 1 ayam dan setidaknya 1 bebek di pekarangan
- 1 ≤ Mi,j ≤ 1 000 000
Batasan Tambahan untuk Subsoal 1 (Mudah)
- Dijamin bahwa banyaknya ayam adalah tepat 1, dan ayam tersebut berada pada petak (1, 1)
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!
0 jawaban
Masuk untuk menulis jawaban