Pembahasan Asah Otak [PDF]

Citation preview

  Soal No. 1 K ​ode Kartu  Level: Easy  Konteks CT: Data direpresentasikan sebagai bilangan biner di  komputer. Bentuk yang “natural” bagi komputer karena ada dua status  (arus listrik melampaui/di bawah ambang tertentu)   Lima kartu diletakkan secara berderet. Masing-masing kartu berisikan  dari kiri ke kanan secara berurutan 16, 8, 4, 2, dan 1 lambang hati.  Di bagian bawah kartu terdapat tulisan angka 0 atau 1. Angka 1  dituliskan jika kartu di atasnya terbuka (dan terlihat gambar  hatinya!), sedangkan angka 0 dituliskan jika kartu tertutup.  Kartu-kartu dapat digunakan untuk membangkitkan kode-kode untuk  mewakili suatu nilai. Contoh berikut merupakan kodefikasi untuk nilai  9 karena total terdapat 9 gambar hati yang dapat terlihat pada gambar  berikut ini. Dari rangkaian tanda karta terbuka/tertutup, kode untuk  angka 9 adalah 01001. 



  Tantangan:  Temukan kode untuk nilai 19 (artinya total ada 19 lambang hati yang  terlihat).  Jawaban:  Jawaban yang benar adalah 10011.  Pembahasan:  Hati ditempatkan di kartu sehingga hanya ada satu hati pada kartu  sebelah kanan, dan setiap kartu di sebelah kiri sesudahnya mengandung  dua kali hati. Maka, akan ada 1, 2, 4, 8, dan 16 hati saat dibaca  dari kiri ke kanan. Dapat dibuktikan bahwa setiap angka dari 0 s.d.  31 dapat direpresentasikan dengan kombinasi tertentu menggunakan  kartu tersebut.      Soal No.2 K ​iri Kanan  Level: Easy  Konteks CT: Pohon biner. Digunakan di antaranya untuk kompresi data  (Huffman coding): simbol yang paling banyak digunakan muncul lebih 



dekat ke “akar” pohon yang artinya menggunakan kode lebih singkat. 



  Untuk merahasiakan lokasi pertemuan mereka, tim berang-berang  menggunakan sistem pengkodean kata yang disebut kode berang-berang,  dengan memakai peta di atas:  ● Setiap pohon di taman diberi nama dengan satu huruf.  ● Kode untuk setiap huruf ditemukan dengan cara mencapai pohon  tersebut dengan berbelok kiri (L) dan kanan (R).  ● Kode untuk setiap huruf selalu dimulai dari pintu masuk taman  (bertanda panah).  Contoh-contoh:  ● Contoh 1: Kode untuk A adalah LL karena untuk mencapai pohon A  dari pintu masuk taman kamu harus berbelok kiri dua kali.  ● Contoh 2: Kode untuk kata BAR adalah LRLLLR.  Tantangan:  Berapa banyak huruf dalam kode berang-berang tersebut untuk kata  BEAR? (Tuliskan angkanya!)  Jawaban:  Jawaban yang benar adalah 9.  Pembahasan:  Tabel berikut ini berisi kode kiri/kanan untuk semua huruf:    B 



E 



A 



R 



LRL 



LRR 



LL 



R 



  Sehingga BEAR akan dikode menjadi LRLLRRLLR yang terdiri dari 9  huruf.      Soal No.3 R ​obot Pengumpul Permen 



