Olimpiade Sains Provinsi (OSP) 2014 - Komputer, Nomor 7
Dewangga memiliki 2 ekor semut dan 2 ekor anak semut. Suatu hari, para semut dan anaknya ingin menyeberangi sungai dengan menggunakan perahu daun. Namun, perahu daun tersebut hanya cukup menampung 2 ekor anak semut atau seekor semut dewasa. Hebatnya, para semut Dewangga sudah terlatih untuk mendayung perahu daun, sehingga tiap kali menyeberang minimal harus ada 1 ekor semut atau 1 ekor anak semut yang mendayung. Untuk menyeberangkan keempat ekor semut, berapa kali minimum perahu tersebut harus menyeberangi sungai (bolak-balik dihitung 2 kali penyeberangan)?
2 jawaban
Mamat Rahmat11 tahun lalu
TOKI 2012, IF ITB 2012. http://olimpiadeinformatika.com
11
Jika dua semut kecil yang menyebrang ke sisi lain, maka satu semut dapat menyebrang kembali untuk mengembalikan perahu ke sisi awal
Jika satu semut besar yang menyebrang ke sisi lain, maka perahu tidak dapat kembali kecuali sebelumnya di sisi lain tersebut terdapat semut kecil.
Strategi yang digunakan adalah dengan menyebrangkan dua semut kecil yang akan menjadi alat untuk menyebrangkan satu semut besar. Caranya, sebrangkan 2 semut kecil X dan Y. Kemudian 1 semut kecil X akan kembali membawa perahu agar semut besar dapat menyebrang. Setelah semut besar menyebrang, semut kecil Y akan mengembalikan perahu.
Butuh 4 kali untuk menyebrangkan 1 semut besar dan 2 semut kecil masih pada kondisi semua. Total = 4*2 + 1 = 9
Ilustrasi :
(misalkan 'A' adalah semut besar dan 'a' adalah semut kecil)
Mula-mula :
AAaa
Langkah 1 :
AA -----aa----->
AA aa
Langkah 2 :
AA <-----a------ a
AAa a
Langkah 3 :
Aa ------A-----> a
Aa Aa
Langkah 4 :
Aa <-----a------ A
Aaa A
Langkah 5 :
A ------aa-----> A
A Aaa
Langkah 6 :
A <-----a------ Aa
Aa Aa
Langkah 7 :
a ------A-----> Aa
a AAa
Langkah 8 :
a <-----a------ AA
aa AA
Langkah 9 :
------aa-----> AA
AAaa
Sehingga total ada 9 langkah
muhammad khafidin al alim11 tahun lalu
1
9 kali
Masuk untuk menulis jawaban