Olimpiade Sains Provinsi (OSP) 2016 - Komputer, Nomor 9
Diberikan sebuah larik (array) yang berisi 7 buah bilangan bulat yaitu: {42, 16, 40, 33, 0, 28, 41}. Pak Dengklek menginginkan sekumpulan bilangan (satu atau beberapa bilangan) yang jika dilakukan operasi XOR (exclusiveor terhadap representasi bit suatu bilangan) terhadap elemen-elemen larik tersebut satu demi satu, hasilnya adalah bernilai 0 (nol).
Pak Dengklek boleh menambahkan satu atau beberapa bilangan bulat ke dalam larik tersebut supaya keinginannya dapat tercapai. Namun ternyata, terdapat biaya yang perlu dibayar untuk menambahkan sekumpulan bilangan bulat, yaitu sebesar bilangan terbesar yang terdapat pada kumpulan bilangan tersebut. Sebagai contoh, bilangan bulat yang ingin ditambahkan = {25, 17, 1} maka biaya yang perlu dibayar adalah 25. Berapakah biaya terkecil yang perlu dibayar Pak Dengklek? (Jika ternyata Pak Dengklek tidak perlu menambahkan apa-apa, tuliskan 0).
2 jawaban
Glenda Emanuella Sutanto10 tahun lalu
7
Perhatikan bahwa : a XOR a = 0
42 XOR 16 XOR 40 XOR 33 XOR 0 XOR 28 XOR 41 = 6
Agar hasilnya jadi 0, maka harus kita XOR kan dengan 6
Agar biaya nya minimal, periksa apakah 6 bisa dihasilkan dari 2 bilangan yang lebih kecil dari 6 yang di XOR kan
Ternyata, 6 = 4 XOR 2 (tidak ada kemungkinan lain)
Maka, kita harus menambah {4,2}
Biaya minimal yang harus dibayar = 4
CMIIW
Hendrico Bolang9 tahun lalu
2
ubah semua bilangan ke bentuk biner:
operasi xor akan bernilai 1 jika salah satu bernilai 1 atau 0 tapi tidak keduanya
42 : 1 0 1 0 1 0
16 : 0 1 0 0 0 0
40 : 1 0 1 0 0 0
33 : 1 0 0 0 0 1
0 : 0 0 0 0 0 0
28 : 0 1 1 1 0 1
41 : 1 0 1 0 0 1
kita melihat tempat di bilangan biner tersebut di mana hanya ada 1 bilangan 1
dan tempatnya berada di 22 dan 21
dapat kita lihat kalau kita memerlukan bilangan 4 dan 2 agar jika dilakukan operasi xor nilainya menjadi 0
*sorry agak ga jelas mungkin penjelasan ini
m irfan firmansyah6 tahun lalu
Rio Aga6 tahun lalu
ralat sikit, yang 28 : 0 1 1 1 0 0
Masuk untuk menulis jawaban