Olimpiade Sains Provinsi (OSP) 2016 - Komputer, Nomor 11
Ada suatu negara yang bernama negara TOKI. Mata uang negara TOKI tersebut unik, yaitu berbentuk koin yang masing-masing bernilai 2n (1, 2, 4, 8, 16, …. s.d. 2048). Pak Dengklek ingin membeli suatu barang dengan harga 714 dan harus membayar dengan uang pas. Berapa banyakkah pecahan mata uang minimum yang dibutuhkan untuk dapat membeli barang tersebut?
3 jawaban
basaruddin ritonga 10 tahun lalu
1
Koin 2n
21 =2
22 =4
23 =8
24 =16
25 =32
26 =64
27 =128
28 =256
29 =512
Harga=714
Pecahan:
1*512 + 1*128 + 1*64 + 1*8 + 1*2 = 714
Maka koin minimal adalah 5
Great?
basaruddin ritonga 10 tahun lalu
Ya,
Yusril Albi8 tahun lalu
Belajar itu bukan tentang quality tapi quantity
1
Binary ASCII dari 714 adalah 1011001010
Sehingga di dapat dari kanan ke kiri bilangan 2n yang memenuhi adalah
21 + 23 + 26 + 27 + 29 = 714
Masuk untuk menulis jawaban
semoga menjawab
Benar, untuk kasus dimana untuk semua i>1 koin Xi=aXi-1 dengan a adalah bilangan bulat > 1, strategi Greedy yang digunakan jawaban ini valid