Level : medium  Konteks  CT  :  optimization  (memaksimalkan  sebuah  prosedur),  lebih  tepatnya:  combinatorial  search  optimization  (optimasi  pada  ruang  pencarian  diskret/kombinatorial),  complete  search  (melakukan  pencarian  secara  lengkap  di  ruang  pencarian  kombinatorial),  serta  teknik  Dynamic  Programming  (DP),  dimana  kita  mengidentifikasi  adanya  overlapping  sub-problem  (misal,  mencari  nilai  permen  maksimal  yg  didapatkan  sampai  dengan  posisi  (4,4)  dan  sampai  posisi  (3,5)  misalnya,  sama-sama  memerlukan  nilai  permen  maksimal  untuk  posisi  (3,3)  misalnya,  yang  merupakan  subproblem  dari  keduanya),  sehingga  untuk  mencari  nilai  optimal,  diperlukan  konsep  memoisasi  (mengingat  jawaban sudah ditemukan untuk subproblem di bawahnya).   Robot Candy diprogram untuk mengumpulkan permen sebanyak mungkin yang  terhampar di lantai yang terdiri dari petak-petak. Tugas tersebut  dilakukan pada saat robot berjalan melalui petak demi petak lantai.  Setiap petak di lantai sebagai tergambar di bawah ini memiliki 0, 1,  2 atau 3 permen. Robot Candy mulai dari petak S (untuk start) di kiri  bawah dan berakhir di petak F (untuk finish) di kanan atas. Namun,  Robot Candy memiliki keterbatasan: setiap kali berpindah, dia hanya  bisa berpindah dari satu petak ke petak berikutnya di sebelah  kanannya atau di sebelah atasnya.  English: Candy-collecting Robot  Candy Robot is a robot that is programmed to collect as many candies  as possible that are spread out on the grid floor. The task is  performed by the robot by going over the floor grid-by-grid,  collecting the candies on each of the grid it visits. Each grid can  contain 0, 1, 2, or 3 pieces of candies. Candy Robot must start at  the grid marked S (start) and stop at the grid marked F (finish).  However, the robot has a limitation, it can only move from its  current grid to a grid directly to the right, or to the top, of the  current grid.   Challenge:  Determine how many candies can the robot collect at most? 



  Tantangan:  Mengingat Robot Candy akan mengumpulkan permen sebanyak-banyaknya,  berapa banyak permen yang dikumpulkan oleh Robot Candy?  Jawaban:  Jawaban yang benar adalah 14.  Pembahasan:  Secara matematis hal ini dapat dinyatakan dengan  ● v (i, 0) = 0  ● v (0, j) = 0  ● v (i, j) = c (i, j) + max {v (i-1, j), v (i, j-1)}  dimana v (i, j) adalah jumlah maksimum permen yang dapat dikumpulkan  di sel (i, j), dan c (i, j) adalah jumlah permen dalam grid pada sel  (i, j) pada awalnya.  Jika kita ingin mengacu ke sel paling kiri dan paling bawah, kita  perlu menambahkan kolom angka nol ke kiri dan deretan angka nol ke  bagian bawah tabel. Dengan menerapkan hubungan ini, kita bisa mengisi  sisa tabel sebagai berikut: 



  dan oleh karena itu, kita bisa mengumpulkan 14 permen di sel F.       



Soal No.4​Kurir Lumpia  Level : easy  Konteks CT : graph (sebagai abstraction dari permasalahan,  menunjukkan mana saja tempat-tempat penting (vertex) dan jalur yang  ada antar tempat-tempat tersebut (edge), termasuk semua  persimpangan), algorithmic thinking (kita diberikan sebuah prosedur:  jalur perjalanan Budi, switch-switch-nya, apa yang boleh dan tidak  boleh dilakukan, serta proses perhitungan dari mbak A dan mbak B,  kemudian kita diberikan juga inputnya (kotak dengan jumlah 6, 14 dan  36 lumpia), dan kita diminta untuk menentukan outputnya, yaitu: hasil  perhitungan dari Mbak A dan Mbak B).   



  Budi menjadi kurir lumpia sebagai sampingan. Tiap harinya Budi  membawa 1 kotak. CCR IPB hanya menerima kotak yang berisi 6-16 buah  lumpia.    Budi memulai perjalanannya di Asrama dan berjalan mengikuti arah  panah.     ● Switch A​membuat Budi pergi ke SMA kornita dan SMA kornita  hanya mau menerima kotak lumpia yg memiliki 2016  - 2 kali menekan +2 -> 2020  Total 14 kali penekanan tombol    Sehingga minimal penekanan yang dilakukan untuk memperoleh angka 2020  adalah 1 ​4 kali penekanan tombol​ .      Soal No.10 T ​eka-Teki Huang  Level : Easy  Konteks CT : Peluang  STATUS APPROVAL: OK 



REVIEWER : SHW  Huang suka sekali membuat teka-teki. Kali ini dia membawa 3 buah peti  yang masing-masing berisi:  - 200 koin emas  - 200 koin perak  - 100 koin emas dan 100 koin perak  Huang kemudian menukar label setiap peti sehingga label setiap peti  berisi informasi yang salah. Berikut isi label setiap peti:  - Peti SUGDW : Berisi 200 koin emas  - Peti AEPFE : Berisi 200 koin perak  - Peti HMSGB : Berisi 100 koin emas dan 100 koin perak  Tantangan:  Kamu diberikan kesempatan oleh Huang untuk mengambil satu koin dari  salah satu peti tanpa melihat isinya agar bisa menebak peti manakah  yang berisi 200 koin emas. Peti manakah yang kamu pilih?  Jawaban:  Peti HMSGB  Penjelasan :  Karena label pada setiap peti berisi informasi yang salah, maka tentu  Peti HMSGB berisi antara 200 koin emas atau 200 koin perak. Jika koin  yang terambil adalah koin emas, maka 200 koin emas berada pada peti  HMSGB. Sebaliknya jika koin yang terambil adalah koin perak, maka 200  koin emas berada pada peti AEPFE (200 koin emas tidak mungkin berada  pada peti SUGDW).