Deskripsi Untuk Soal Nomor 21 dan 24
Deskripsi Cerita
Pak Dengklek memiliki papan berukuran N baris dan M kolom. Setiap baris dinomori dari 1 hingga N dari atas ke bawah dan setiap kolom dinomori dari 1 hingga M dari kiri ke kanan. Petak (X, Y) menyatakan petak pada baris ke-X dan kolom ke-Y. Pak Dengklek akan mengisi setiap petak pada papan tersebut dengan angka 1 hingga N × M sedemikian sehingga masing-masing angka akan muncul tepat satu kali pada papan.
Sebuah robot bebek akan mulai pada petak (1, 1). Pada setiap waktu, robot tersebut akan membandingkan petak tepat di kanannya dengan petak tepat di bawahnya. Robot kemudian akan berpindah ke petak yang memiliki angka yang lebih besar. Jika robot berada pada baris terakhir (baris ke-N), maka ia secara otomatis hanya akan bergerak ke kanan. Jika robot berada pada kolom terakhir (kolom ke-M), maka ia secara otomatis hanya akan bergerak ke bawah. Robot akan berhenti pada petak (N, M).
Angka-angka pada seluruh petak yang dikunjungi oleh robot bebek (termasuk petak (1, 1) dan petak (N, M)) akan dijumlahkan. Pak Dengklek kemudian akan memberi hadiah kepada bebek-bebeknya permen sebanyak jumlah ini.
Karena Pak Dengklek tidak ingin bebek-bebeknya makan terlalu banyak permen, tugas Anda adalah membantu Pak Dengklek untuk menentukan jumlah terkecil yang mungkin apabila Pak Dengklek mengisi setiap petak pada papannya dengan angka 1 hingga N × M secara optimal.
Asumsikan papan Pak Dengklek berukuran 3 baris dan 4 kolom dan Pak Dengklek mengisi papan tersebut dengan konfigurasi angka-angka seperti berikut ini.
| 4 | 6 | 1 | 10 |
| 3 | 5 | 8 | 9 |
| 12 | 11 | 2 | 7 |
Berapa jumlah angka-angka pada petak-petak yang akan dikunjungi oleh robot bebek?
Tuliskan jawaban dalam bentuk ANGKA.
Apabila papan Pak Dengklek berukuran 5 baris dan 2 kolom, berapa jumlah terkecil yang mungkin apabila Pak Dengklek mengisi setiap petak pada papan dengan angka 1 hingga 10 secara optimal?
Tuliskan jawaban dalam bentuk ANGKA.
Apabila papan Pak Dengklek berukuran 3 baris dan 3 kolom, berapa jumlah terkecil yang mungkin apabila Pak Dengklek mengisi setiap petak pada papan dengan angka 1 hingga 9 secara optimal?
Tuliskan jawaban dalam bentuk ANGKA.
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 MFormat Keluaran:
Keluarkan sebuah baris berisi sebuah bilangan bulat yang menyatakan jumlah terkecil yang mungkin apabila Pak Dengklek mengisi setiap petak pada papannya dengan angka 1 hingga N × M secara optimal.
Contoh Masukan dan Keluaran:
| Contoh Masukan | Contoh Keluaran |
|---|---|
2 3 | 11 |
1 1 | 1 |
Penjelasan Contoh:
Pada contoh pertama, salah satu konfigurasi pengisian yang optimal adalah sebagai berikut.
| 2 | 4 | 6 |
| 5 | 3 | 1 |
Robot bebek akan berjalan sebagai berikut:
Jumlah angka-angka pada petak-petak yang dikunjungi oleh robot bebek adalah 2+5+3+1 = 11.
Pada contoh kedua, hanya ada 1 kemungkinan konfigurasi pengisian yakni satu petak berisi angka 1.
Batasan:
Untuk seluruh kasus uji berlaku:
Batasan Tambahan untuk Subsoal 1 (Mudah)
Pada subsoal ini, untuk seluruh kasus uji berlaku:
Batasan Tambahan untuk Subsoal 2 (Sulit)
Tidak ada batasan tambahan pada subsoal ini.
Masuk untuk menulis jawaban