OSK Komputer

Berikut ini beberapa pembahasan soal-soal OSK / KSN-K Komputer. Soal no 9 OSK 2019. Pak Dengklek sangat suka makan bakso. Oleh karena itu, pada suatu hari ia berpikir jika ia ingin memotong sebuah bakso sebanyak 3 kali, berapa paling banyak jumlah potongan yang bisa ia dapat? Pembahasan Banyaknya potongan maksimum yang bisa didapatkan oleh pak dengklek adalah 2^n = 8 potongan. Dengan aturan pemotongan sebagai berikut: Pemotongan secara horizontal Pemotongan secara vertikal pemotongan pada tengah bakso. (secara melingkar) Soal no 26 OSK 2019. Pak Dengklek sedang melatih Beklek, bebek kesayangannya, untuk mengikuti lomba lari antar kandang bebek. Setiap harinya Beklek harus berlari berkeliling kolam dan Pak Dengklek mencatat waktu tempuh setiap putarannya. Dari data waktu yang dicatatnya, Pak Dengklek ingin mengetahui deretan putaran- putaran manakah Bekwat berada pada kondisi terbaiknya. Selama ini Beklek memiliki rata-rata p=14 per putaran. Setiap Beklek berlari dengan waktu q maka Pak Dengklek memberi nilai sebesar (p-q). Kondisi terbaik adalah ketika total nilai dalam deretan itu adalah sebesar-besarnya dan dengan panjang deretan putaran sependek-pendeknya. Misalnya suatu hari catatan waktunya adalah   Putaran ke 1 2 3 4 5 6 7 8   Waktu tempuh 13 13 13 18 12 13 13 17 Kondisi terbaiknya adalah mulai dari putaran ke 5 sampai dengan ke 7 dengan total 4 point. Untuk data catatan waktu berikut berapa total nilai pada putaran terbaiknya Beklek hari itu?   Putaran ke 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18   Waktu tempuh  13 15 11 12 16 16 15 12 14 16 12 12 15 12 16 11 15 15 Pembahasan Soal diatas dapat diselesaikan menggunakan kadane algorithms atau dynamic programming. Selain itu, problem di atas juga dapat dikenal sebagai Largest Sum Contiguous Subarray Problem atau Maximum subarray problem. Kadane algorithm pseudocode  best_sum = INT_MINcurrent_sum = 0Loop for each element of the array  current_sum = Max(0, current_sum + a[i])  best_sum = Max(best_sum, current_sum)return best_sum Pseudocode algoritma kadane Pada problem diatas kita diminta untuk mencari jumlah nilai terbesar dari suatu array. Array yang diberikan pada soal, semua nilai pada baris waktu tempuhnya diubah menjadi p-q seperti pada soal. Sehingga terbentuk tabel sebagai berikut.   Putaran ke 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18   p-q  1 -1 3 2 -2 -2 -1 2 0 -2 2 2 -1 2 -2 3 -1 -1 Dengan menggunakan kadane algorithms didapatkan total nilai terbaiknya adalah 6. Dimulai dari putaran ke-1 sampai dengan putaran ke 16. Soal no 22 OSK 2019. Pada ulang tahunnya yang ke 67 tahun depan, pak Dengklek ingin mengundang sedikit mungkin orang sehingga paling tidak ada 67 orang yang berulang tahun pada hari yang sama. Berapakah orang yang harus ia undang untuk pestanya? (diasumsikan pada setiap tahun hanya ada 365 hari) Pembahasan Persoalan di atas dapat diselesaikan menggunakan prinsip sarang merpati (Pigeonhole Principle). Pada Pigeonhole Principle, Jika kita memiliki n buah benda yang akan ditempatkan pada m kontainer (tempat) dengan nilai n > m, maka setidaknya satu container harus berisi lebih dari satu item. Pada persoalan diatas, banyaknya orang yang berulang tahun dapat kita sebut sebagai n dan kontainernya atau m adalah banyaknya hari dalam setahun. Berdasarkan hal tersebut dapat banyaknya orang yang diundang adalah 365*66+1= 24.091. Akan tetapi karena pada hari tersebut juga pak Dengklek berulang tahun maka jumlah orang yang perlu ia undang untuk mendapatkan hal yang ia inginkan adalah 24.091 – 1 = 24090 Orang. Soal no 29 OSK 2019. Saatnya makan siang, para bebek akan diatur untuk duduk di ruang makan pada kursi-kursi yang kebetulan sudah dinomori dari 0, 1, 2, … 14. Supaya ada variasi urutan duduk maka Pak Dengklek akan mendudukan para bebek menurut aturan sebagai berikut. Berdasarkan urutan awal dengan angka menyatakan tinggi badan: 44, 94, 83, 42, 38, 36, 20, 49, 33, 92, 34, 32, 13, 24, 53. Setiap bebek mulai dari yang pertama hingga terakhir harus berhitung sebagai berikut. Jika berat badan X maka dapatkan Y = (X*11) mod 15. Jika kursi nomor Y kosong, maka bebek dengan berat badan X menempati posisi Y. Jika tidak, (sudah ada yang menempati), maka ulangi memeriksa kursi-kursi berikutnya (atau no Y+1, Y+2, …) hingga ada yang kosong atau jika sampai nomor 14 terisi, ia melanjutkan memeriksa dari kursi nomor 0, nomor 1, dan seterusnya. Bebek dengan berat badan 44, akan menempati kursi 4, karena 44*11 mod 15 = 4 (masih kosong). Bebek dengan berat badan 94, akan menempati kursi 14, karena 94*11 mod 15 = 14 (masih kosong). Bebek dengan berat badan 83, akan menempati kursi 13, karena 83*11 mod 15 = 13 (masih kosong). Bebek dengan berat badan 42, akan menempati kursi 12, karena 42*11 mod 15 = 12 (masih kosong). Bebek dengan berat badan 38, akan menempati kursi 0, karena 42*11 mod 15 = 13 (sudah terisi), no 14 juga sudah terisi, baru di 0 masih kosong. Dan seterusnya. Pertanyaan: Bebek dengan berat badan berapakah yang menempati kursi no 9? Pembahasan Persoalan ini dapat diselesaikan dengan melakukan tracing secara manual sebagai berikut: Bebek dengan berat badan 92, akan menempati kursi 7, karena 42*11 mod 15 = 7 Bebek dengan berat badan 34 akan menempati kursi 1, karena 14 (sudah terisi), 0 (sudah terisi) Bebek dengan berat badan 32, akan menempati kursi 8, karena 32*11 mod 15 = 7 (sudah terisi), lanjut ke kursi 8 Bebek dengan berat badan 13 akan menempati kursi 9, karena 13*11 mod 15 = 8 (sudah terisi) lanjut ke kursi 9. Maka bebek yang duduk di kursi nomor 9 adalah bebek yang memiliki berat 13. Soal no 25 OSK 2018. Untuk ulang tahun pak Dengklek, ibu Dengklek membuat kue yang dibubuhi dengan 8 macam zat pelezat. Ternyata, setelah dibakar, kuenya berwarna hijau. Walaupun demikian, para tamu mengatakan bahwa kue itu sangat enak. Bu Dengklek ingin membuat kue itu lagi, namun tak ingin warnanya hijau, dengan mengkombinasikan zat pelezat yang akan dicampurkan. Setelah melakukan konsultasi ke bu Ganesh, ternyata hanya salah satu zat pelezat yang menyebabkan warna kuenya hijau. Berapa kali usaha