Game
Soal 4 Olimpiade Sains Mahasiswa 2007, Yogyakarta.
Deskripsi Soal :
Buatlah sebuah game 2 player antara Komputer Vs User dengan deskripsi game seperti berikut :
Ada dua buah kotak. Kotak pertama berisi sejumlah kelereng N. Secara bergantian, player 1 dan payer 2 memindahkan sejumlah kelereng dari kotak pertama ke kotak kedua dan tidak boleh melebihi jumlah maksimal pemindahan, M. M dijamin tidak melebih 10% dari total kelereng. Pemain yang berhasil memindahkan kelereng terakhir kali sehingga kotak pertama kosong, keluar sebagai pemenang.
Diberikan input N dan M. User memilih siapa yang menjadi player 1, komputer atau user, kemudian user menginputkan jumlah kelereng yang ingin dipindahkan setiap kali gilirannya. Program harus dibuat sehingga komputer selalu memenangkan game, kecuali jika player 1 adalah User dan User selalu mengambil langkah terbaik.
Solusi :
Saya belum mendapatkan solusi optimalnya, jadi bagi yang sudah tahu, isi saja comment untuk post ini.
Risan berkata,
Maret 30, 2008 pada 11:05 am
Wah, ternyata Kak Riza juga punya blog.
Bisa pake algoritma ini ga ya: Pertama-tama, Komputer ambil kelereng sebanyak N mod (M+1), terus klo user ambil sebanyak X, Komputer ambil sebanyak (M+1)-X. Komputer udah pasti menang klo jalan duluan, kecuali kalau N habis dibagi (M+1), udah pasti user menang karena dia jalannya optimal. Hehehe…
Risan
Risan berkata,
Maret 30, 2008 pada 11:08 am
Itu mirip soal OSP, di TOKInet pernah ada yang bahas. Hehehe…
Risan
Riza berkata,
April 1, 2008 pada 12:08 am
Heh, di milis TOKI dah pernah dibahas ya??
Wakakakak, dasar akunya yang gak pernah buka2 milis.
Kemarin pake cara itu juga sih, tapi masih gak yakin bener
Maklum, sudah tuwa
Riza berkata,
April 2, 2008 pada 12:31 am
Kalo N=(M+1)*A , trus komputer jalan duluan, masih bisa menang gak San?
Risan berkata,
April 6, 2008 pada 2:27 am
Klo N=(M+1)*A, udah pasti user yang menang.