Dika Wahyu7 tahun lalu
MAN 1 LAMPUNG TENGAH Go To TOKI 2019 Go Get Gold IOI 2019
-1
log2[100]+1 = 7 atau 100 div 2= 50 div 2= 25 div 2= 12 div 2=6 div 2= 3 div 2=1 {100,50,25,12,6,3,1} ada 7 kali penebakan
Pak Dengklek sedang bermain Tebak Angka bersama Pak Ganesh. Terdapat 100 bilangan bulat. Pak Dengklek memilih sebuah bilangan di antara 1 sampai 100, lalu Pak Ganesh berusaha menebak bilangan yang dipilih Pak Dengklek. Setiap putarannya, Pak Ganesh dapat menyebutkan sebuah bilangan, dan Pak Dengklek dapat memberikan umpan balik "Kurang Dari", "Sama Dengan", dan "Lebih Dari" sesuai dengan bilangan yang dipilih. Permainan berhenti apabila Pak Ganesh berhasil menebak bilangan yang dipilih Pak Dengklek, yaitu saat Pak Dengklek memberikan umpan balik "Sama Dengan". Paling sedikit berapa kali Pak Ganesh menyebut angka tebakan sehingga dijamin bahwa Pak Ganesh dapat menebak bilangan yang dipilih Pak Dengklek dengan benar untuk setiap kasus?
Jawaban: ……………. {tuliskan jawaban dalam bentuk angka saja}
Always thing logic
The Simple Answer Is :
2n >= 100 (Pilih n seminilmal mungkin)
misal :
23 = 8
26 = 64
27 = 128
jadi jawabannya adalah 7
Misal ane punya angka 94
50 = 100 div 2 (Lebih)
75 = 100 div 2 div 2 + 50 (Lebih)
87 = 100 div 2 div 2 div 2 + 75 (Lebih)
93 = 100 div 2 div 2 div 2 div 2 + 87(Lebih)
96 = 100 div 2 div 2 div 2 div 2 div 2 + 93 (Kurang)
Sampai disini ada 2 kemungkinan 94/95 karena ini nebak benarnya harus minimal jadi harus pasti dan
kita pakai worst case sehingga ada 2 kemungkinan lagi.Sehingga total ada 7
Perhatikan bahwa cara tercepat adalah memilih angka paling tengah secara terus menerus untuk membagi 2 angka yang mungkin.
Jadi kita akan mencari n terkecil dimana 2n > 100
n = ceil(log2 100)= 7
info: ceil artinya dibulatkan ke atas
Gunakan konsep binary search:
100/2 = 50/2 = 25/2 = 12/2 = 6/2 = 3/2 = 1
sehingga pak ganesh perlu menebak 6 bilangan untuk benar dalam setiap kasus.
Masuk untuk menulis jawaban
MAN 1 LAMPUNG TENGAH Go To TOKI 2019 Go Get Gold IOI 2019
log2[100]+1 = 7 atau 100 div 2= 50 div 2= 25 div 2= 12 div 2=6 div 2= 3 div 2=1 {100,50,25,12,6,3,1} ada 7 kali penebakan
Apakah Yang terakhir kali itu bukan penebakan???
Seharusnya yang terakhir kali juga dihtung karena dikatakan "Permainan berhenti apabila Pak Ganesh berhasil menebak bilangan yang dipilih Pak Dengklek, yaitu saat Pak Dengklek memberikan umpan balik "Sama Dengan". Paling sedikit berapa kali Pak Ganesh menyebut angka tebakan"