Olimpiade Sains Nasional VI
Soal Aritmetika / Analitika / Logika
SOAL ARITMETIKA / ANALITIKA / LOGIKA
1. Bilangan selanjutnya dari barisan 4, 5, 8, 13, 20, 29, ... adalah: a. 38
b. 39
2. Berapakah nilai dari
a. 1
b. 2/3
c. 40
d. 42
e. 49
d. 2
e. tidak ada pilihan jawaban lain yang benar
?
c. 30/11
3. Berapakah nilai dari ekspresi 2 – 4 + 6 – 8 + 10 – 12 + 14 – ... – 100 ? a. –50
b. 0
c. 50
d. 100
e. tidak ada pilihan jawaban lain yang benar
4. Berapakah nilai dari: 1 + 2 – 3 – 4 + 5 + 6 – 7 – 8 + 9 + ... – 99 – 100 ? a. –100
b. 0
c. 1
d. 100
e. tidak ada pilihan jawaban lain yang benar
5. Floor(x) adalah bilangan bulat terbesar yang tidak lebih besar dari x. Sebagai contoh, floor(10/3) = 3. Berapakah hasil perhitungan floor(floor(1000/7)/floor(71/2))? a. 4
b. 5
c. 7
d. 10
e. 500
6. Jika a ⌂ b = ab + a – b, berapakah (7 ⌂ p) – (p ⌂ 7)? a. 14p
b. 14 – 2p c. p + 7
d. 0
e. tidak ada pilihan jawaban lain yang benar
7. Ada berapa carakah kita dapat menuliskan angka 10 sebagai hasil penjumlahan atas tepat tiga bilangan bulat positif yang tidak harus berbeda satu sama lain jika urutan penulisannya tidak diperhitungkan? (Sebagai contoh, salah satu cara memperolehnya adalah 10 = 1+4+5, yang sama dengan 10 = 4+1+5)
Page 1 of 18
Olimpiade Sains Nasional VI
a. 5
b. 6
Soal Aritmetika / Analitika / Logika
c. 7
d. 8
e. 10
8. Sebuah lantai persegi panjang dilapisi sepenuhnya dengan ubin yang berukuran 1 × 2. Jika ubin-ubin ini tidak dipotong dan tidak saling bertindihan, lantai tersebut tidak mungkin berukuran: a. 4 × 9
b. 8 × 8
c. 11 × 7
d. 16 × 5
e. tidak ada pilihan jawaban lain yang benar
9. Sebuah kubus 4 × 4 × 4, yang dibangun dengan cara melekatkan kubus-kubus berukuran 1 × 1 × 1, dicat pada sisi-sisi luarnya dan kemudian diurai kembali. Berapa jumlah kubus-kubus kecil hasil penguraian ini yang memiliki tepat 2 sisi bercat? a. 8
b. 16
c. 20
d. 24
e. 32
10. Sebuah kotak berisikan 80 balok, sebagian terbuat dari kayu dan sebagian lagi terbuat dari plastik. Tiap balok diwarnai dengan warna merah atau hijau. Jika 48 buah balok terbuat dari kayu dan 32 balok berwarna merah, berapakah jumlah terbesar balok plastik hijau yang mungkin? a. 16
b. 24
c. 32
d. 48
e. tidak ada pilihan jawaban lain yang benar
11. Sebuah jalur yang berlebar 1m dikelilingi sebagian oleh pagar yang ditunjukkan pada diagram berikut. Berapakah panjang dari pagar tersebut?
Page 2 of 18
Olimpiade Sains Nasional VI
a. 21m
b. 22m
Soal Aritmetika / Analitika / Logika
c. 23m
d. 24m
e. 25m
12. Seorang siswa yang sedang menggunakan sebuah kalkulator untuk menghitung sebuah penjumlahan secara tidak sengaja menambahkan 79012 sementara sebenarnya ia ingin menambahkan 7912. Untuk membetulkan perhitungannya dalam satu operasi, siswa tersebut harus melakukan pengurangan dengan: a. 7012
b. 71100
c. 71112
d. 86924
e. tidak ada pilihan jawaban lain yang benar
13. Suatu hari, Kwek bertanya kepada Pak Dengklek, “Pak, berapa umur Anda?”. Pak Dengklek menjawab, “Tahun ini, saya tiga kali lebih tua dari saudara saya. Enam tahun lalu, saya lima kali lebih tua darinya.” Berapakah umur Pak Dengklek saat itu? a. 36
b. 40
c. 49
d. 55
e. tidak ada pilihan jawaban lain yang benar
14. Empat orang anak menemukan sekantong kelereng dan membaginya di antara mereka. Tiap anak mengambil sejumlah berbeda kelereng dan tidak satupun anak mendapat kelereng sebanyak lebih dari 2 kali lipat kelereng yang dimiliki oleh anak lainnya. Banyak terkecil kelereng yang mungkin terdapat pada kantong tersebut adalah: a. 10
b. 15
c. 18
d. 21
e. tidak ada pilihan jawaban lain yang benar
15. Tepat 100 orang tinggal di sebuah desa. Orang tertua di desa tersebut dilahirkan pada tahun 1900 dan setiap orang pada desa tersebut dilahirkan pada tahun yang berbeda tetapi kesemuanya lahir pada 1 Januari. Pada tahun 1999, hasil penjumlahan digit-digit dari angka tahun lahir seorang penduduk desa tersebut sama dengan umurnya saat itu. Berapakah umur orang tersebut? a. 4
b. 12
c. 16
d. 23
e. tidak ada pilihan jawaban lain yang benar
Page 3 of 18
Olimpiade Sains Nasional VI
Soal Aritmetika / Analitika / Logika
16. Kwak berlari dengan kecepatan tetap dari titik A ke titik C. Pada saat yang bersamaan, Kwik berlari dari titik B ke titik C dengan kecepatan tetap pula. Mereka tiba di C pada saat yang bersamaan. Jika mereka terus berlari dengan arah yang sama seperti semula, Kwak tiba di B tepat 10 detik sebelum Kwik tiba di A. Seberapa cepatkah (dalam m/s) Kwik berlari? (titik C berada di antara A dan B, jarak AC adalah 60m, jarak CB 40m)
a. 3
b. 10/3
c.
13/3
d. 5
e. informasi tidak
cukup 17. Sebuah kotak berisikan beberapa buah
apel. Kwak mengambil 1/2 di antaranya
ditambah 1 buah apel lagi dari apel-apel
yang tersisa. Kemudian, Kwik mengambil 1/3
dari apel yang tersisa tetapi kemudian memasukkan kembali 2 buah apel ke dalam kotak. Kwek lantas mengambil 5/6 dari apel yang tersisa ditambah 1 buah apel lainnya. Setelah pengambilan-pengambilan tersebut, apel yang tersisa di dalam kotak tersebut tinggal 7 buah. Berapa banyakkah jumlah apel mula-mula? a. 16
b. 44
c. 110
d. 140
e. tidak ada pilihan jawaban lain yang benar
18. Dalam sebuah ujian yang terdiri atas 2 soal, 18 peserta menjawab pertanyaan pertama dengan benar, 23 peserta menjawab pertanyaan kedua dengan benar, 8 peserta menjawab kedua pertanyaan dengan benar dan 11 peserta tidak berhasil menjawab dengan benar kedua pertanyaan. Berapakah jumlah peserta ujian tersebut? a. 41
b. 44
c. 49
d. 52
e. 60
19. Berapakah banyaknya persegi panjang pada sebuah papan catur berukuran 5 × 5? (Jangan lupa menghitung pula bujur sangkar (persegi) yang Page 4 of 18
Olimpiade Sains Nasional VI
Soal Aritmetika / Analitika / Logika
ditemukan karena bujur sangkar merupakan salah satu jenis khusus dari persegi panjang) a. 25
b. 225
c. 55
d. 200
e. 170
20. Pak Dengklek memiliki 101 buah telur yang harus dibagi-bagi ke dalam beberapa buah kantung untuk dijual. Pak Dengklek kemudian melabeli kantung-kantung tersebut dengan banyaknya telur yang ada dalam kantung tersebut serta menyegelnya. Pak Dengklek ingin agar dia dapat melayani seorang pembeli yang ingin membeli telur sebanyak sembarang butir antara 1 dan 101 (termasuk 1 dan 101) tanpa harus membuka satu pun segel dan mengemas ulang telur-telur tersebut. Agar dapat memenuhi kondisi tersebut, berapakah jumlah kantung minimal yang dibutuhkan Pak Dengklek pada saat pembungkusan awal? (Perlu diketahui bahwa Pak Dengklek bebas menentukan banyaknya kantung serta banyaknya telur yang dimasukkan pada masing-masing kantung, jumlah telur pada setiap kantong tidak harus sama meski boleh sama, dan telur harus dimasukkan ke dalam kantung dalam kondisi utuh – tidak mungkin memasukkan ½ telur atau telur dalam jumlah pecahan lainnya) a. 7
b. 21
c. 5
d. 101
e. 8
21. Berat badan Kwek 140 gram lebih berat dari Kwik. Total berat mereka 200 gram. Berapakah berat badan Kwik (dalam gram)? a. 30
b. 60
c. 80
d. 140
e. 170
22. Dalam sebuah turnamen sepakbola, setiap kesebelasan diharuskan bertanding tepat satu kali melawan tiap kesebelasan lainnya. Jika dalam turnamen tersebut dimainkan 66 pertandingan, berapakah banyaknya kesebelasan yang mengikuti turnamen tersebut? a. 33
b. 12
c. 20
d. 11
e. 6
23. Sebuah lomba tenis perorangan dilangsungkan dengan sistem gugur. (Untuk setiap tahap, tiap peserta ditandingkan dengan salah satu peserta lain. Peserta yang menang akan maju ke tahap berikutnya dan ditandingkan dengan salah satu pemenang lainnya. Demikian seterusnya hingga tersisa 1 orang pemenang pada tahap terakhir.) Jika banyak peserta adalah 32 orang, berapakah banyaknya pertandingan yang terjadi pada lomba tenis tersebut? a. 32
b. 16
c. 15
d. 31
e. 17
24. Seorang saudagar kaya memiliki banyak koin emas. Karena tak ingin kekayaannya diketahui orang, dia menyimpannya di sebuah gua Page 5 of 18
Olimpiade Sains Nasional VI
Soal Aritmetika / Analitika / Logika
tersembunyi di dalam hutan dan tidak pernah memberitahukan jumlah kekayaannya kepada siapapun. Suatu hari, karena penasaran, istri saudagar tersebut bertanya kepada saudagar tersebut mengenai jumlah kekayaannya. Mendengar pertanyaan itu, sang saudagar hanya menjawab, “Jika aku membaginya menjadi 2 bagian tidak sama banyak, selisih banyak koin antardua bagian tersebut dikalikan 42 sama banyaknya dengan selisih dari (kuadrat banyak koin bagian pertama) dan (kuadrat banyak koin pada bagian kedua).” Berapa banyakkah koin emas yang dimiliki saudagar tersebut? a. 9
b. 7
c. 33
d. 6
e. 42
25. Seorang pengemudi mengendarai mobil dari kota A ke kota B, kemudian kembali ke kota A melalui jalur jalan yang persis sama. Perjalanan dari kota A ke kota B bersifat menanjak dan ditempuh dengan kecepatan 42 km/jam. Sebaliknya, perjalanan dari kota B ke kota A menurun, sehingga kecepatan yang dicapainya adalah 56 km/jam. Berapakah kecepatan rata-rata pengemudi tersebut untuk keseluruhan perjalanan? a. 49
b. 48
c. 50
d. 47
e. tidak ada pilihan jawaban lain yang benar
26. “Jarak” antara dua tombol pada tuts telepon adalah jumlah perbedaan posisi kolom dan baris keduanya. Sebagai contoh, “jarak” antara tombol 0 dan 1 adalah 4, karena ada perbedaan 1 kolom dan 3 baris
antara tombol 0 dan 1. Berapakah “jarak” yang tercipta jika
tombol 8654937 ditekan sebanyak 2007 kali berturut-
turut?
a. 26091
b. 27094
c. 28097
d.
29100 e. tidak ada pilihan jawaban lain yang benar
27. Dino berada di sekolah dari jam 06.36 pagi hingga
14.24. Selama berada di sekolah, sepertiga waktunya digunakan
untuk beristirahat. Seperempat dari waktu yang tersisa
digunakan untuk berolahraga. Jika sisa waktunya digunakan
untuk belajar, maka pernyataan manakah yang benar? a. Dino belajar 156 menit lebih lama dari berolahraga
b. Dino belajar 160 menit lebih lama dari berolahraga
menit lebih lama dari berolahraga d. Dino belajar 240 menit lebih lama dari berolahraga
c. Dino belajar 234
e. tidak ada pilihan jawaban lain yang benar
28. Sebuah fungsi didefinisikan sebagai f(n) = f(n-1).f(n-2) dan selalu bernilai non-negatif. Diketahui f(36) = 7 dan f(39) = 1008. Berapakah nilai Page 6 of 18
Olimpiade Sains Nasional VI
Soal Aritmetika / Analitika / Logika
dari f(38) – f(37)? a. 72
b. 84
c. 144
d. tidak dapat ditentukan
e. tidak ada pilihan jawaban lain yang benar
29. Pada suatu waktu ada 5 orang sahabat: Andi, Budi, Ratna, Hendri, dan Tuti. Hendri memiliki uang Rp. 10000, sementara yang lainnya tidak memiliki uang. Suatu hari, Budi meminjam uang Rp. 9000 dari Hendri dengan bunga 5%. Lalu, Ratna meminjam uang Rp. 8000 dari Budi dengan bunga 10%. Kemudian, Andi meminjam uang Rp. 4500 dari Ratna dengan bunga 20%. Lalu, Tuti meminjam uang Rp. 4000 dari Andi dengan bunga 25%. Terakhir, Hendri memberikan uang Rp. 1000 kepada Tuti sebagai hadiah ulang tahun. Setelah semua hutang-hutang dan bunganya dibayarkan (dengan asumsi tidak ada tambahan pemasukan lain), siapakah yang memiliki uang paling banyak? a. Andi
b. Budi
c. Ratna
d. Hendri e. Tuti
30. Dari angka 1 hingga 1000 (termasuk 1 dan 1000), ada berapa banyakkah kelipatan 3 yang bukan kelipatan 5? a. 123
b. 200
c. 267
d. 334
e. tidak ada pilihan jawaban lain yang benar
31. Berapakah nilai rata-rata dari 100000 bilangan bulat positif ganjil pertama? a. 100000 b. 1000000 c. 10000000
d. 100000000
e. 1000000000
32. Jika digabungkan, seluruh sekolah SMA di kota X memiliki 1.989 unit komputer untuk keperluan berlajar siswa-siswanya, yang mana dari jumlah tersebut maka rasio jumlah siswa dibandingkan jumlah komputer adalah 68,6. Berapakah kira-kira terdekat jumlah siswa SMA di kota tersebut? (dalam ribuan) a. 30
b. 120
c. 140
d. 160
e. 200
33. Jika p adalah sebuah bilangan bulat positif, manakah dari persamaan berikut ini yang mungkin menghasilkan bilangan prima? a. 8p
b. 8p + 1
c. 8p + 2
d. 8p + 4
e. 8p + 6
34. Sebuah mobil ambulans menempuh jarak 10 km pada kecepatan 50 km/jam, Berapakah kecepatan (dalam km/jam) yang harus dicapai oleh ambulans tersebut agar total waktu tempuh perjalanan pulang perginya tepat 20 menit? a. 55
b. 60
c. 65
d. 70
e. 75
Page 7 of 18
Olimpiade Sains Nasional VI
Soal Aritmetika / Analitika / Logika
35. Dua hari terakhir ini, Pak Dengklek membelikan sarapan untuk beberapa orang temannya. Untuk masing-masing temannya, kemarin Pak Dengklek membelikan sepotong roti dan segelas teh manis di sebuah warung. Karena sarapan kemarin dirasa kurang, hari ini, ia membelikan 3 potong roti dan segelas teh manis di warung yang sama. Jika Pak Dengklek menghabiskan total uang sebesar Rp 5.400 kemarin dan Rp 12.600 hari ini, berapakah uang yang dikeluarkan Parto untuk membayar roti-roti yang dibelinya hari ini? (dengan asumsi harga sepotong roti dan harga segelas teh manis tidak berubah dalam dua hari ini) a. Rp 10.800
b. Rp 9.600
c. Rp 7.200
d. Rp 3.600
e. Rp 2.400
SOAL BACAAN 1 Seorang petugas museum merencanakan sebuah pameran patung di sebuah taman. Terdapat tujuh patung yang akan dipamerkan: F, G, H, J, R, S dan U. Tiga patung akan di pamerkan di taman sebelah selatan dan empat patung akan di pamerkan di taman sebelah utara. Empat dari patung-patung tersebut – F, G, H, J – terbuat dari baja sedangkan tiga patung lainnya – R, S, U – terbuat dari perunggu. Petugas museum tersebut akan menyusun patungpatung tersebut dengan beberapa aturan berikut ini: − Masing-masing taman harus terdapat paling banyak 2 patung perunggu − G tidak dapat berada di sisi taman yang sama dengan U − H tidak dapat berada di sisi taman yang sama dengan R
36. Manakah dari kelompok berikut ini yang dapat diletakkan di taman sebelah utara? a. F, G, H dan U
b. F, H, S dan U
c. G, H, R dan U
d. G, J, R dan U
e. J, R, S dan U
37. Jika U dan R ditempatkan di taman sebelah utara, manakah kelompok patung berikut ini yang seharusnya berada di taman sebelah selatan? a. F, G dan H
b. F, J dan S
c. G, H dan S
d. G, H dan U
e. H, S dan U
38. Jika S dan U ditempatkan di taman sebelah selatan, masing-masing patung berikut ini harus diletakkan di taman sebelah utara, KECUALI : a. F
b. G
c. H
d. J
e. R Page 8 of 18
Olimpiade Sains Nasional VI
Soal Aritmetika / Analitika / Logika
39. Jika S dan R diletakkan di taman sebelah selatan, manakah dari patung-patung berikut ini yang juga ditempatkan di taman yang sama? a. F
b. G
c. H
d. J
e. U
40. Jika G dan H diletakkan di taman sebelah selatan, manakah diantara patung-patung berikut ini yang harus juga berada di taman yang sama? a. F
b. J
c. R
d. S
e. U
41. Jika F dan G diletakkan di taman sebelah utara, manakah diantara kelompok patung-patung ini yang dapat diletakkan di taman sebelah selatan ? a. H, J dan S
b. H, J dan U
c. H, R, dan U
d. J, S dan U
e. R, S dan U
SOAL BACAAN 2 Terdapat 6 buah tiang kayu – P, Q, R, S, T dan U - yang masing-masing diletakkan ke dalam lubang-lubang yang berbeda. Terdapat 7 lubang yang telah disiapkan dan masing-masing diberi nomer berurutan dari kiri ke kanan, lubang-lubang tersebut dibuat sejajar lurus dan diberi jarak yang sama di masing-masing lubang. Penempatan tiang-tiang tersebut harus mengikuti beberapa kondisi berikut ini: − Jarak yang memisahkan antara tiang P dan Q harus sama dengan jarak yang memisahkan R dan S − T harus berada di lubang yang berdampingan setelah lubang dimana U ditempatkan − Lubang yang paling kiri harus terisi (tidak dapat dibiarkan kosong)
42. Jika U ada di lubang nomer 2, manakah pernyataan yang benar? a. P berada di lubang nomer 3 7
b. Q berada di lubang nomer 4
c. R berada di lubang nomer 5
d. S berada di lubang nomer
e. T berada di lubang nomer 1 43. Jika U, P dan R berada di lubang nomer 5, 6, dan 7 berturut-turut, manakah pernyataan yang benar? a. S berada di lubang nomer 1
2
b. S berada di lubang nomer 2
e. Lubang nomer 2 adalah lubang kosong
Page 9 of 18
c. Q berada di lubang nomer 2
d. Q berada di lubang nomer
Olimpiade Sains Nasional VI
Soal Aritmetika / Analitika / Logika
44. Jika P dan R berada di lubang 1 dan 3 berurutan, lubang yang mungkin akan menjadi kosong adalah salah satu dari: a. 2 atau 4 b. 2 atau 6 c. 4 atau 5 d. 5 atau 7 e. 6 atau 7 45. Jika P dan Q berada di lubang 2 dan 4 berurutan, manakah pernyataan yang benar? a. R berada di lubang nomer 3 1
b. R berada di lubang nomer 5
c. S berada di lubang nomer 6
d. U berada di lubang nomer
e. Lubang nomer 6 adalah lubang kosong
SOAL ALGORITMIK 1 Ada sebuah alat gambar sederhana yang hanya bisa menggambar garis lurus pada sebuah bidang Cartesius. Alat ini diberi input berupa 2 bilangan: x y. -
x artinya alat berputar x*900 ke kanan
-
y artinya alat bergerak maju y kotak
-
pada awalnya alat ini menghadap sumbu y-positif
Contoh pemakaian alat: 1. Jika dimasukkan: 0 10 maka alat akan berputar 0*900 ke kanan dan bergerak maju 10 kotak sehingga muncul garis vertikal sepanjang 10 satuan. Jika ditambah lagi: 1 10
{berputar 1*900 ke kanan dan maju 10 kotak}
1 10 1 10 maka akan tergambar sebuah persegi dengan panjang sisi 10
Page 10 of 18
Olimpiade Sains Nasional VI
Soal Aritmetika / Analitika / Logika
2. Jika dimasukkan: 0 5
{berputar 0*900 ke kanan dan maju 5 kotak}
1 2
{berputar 1*900 ke kanan dan maju 2 kotak}
1 4
{berputar 1*900 ke kanan dan maju 4 kotak}
3 2
{berputar 3*900 ke kanan dan maju 2 kotak}
1 1
{berputar 1*900 ke kanan dan maju 1 kotak}
1 4
{berputar 1*900 ke kanan dan maju 4 kotak}
maka akan tergambar bentuk:
dengan penjelasan:
Page 11 of 18
Olimpiade Sains Nasional VI
Soal Aritmetika / Analitika / Logika
46. Apa gambar yang dihasilkan oleh mesin gambar ini jika diberi masukan: 4 2 8 3 10 5
7 4
a.
b.
c.
47. Manakah masukan yang menghasilkan gambar a.
1 3
b.
8 3
d.
e. tidak ada pilihan jawaban lain yang benar
? c.
3 3
d.
0 7
5 3
1 3
7 4
1 3
10 6
1 6
3 5
5 3
7 3
9 3
3 6
1 4
3 6
1 3
7 5
3 4
3 3
5 4
3 2
7 3
Page 12 of 18
e. tidak ada pilihan jawaban lain yang benar
Olimpiade Sains Nasional VI
Soal Aritmetika / Analitika / Logika
SOAL ALGORITMIK 2 Ada sebuah alat yang dapat mengendalikan 4 buah wadah air: -
Wadah 1 berukuran 4 liter
-
Wadah 2 berukuran 7 liter
-
Wadah 3 berukuran 13 liter
-
Wadah 4 berukuran 19 liter {pada awalnya, semua wadah air kosong}
Alat ini dapat diberi input: isi x {perintah ini untuk mengisi wadah x sampai penuh} tuang x y {perintah ini untuk menuangkan isi wadah x ke wadah y, jika wadah y sudah penuh maka penuangan dihentikan} tumpah x y {perintah ini untuk menuangkan isi wadah x ke wadah y, walaupun wadah y sudah penuh penuangan tetap diteruskan sampai isi wadah x habis (sisanya tumpah)} buang x {perintah ini untuk mengosongkan isi wadah x} Contoh pemakaian: isi 4
{maka wadah 4 berisi penuh 19 L}
tuang 4 3 {maka wadah 3 berisi penuh 13 L dan wadah 4 sisa 6 L} tumpah 3 1 buang 2
{maka wadah 1 berisi penuh 4 L dan wadah 3 kosong}
{karena wadah 2 memang kosong sejak awal, tidak terjadi perubahan apa-apa} Page 13 of 18
Olimpiade Sains Nasional VI
Soal Aritmetika / Analitika / Logika
{keadaan akhir: - wadah 1: 4 L - wadah 2: 0 L - wadah 3: 0 L - wadah 4: 6 L} 48. Manakah deretan input yang menghasilkan 9 L air pada wadah 4? a.
b.
isi 3
c.
isi 3
isi 2
tuang 3 2
tuang 3 1
tuang 2 4
tumpah 3 4
tumpah 3 4
tambah 2 4
d. ada lebih dari satu deretan input yang benar
e. tidak ada pilihan jawaban lain yang benar
49. Berapa input minimal yang diperlukan untuk menghasilkan 5 L air pada wadah 4? a. 3
b. 4
c. 5
d. 6
e. tidak ada pilihan jawaban lain yang benar
SOAL ALGORITMIK 3 50. Var matriks : array[1..10, 1..10] of integer Bayangkan kita memiliki sebuah array 2 dimensi seperti deklarasi diatas. Kita ingin mengisi salah satu nilai dalam matriks tersebut. Kita baca x dan y sebagai posisi elemen matriks yang akan diisikan, kemudian kita baca nilai yang akan diisikan ke dalam matriks[x,y] tersebut. Pengecekan manakah yang paling tepat untuk mencegah agar posisi yang akan kita isikan tidak berada di luar jangkauan? a. if (x>0) or (y>0) and (x<=10) or (y<=10) then ... b. if (x>0) and (y>0) or (x<=10) and (y<=10) then ... c. if not((x<0) or (y<0) or (x>10) or (y>10)) then ... d. if (x>0) and (y>0) and not(x<11) and not(y<11) then ...
Page 14 of 18
Olimpiade Sains Nasional VI
Soal Aritmetika / Analitika / Logika
e. if not((x<1) or (x>10)) and not((y<1) or (y>10)) then ... SOAL ALGORITMIK 4 Perhatikan sub program berikut:
51. Dari pemanggilan dibawah ini, manakah yang bernilai FALSE? a. topSecret(1,2,3) b. topSecret(2,6,2) c. topSecret(4,8,8) d. topSecret(6,5,4) e. topSecret(7,9,5)
Page 15 of 18
Olimpiade Sains Nasional VI
Soal Aritmetika / Analitika / Logika
52. Dari pemanggilan dibawah ini, manakah yang bernilai TRUE? a.
topSecret(77,35,59)
b.
topSecret(61,82,93)
c.
topSecret(54,20,11)
d.
topSecret(44,43,72)
e.
topSecret(25,18,36)
SOAL ALGORITMIK 5 Perhatikan potongan program di bawah ini!
Page 16 of 18
Olimpiade Sains Nasional VI
Soal Aritmetika / Analitika / Logika
53. Jika kita memasukkan bilangan 5 3 8 1 6 sebagai pengisi a, b, c, d dan e, maka apakah keluaran potongan program di atas? a.
-2 3 8 4 1
b.
0 3 8 4 1
c.
3 -3 -2 8 0
d.
3 3 -2 4 0
e.
5 3 8 16 0
SOAL ALGORITMIK 5 Perhatikan potongan program di bawah ini!
54. Jika di akhir, dituliskan writeln(data[2,2]); apakah keluaran program tersebut? a. 1
b. 2
c. 4
d. 7
e. 11 Page 17 of 18
Olimpiade Sains Nasional VI
Soal Aritmetika / Analitika / Logika
55. Berapakah nilai akhir data[5,5]? a. 10
b. 16
c. 23
d. 24
e. 45
CADANGAN
56. Berapakah digit terakhir dari hasil perkalian 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1? a. 0
b. 2
c. 4
d. 6
e. 8
57. Berapakah hasil penjumlahan 200 + 201 + 202 + ... + 800? a. 300000 b. 300500 c. 301500 d. 302000 e.302500 58. Apakah digit terakhir dari perhitungan a. 1
b. 3
c. 5
? d. 7
e. 9
59. Jika bilangan x habis dibagi 7 dan bilangan y habis dibagi 21, pernyataan-pernyataan manakah yang benar? I. x dan y kemungkinan adalah bilangan yang sama II. y-x akan berupa bilangan non-negatif III. Faktor persekutuan terbesar dari x dan y adalah 7 a. I dan II b. I dan III c. II dan III d. I, II, dan III
e. tidak ada pilihan jawaban lain yang benar
Page 18 of 18
SOAL SESI 1
OLIMPIADE SAINS NASIONAL VII BIDANG INFORMATIKA 10 AGUSTUS 2008 MAKASSAR, SULAWESI SELATAN
Selamat Bekerja, Berkompetisi, Jadilah Yang Terbaik!
Sesi 3
OSN VII
OSN2008: Olimpiade Sain Nasional 2008 Pilihan berganda Waktu: 10 Agustus 2008, 08:45:00-11:45:00 • Jawaban Betul: 4 • Jawaban Salah: -1 • Jawaban Kosong: 0 • Nilai akhir dipetakan ke 20 - 100
Bagian Deskripsi Deskripsi osn0816.html Berikut ini adalah sebuah fungsi untuk menjawab beberapa pertanyaan dalam set ini:
Deskripsi osn0831.html Di sebuah daerah, ada tepat 5 buah sungai, bernama A, B, C, D, E dan tepat 5 buah kota, bernama F, G, H, I, J. Kota F, H, dan J masing-masing dialiri oleh 3 buah sungai. Sungai B, C, dan D masingmasing mengaliri 2 buah kota. Kota I hanya dialiri oleh sungai B dan E, dan kota G hanya dialiri oleh sungai D dan A. Jika sebuah sungai yang mengaliri sebuah kota meluap, maka kota tersebut akan kebanjiran.
Bagian Pertanyaan 1. "Angap bahwa semua burung bersayap dua, dan semua serangga bersayap genap. Anggap juga bahwa tidak semua burung tidak bisa terbang, tetapi semua serangga bisa terbang. Tetapi, ada juga hewan lain yang bisa terbang, meskipun hewan itu bukan burung dan bukan serangga." Berdasarkan pernyataan di atas, manakah pernyataan yang salah? A. "Setiap hewan yang tidak bisa terbang tetapi bersayap dua adalah burung." B. "Setiap hewan yang tidak berwayap dua tetapi bisa terbang bukan burung." C. "Jika seekor hewan tidak bisa terbang dan bersayap ganjil, hewan itu bukan burung." D. "Tidak semua hewan bersayap genap adalah burung." E. "Tidak semua hewan yang bersayap 6 dan bisa terbang adalah serangga."
2. Ada 5 orang di sebuah pertemuan, bernama A, B, C, D, dan E. o A berkata bahwa dia mengenal B dan E, tetapi C tidak mengenal E. o B berkata bahwa C, D, dan E mengenal satu sama lain. o C berkata behwa dia tidak mengenal E. o D berkata behwa A tidak mengenal C. o E berkata behwa dia mengenal C, dan A juga mengenal C. Jika ada tepat dua orang berbohong, siapakah keduanya itu? A. B. C. D. E.
B dan E B dan D A dan E A dan B C dan E
Halaman 1 dari 9
Sesi 3
OSN VII
3. Ada 1000 buah kubus yang masing-masing berukuran 1 cm x 1 cm x1 cm. Setiap sisi dari setiap kubus dicat dengan warna yang berbeda-beda: merah, biru, hijau, kuning, oranye, dan putih. Kubuskubus itu disusun sehingga membentuk sebuah kubus besar berukuran 10c cm x 10 cm x 10 cm. Berapa cm2 luas maksimal daerah berwarna merah yang mungkin dilihat oleh seorang pengamat? A. B. C. D. E.
488 384 502 592 600
4. Dari bilangan 1 sampai dengan 2008, ada berapa bilangan yang hanya terdiri dari angka-angka ganjil? A. B. C. D. E.
280 208 99 504 1004
5. Jika setiap digit dari deret bilangan 1, 2, 3, ..., 100 dijumlahkan, maka berpakah hasilnya? A. B. C. D. E.
901 5050 200 910 505
6. (Soal ini mengacu pada Deskripsi osn0816.html di atas) Hasil pemanggilan f(10,6) adalah: A. B. C. D. E.
848 60 160 6000 1012
7. Perhatikan algoritma rekursif berikut: 1. function f(m,n: integer): integer; 2. begin 3. if (m = 0) or (n = 0) then f := 1 4. else f := f(m-1, n-1) + f(m-1, n); 5. end; Hasil pemanggilan f(6,6) adalah: A. B. C. D. E.
64 12 15 35 81
Halaman 2 dari 9
Sesi 3
8. Perhatikan algoritma berikut ini:
Jika nilai awal n adalah 0 dan nilai i adalah 686; nilai n pada akhir algoritma adalah A. B. C. D. E.
12 11 13 14 15
9. Perhatikan algoritma sebuah fungsi berikut ini:
nilai coba(19, 4, 15) adalah A. B. C. D. E.
150 112 78 22 18
10. Jika pada program didefinisikan sebuah array berikut ini:
dan diberikan sebuah fungsi hitung berikut ini:
Nilai hitung(4) adalah
Halaman 3 dari 9
OSN VII
Sesi 3
A. B. C. D. E.
OSN VII
87 66 72 82 79
11. Diberikan sebuah algoritma
Nilai yang dicetak ke layar jika a, b, c, d masing-masing 1, 2, 3, 4 adalah A. B. C. D. E.
66 58 32 28 82
12. Diberikan sebuah array A berikut ini:
dan algoritma berikut ini:
Saat A[6] bernilai 18 makaaa A[8] bernilai ... A. B. C. D. E.
14 13 11 12 10
13. Perhatikan algoritma di bawah ini:
Jika diberikan a, b, c ketiganya adaah 1, maka jika nilai n adalah 20, nilai satuan dari d pada akhir algoritma adalah ...
Halaman 4 dari 9
Sesi 3
A. B. C. D. E.
9 8 4 6 10
14. Diberikan array berikut:
dan diberikan algoritma berikut:
Nilai elemen ke 9 dari array tersebut (atau a[9]) adalah... A. B. C. D. E.
7 8 4 6 5
15. Diberikan algoritma berikut: (*** Algoritma ini telah mengalami revisi!! ***)
Banyaknya karakter '*' yang dicetak ke layar adalah ... A. B. C. D. E.
128 121 149 118 102
Halaman 5 dari 9
OSN VII
Sesi 3
OSN VII
16. Perhatikan algoritma berikut ini:
Jika nilai awal x, y, z ketiganya adalah 1; nilai z pada akhir algoritma adalah A. B. C. D. E.
1593 983 606 2580 140
17. Perhatikan algoritma berikut ini:
Jika nilai x, y, dan z diberikan masing-masing 2, 6, 21; nilai yang dicetak ke layar adalah A. B. C. D. E.
17 13 -25 25 -17
18. (Soal ini mengacu pada Deskripsi osn0831.html di atas) Pernyataan manakah yang pasti salah? A. B. C. D. E.
Ada tepat 3 sungai yang meluap tetapi kota H tidak kebanjiran Ada tepat 1 sungai yang meluap dan 4 kota yang kebanjiran Ada tepat 2 sungai yang meluap dan 4 kota yang kebanjiran Kota F, G, dan H kebanjiran tetapi sungai A, B, dan C tidak meluap Sungai A dan E meluap dan semua kota kebanjiran
19. (Soal ini mengacu pada Deskripsi osn0831.html di atas) Jika ada tepat 4 kota yang kebanjiran, berapa jumlah minimal sungai yang meluap? A. B. C. D. E.
1 2 3 4 5
Halaman 6 dari 9
Sesi 3
OSN VII
20. (Soal ini mengacu pada Deskripsi osn0831.html di atas) Jika semua sungai-sungai yang mengaliri kota F meluap, berapa banyak minimal kota yang kebanjiran? A. B. C. D. E.
2 1 3 4 5
21. (Soal ini mengacu pada Deskripsi osn0831.html di atas) Jika kota H dialiri oleh sungai A, C, dan E, sungai manakah yang tidak mugkin mengaliri F dan J sekaligus? A. B. C. D. E.
C A B D E
22. (Soal ini mengacu pada Deskripsi osn0831.html di atas) Dua kota manakah yang pasti dialiri sungai yang sama? A. B. C. D. E.
F dan H F da I G dan H G dan I H dan I
23. (Soal ini mengacu pada Deskripsi osn0831.html di atas) Jika sungai A mengaliri tepat 4 kota di daerah tersebut, berapa kota kah yang dialiri oleh sungai E? A. B. C. D. E.
3 1 2 4 5
24. Seorang tukang cat dapat mengerjakan pengecatan suatu ruangan dalam x jam. Tepat pada jam ke 2, catnya habis sehingga terpaksa menunggu kaleng cat berikutnya yang sedang dipesan. Berapa bagiankah pekerjaan yang belum ia selesaikan? A. B. C. D. E.
(x - 2)/x (2 - x)/x x-2 (x - 2)/2 x/2
25. Suatu kubus A berada di dalam bola dan tepat setiap ujung kubis mengenai dinding bola. Bola tersebut berada dalam suatu kubus B dan tepat keenam dinding kubus B menempel pada bola. Dengan asumsi dinding bola maupun kubus sangat tipis hingga bisa diabaikan, berapa kalikah volume kubus B terhadap volume kubus A? A. B. C. D. E.
2.828 3.14 4 8 2.09
Halaman 7 dari 9
Sesi 3
OSN VII
Soal Isian Singkat OSN2008: Olimpiade Sains Nasional 2008 Petunjuk: Jawablah sesingkat-singkatnya untuk memungkinkan penilaian secara otomatis 1. Mengacu pada Masalah Reverse & Add, berapakah harga bilangan palindrom yang diperoleh jika dimulai dari N=750? 2. Jika setiap digit ganjil dari deret bilangan ganjil 1, 3, 5, ..., 9999 dijumlahkan, maka berapakah hasilnya? 3. Masalah Reverse & Add: Mereverse suatu bilangan bulat positif N adalah membalikkan urutan digitnya (direverse) membentuk bilangan baru M. Misalnya 123 direverse menjadi 321 dan 130 direverse menjadi 031 (yaitu 31). Jika N direverse menjadi M dan kemudian keduanya dijumlahkan membentuk N baru, dan direverse kembali menjadi M, lalu dijumlahkan kembali secara berulang-ulang hingga menghasilkan bilangan yang jika direverse menghasilkan bilangan yang sama (yaitu bilangan palindrom). Jika bilangan N awalnya adalah 195 berapakah bilanga palindromnya? 4. Deret 3n+1: Sebuah deret bilangan bulat positif dihasilkan dengan aturan sbb. o Dimulai dari satu bilangan a > 0 o Jika a merupakan bilangan genap maka bilangan berikutnya adalah a/2 o Jika a merupakan bilangan ganjil maka bilangan berikutnya adalah 3a+1 o Bilangan-bilangan berikutnya dihasilkan dengan aturan di atas. Jika dimulai dari deret barharga 55 sebagai yang pertama berapakah harga bilangan yang ke 10 dalam deret? 5. Mengacu pada deret bilangan 3n+1 pada soal sebelumnya, ada berapa bilangan yang akan muncul mulai dari 100 sampai dengan angka 10? 6. Mengacu pada deret bilangan 3n+1 pada soal sebelumnya, jika dimulai dari 55 sebagai yang pertama pada bilangan keberapa bilangan > 1000 muncul pertama kalinya? 7. Multiplying Game: Amir dan Badu suka sekali akan permainan berikut ini. Mula-mula keduanya mendapatkan sebuah bilangan bulat positif secara sembarang. Bilangan itu kita sebut N. Mulai dari p=1, secara bergantian keduanya menentukan satu bilangan k antara 2 s.d. 9 dan memperkalikannya ke p (sehingga berikutnya p berharga p semula dikali k). Permainan berlanjut selama p < N dan pemain yang menang adalah yang pertama menyebahkan p >= N. Dengan asumsi bahwa mereka sudah mahir memilih yang bilangan k terbaik pada setiap gilirannya (tidak akan membuat kesalahan yang tidak perlu), pada suatu kesempatan didapati N = 17 dan Badu kebagian yang pertama yang harus memilih k. Siapkah yang akan kalah? (Jawab: Amir atau Badu). 8. Mengacu pada permainan Multiplying Game di soal sebelumnya antara Amir dan Badu, untuk N = 162 dan Badu yang memulai siapakah yang akan menang? 9. Soal Tangga Baru Pak Dengklek: Sudah bosan membuat tangga yang biasa-biasa saja, Pak Dengklek hedak membuat tangga dengan aturan jarak sebagai berikut. Tinggi tangga adalah bilangan bulat (positif) dinyatakan dalam suatu satuan. Tinggi anak tangga adalah bilangan bulat namun beda ketinggian suatu anak tangga dengan anak tangga berikutnya/sebelumnya tidak boleh berselisih lebih dari satu satuan (anak tangga berikutnya bisa lebih pendek 1 satuan, bisa lebih panjang 1 satuan atau sama tinggi). Aturan berikutnya, anak tangga pertama harus tepat 1 satuan dari ujung bawah tangga (yaitu pada lantai) dan terakhir harus tepat 1 satuan dari ujung atas tangga. Misalnya jika tinggi tangga 4 maka tinggi dari anak-anak tangga bisa, 1, 2, dan 1 (ada 3 anak tangga). Ada berapa minimal banyaknya anak tangga jika tinggi tangga 10? 10. Notasi prefiks sering digunakan dalam menyatakan suatu ekspresi aritmatika dengan menuliskan operator aritmatika di depan dari kedua operand-nya. Misalnya untuk "a + b" ditulis "+ a b" (Baca: "+_a_b" dengan "_" adalah spasi). Dengan notasi prefiks maka tanda kurung tidak diperlukan lagi karena otomatis yang akan menjadi operand dari suatu operator adalah yang mengikutinya misalnya "(a + b) * c" akan ditulis "* + a b c" (Baca: "*_+_a_b_c" dengan "_" adalah spasi) sementara untuk "a + b * c" adalah "+ a * b c" (Baca: "+_a_*_b_c" dengan "_" adalah spasi). Berapakah perhitungan dari ekpresi aritmatika dalam notasi prefiks "+ * / 14 + 9 12 + - / 3 + 4 2 / 4 8 3 / 22 1" (Baca: "+_*_/_14_+_9_12_+_-_/_3_+_4_2_/_4_8_3_/_22_1" dengan "_" adalah spasi) 11. Masalah Makanan-makanan di OSN: Selama penyelenggaraan suatu OSN, kepada para OSN diberikan menu makanan yang berisi 6 pilihan: A, B, C, D, E, dan F. Panitia yang bertugas menyiapkan makanan telah mendapatkan informasi sebagai berikut. o Mereka yang menyukai B pasti menyukai juga E. o Mereka yang menyukai E pasti tidak suka C. o Beberapa dari yang menyukai E juga menyukai A. o Semua yang menyukai C, suka juga D. o Beberapa dari yang suka D menyukai juga E. o Beberapa yang menyukai A, tidak suka C. o Semua yang menyukai D, juga menyukai F. Budiman adalah peserta OSN yang menyukai B. Suatu hari disajikan makanan-makanan A, C, D, E
Halaman 8 dari 9
Sesi 3
OSN VII
dan F. Manakah di antaranya yang ia tidak sukai? 12. Dari soal Makanan-makanan di OSN di atas, apabila ternyata Tono yang juga peserta OSN, menyukai D, apakah ia juga menyukai C? (Jawab dengan Y untuk Ya, T untuk tidak, atau X untuk tidak bisa ditentukan. 13. Empat orang hendak menyeberangi sebuah jembatan yang sempit dari tepi A ke tepi B sesegera mungkin. Sayangnya hari itu turun hujan deras dan mereka tidak mau kehujanan. Di A maupun di B terdapat tempat berteduh dari hujan. Beruntungnya seseorang membawa payung walaupun hanya cukup untuk berdua saja sekali menyeberang. Jadi dua orang menyeberang dan dari A ke B, kemudian satu orang kembali dari B ke A untuk membawa payung untuk digunakan yang lainnya. Kecepatan secara perorangan berbeda-beda tetapi saat menyeberang tentunya yang lebih cepat harus mengikuti yang lebh lambat. Waktu tempuh menyeberangi jembatan secara perorangan adalah 5, 1, 10, dan 2 (dalam satuan waktu tetentu). Jika mereka menemukan urutan penyeberangan yang mencapai waktu total minimal, berapakah panjang waktu minimal itu sehingga keempatnya tiba di B? 14. Berapakah 3 digit terkanan dari 1110? 15. Diberikan algoritma mencetak '*' berikut: 1. 2. 3. 4. 5. 6. 7. 8. 9.
i := 1; while i < n do begin j := n; while j > 0 do begin if (j mod 2) = 1 then write('*'); j := j div 2; end; i := i + 2; end; Jika banyaknya '*' yang dicetak adalah 104, berapakah n harus diberi harga?
16. Diberikan algoritma fungsi wah berikut ini.
17. 18. 19.
20.
Hasil dari pemanggilan fungsi wah(3,3) adalah... (mohon diabaikan ";" di belakang pemangilan rekursif fungsi "wah(...)+1") Mengacu pada deskripsi fungsi wah pada soal sebelumnya, banyaknya pasangan x dan y yang berbeda, yang menyebabkan pemanggilan wah(x,y) bernilai 3 adalah .... Diberikan persamaan ABCDEF x 5 = FABCDE, di mana setiap huruf mewakili satu digit (huruf yang berbeda boleh mewakili digit yang sama), dan A ≠ 0, digit apakah yang diwakili oleh B? Sebuah sungai dimulai dari sebuah mata air. Setelah mengalir 1 km, sungai itu bercang dua. Untuk setiap cabang, setelah mengalir 1 km, cabang itu bercabang dua lagi. Begitu seterusnya dengan cabang-cabang yang terbentuk. Jarak dari sumber mata air ke laut, melalui cabang yang mana saja adalah 8 km. Berapakah panjang total aliran air sungai tersebut. Andi adalah kakak Tono dan Didi adalah adik Tono. Andi memiliki 5 orang adik. Didi memiliki 2 orang adik dan 7 orang kakak. Ada berapa orang di dalam keluarga Tono yang lebih tua daripada Tono tetapi lebih muda daripada Andi, jika tidak ada yang kembar di dalam keluarga Tono?
Halaman 9 dari 9
SOAL SESI 1
OLIMPIADE SAINS NASIONAL VIII BIDANG INFORMATIKA 5 AGUSTUS 2009 DKI JAKARTA
Selamat Bekerja, Berkompetisi, Jadilah Yang Terbaik!
Sesi 1
OSN VIII
1. Ada 27 buah bola tenis. 1 di antaranya lebih berat dibanding yang lainnya (ke‐26 bola lainnya memiliki berat yang sama). Andaikan Anda memiliki sebuah timbangan yang terdiri atas dua buah nampan dan dapat menentukan nampan manakah yang lebih berat/ringan dibanding yang lainnya (tetapi tidak dapat menentukan besarnya perbedaan berat) seperti yang ditunjukkan pada gambar berikut:
Harus berapa kalikah paling sedikit Anda perlu melakukan penimbangan untuk menentukan bola manakah yang berbeda beratnya? Tuliskan jawabannya dalam bentuk angka. Untuk soal 2 sampai 6: Sebuah perusahaan ingin membagi karyawan‐karyawannya menjadi beberapa tim, dan ingin agar tim‐tim tersebut dapat bekerja seefektif mungkin. Agar dapat bekerja seefektif mungkin, setiap anggota dalam sebuah tim harus menyukai anggota lainnya di dalam tim tersebut. Dari antara 8 karyawan yang sudah ada, A, B, C, D, E, F, G, H, sang manager telah memperhatikan bahwa secara umum setiap karyawan saling menyukai satu sama lain, kecuali pasangan‐pasangan berikut ini: A dan H, F dan G, C dan E, B dan E, F dan D, B dan H, F dan B, C dan G, A dan F. Sebuah tim didefinisikan sebagai kumpulan dua atau lebih karyawan. 2. Sang manager harus membagi kedelapan karyawan tersebut minimal ke dalam berapa tim agar tidak ada dua orang anggota dalam sebuah tim yang tidak menyukai satu sama lain, dan setiap karyawan menjadi anggota tepat sebuah tim? Tuliskan jawabannya dalam bentuk angka. 3. Dari antara karyawan‐karyawan tersebut, misalkan sang manager ingin memecat satu orang karyawan, agar banyaknya tim yang dibuatnya berkurang. Sebutkan siapa sajakah yang jika menjadi seorang karyawan yang dipecat tersebut, tidak dapat mengurangi jumlah tim yang harus dibuat? Tuliskan jawabannya terurut secara alfabetis, dengan huruf kapital, dipisahkan oleh sebuah spasi. 4. Sang manager tidak jadi memecat satu orang, tetapi dia ingin memecat dua orang sekaligus agar tidak ada yang merasa dikucilkan. Namun, kedua orang itu haruslah tidak menyukai satu sama lain, untuk mengurangi resiko pemberontakan. Pasangan mana sajakah yang, meskipun sudah dipecat, tetap tidak bisa mengurangi banyaknya tim yang harus dibuat sang manager? Tuliskan jawabannya terurut secara alfabetis, dengan huruf kapital, dipisahkan oleh sebuah spasi. 5. Jika tiba‐tiba setiap pasang karyawan yang saling menyukai satu sama lain tiba‐tiba membenci satu sama lain, dan setiap pasang karyawan yang saling tidak menyukai satu sama lain tiba‐tiba menyukai satu sama lain, sang manager harus mengubah konfigurasi tim. Ada berapa tim paling sedikit yang harus dibentuk? Tuliskan jawabannya dalam bentuk angka.
6. Dalam tim‐tim baru yang dibentuk ini, siapa sajakah karyawan‐karyawan yang berada di tim yang sama dengan B? Tuliskan jawabannya terurut secara alfabetis, dengan huruf kapital, dipisahkan oleh sebuah spasi. Halaman 1 dari 11
Sesi 1
OSN VIII
Untuk soal 7 sampai 10: Sebuah keluarga yang terdiri atas ayah, ibu, putra dan putri hendak menyeberangi sebuah jembatan gantung di waktu malam. Karena sempitnya jembatan tersebut, hanya 2 orang yang dapat melewatinya dalam suatu waktu secara bersamaan. Sang ayah dapat menyeberangi jembatan dalam 1 menit, ibu dalam 2 menit, putra dalam 4 menit, dan putri dalam 5 menit. Apabila ada lebih dari 1 orang yang menyeberang jembatan secara bersamaan, kecepatan kedua orang tersebut menyeberang sama dengan kecepatan orang yang lebih lambat. Sayangnya, keluarga tersebut hanya membawa 1 buah senter sementara malam begitu gelap sehingga tidak seorang pun dapat menyeberang tanpa membawa senter. 7. Berapa menitkah waktu minimal yang dibutuhkan agar seluruh anggota keluarga tersebut dapat pindah ke sisi lain jembatan? Tuliskan jawabannya dalam bentuk angka. 8. Berapa menitkah waktu tempuh orang/pasangan yang pertama kali menyeberang jika diinginkan agar waktu tempuh total seminimal mungkin? Tuliskan jawabannya dalam bentuk angka. 9. Siapakah orang pertama yang kembali dari sisi lain jembatan untuk mengantar senter? Tuliskan jawaban dalam huruf kecil seluruhnya. 10. Terjadi berapa kali penyeberangankah (tiap perpindahan orang/pasangan dari satu sisi ke sisi lain dihitung 1 kali penyeberangan) untuk mendapatkan total waktu tempuh yang minimal? Tuliskan jawabannya dalam bentuk angka. 11. Berapakah digit terakhir (angka satuan) dari
? Tuliskan jawabannya dalam bentuk
angka. 12. Sebuah kandang ayam memiliki kapasitas untuk menampung maksimum 10 ekor ayam. Jika sebuah peternakan memiliki 21 kandang ayam dan 100 ekor ayam, ada minimal berapa kandang ayamkah yang harus berisi 4 ekor ayam atau lebih agar setiap ayam kebagian kandang? Tuliskan jawabannya dalam bentuk angka. 13. Sebuah lembaga sepak bola mengadakan survey kepada para pelajar di sebuah sekolah, untuk mengetahui seberapa populer olahraga sepak bola di antara remaja putra dan putri. Dari 100 pelajar yang disurvey, ternyata banyaknya remaja putra yang menyukai sepak bola sama banyak dengan banyaknya remaja putri yang tidak menyukai sepak bola, dan perbandingan antara banyaknya remaja putra yang menyukai sepak bola dan tidak menyukai sepak bola adalah 3 : 1. Jika 52% pelajar yang disurvey adalah putri, ada berapa pelajar putri yang menyukai sepak bola? Tuliskan jawabannya dalam bentuk angka. ? Tuliskan jawabannya dalam 14. Berapakah digit terakhir dari bentuk angka. 15. x mod (x div 1000 ‐ 1) = 1001 Untuk membuat persamaan di atas menjadi benar, berapakah nilai bilangan bulat positif x yang paling kecil? Tuliskan jawabannya dalam bentuk angka. Untuk soal 16 dan 17: Ditemukan bahwa sebuah tes yang digunakan untuk mengecek apakah seseorang terkena penyakit flu babi memiliki tingkat keakuratan 80% ‐‐ yang artinya jika seseorang yang berpenyakit flu babi mengambil tes ini, pada 80% kesempatan (misalnya, 8 dari 10 kali tes), hasil tesnya akan positif dan sebaliknya jika seseorang tidak berpenyakit flu babi, hasil tesnya akan negatif pada 80% kesempatan. Seseorang diambil secara acak dari sebuah grup yang 10% di antaranya adalah penderita penyakit flu babi. 16. Jika hasil tes orang yang diambil secara acak tersebut adalah positif, berapakah kemungkinan dia menderita flu babi? (tuliskan dalam bentuk pecahan paling sederhana, berupa dua buah bilangan bulat yang dipisahkan dengan sebuah tanda /, tanpa spasi) Halaman 2 dari 11
Sesi 1
OSN VIII
17. Jika hasil tes orang yang diambil secara acak tersebut adalah negatif, berapakah kemungkinan dia menderita flu babi? (tuliskan dalam bentuk pecahan paling sederhana, berupa dua buah bilangan bulat yang dipisahkan dengan sebuah tanda /, tanpa spasi) Untuk soal 18 sampai 21: Diberikan 4 buah ekspresi : 1. N^N 2. N! + 1 3. N^(N!) ‐ (N!)^N 4. 2^(N!) ‐ 3^N N adalah bilangan bulat positif. 18. Supaya #1 memiliki nilai terbesar dibanding semuanya, maka berapakah batasan N maksimum yang bisa diberikan? Tuliskan jawabannya dalam bentuk angka. 19. Supaya #2 memiliki nilai terbesar dibanding semuanya, maka berapakah batasan N maksimum yang bisa diberikan? Tuliskan jawabannya dalam bentuk angka. 20. Dengan N nilai yang sangat besar, maka ekspresi mana yang akan menghasilkan nilai paling kecil? Tuliskan jawabannya dalam bentuk angka. 21. Dengan N nilai yang sangat besar, maka ekspresi mana yang akan menghasilkan nilai paling besar? Tuliskan jawabannya dalam bentuk angka. 22. Berapakah angka yang sesuai untuk melanjutkan deret berikut: 1, 2, 6, 24, 120, ? 23. Kontingen olimpiade sains nasional dari suatu propinsi terdiri dari 8 siswa yang akan mengikuti lomba tingkat SMA, 3 siswa yang mengikuti lomba tingkat SMP, dan 2 siswa yang mengikuti lomba tingkat SD. Berapa kombinasi yang dapat dihasilkan, untuk mementukan satu wakil siswa SMA, satu wakil siswa SMP, dan satu wakil siswa SD yang akan mewakili kontingen propinsi tsb untuk acara Pembukaan? Tuliskan jawabannya dalam bentuk angka. 24. Jumlah kontingen tingkat SMA dari suatu propinsi terdiri dari bidang Matematika: 4 siswa, Fisika: 4 siswa, Kimia: 3 siswa, Biologi: 3 siswa, Komputer: 3 siswa, Astronomi: 2 siswa, Kebumian: 2 siswa, dan Ekonomi 4 siswa. Berapa kombinasi yang dapat dihasilkan untuk menentukan satu siswa yang akan mewakili siswa tingkat SMA dari propinsi tersebut dalam upacara Pembukaan? Tuliskan jawabannya dalam bentuk angka. 25. Jika terdapat 10 pertanyaan yang masing‐masing dapat dijawab benar atau salah (B atau S), berapakah kemungkinan kombinasi jawaban yang dapat dibuat? Tuliskan jawabannya dalam bentuk angka. 26. Berapakah banyaknya bilangan ganjil antara 1000 dan 9999 (termasuk 1000 dan 9999 itu sendiri) yang semua angkanya berbeda? Tuliskan jawabannya dalam bentuk angka. 27. Berapakah banyaknya bilangan ganjil antara 1000 dan 9999 (termasuk 1000 dan 9999 itu sendiri) jika boleh ada angka yaang berulang? Tuliskan jawabannya dalam bentuk angka. 28. Berapakah banyak string yang dapat dibentuk dari kombinasi huruf‐huruf pada kata ‘kerang’ sedemikian sehingga huruf‐huruf vokal terletak pada posisi saling bersebelahan? Tuliskan jawabannya dalam bentuk angka. 29. Ada berapa kombinasi untuk dapat memilih 3 dari 4 elemen himpunan S = {p, q, r, s}? Tuliskan jawabannya dalam bentuk angka.
Halaman 3 dari 11
Sesi 1
OSN VIII
30. Berapakan jumlah kemungkinan membentuk 3 angka dari 5 angka berikut: 1, 2, 3, 4, 5, jika boleh ada pengulangan angka. Tuliskan jawabannya dalam bentuk angka. 31. Jika Anda melemparkan x buah dadu dan menjumlahkan angka‐angka yang keluar, peluang mendapatkan angka‐angka dadu berjumlah 31 sama dengan peluang mendapatkan angka‐angka dadu berjumlah 46. Berapakah nilai x? Tuliskan jawabannya dalam bentuk angka. 32. Proyek pembangunan jalan di Kabupaten “Panjang Jalan” telah selesai. Hasil yang dicapai proyek ini luar biasa: Setiap pasang desa yang ada di Kabupaten “Panjang Jalan” dihubungkan oleh tepat sebuah ruas jalan. Jika ada 36 ruas jalan di Kabupaten “Panjang Jalan”, ada berapa desa di Kabupaten tersebut? Tuliskan jawabannya dalam bentuk angka. 33. Definisi tahun kabisat yang resmi adalah sebagai berikut. Jika angka tahun habis dibagi 4 tetapi tidak habis dibagi 100, maka tahun itu adalah tahun kabisat. Jika angka tahun habis dibagi 100 tetapi tidak habis dibagi 400, maka tahun itu bukan tahun kabisat. Jika angka tahun habis dibagi 400, maka tahun itu adalah tahun kabisat. Ada berapa tahun yang bukan tahun kabisat mulai tahun 1000 sampai dengan tahun 2000 (1000 dan 2000 termasuk)? Tuliskan jawabannya dalam bentuk angka. 34. Jika kita mempunyai deretan bilangan : 1 2 3 4 5 6 7 ... 999999 1000000, ada berapakah bilangan yang merupakan angka kuadrat (misalnya: 1, 4, 9, 16)? Tuliskan jawabannya dalam bentuk angka. Untuk soal 35 dan 36: function F1(a, b : integer) : integer; begin if (a < b) then begin F1 := F2(a, b) + 1; end else if (a < 2 * b) then begin F1 := F1(b, a) + 1; end else F1 := 0; begin end; function F2(b, a : integer) : integer; begin F2 := F1(2 * a, b) + 1; while (a < b) do begin F2 := F1(a, b); a := 2 * a; end; end; Halaman 4 dari 11
Sesi 1
OSN VIII
35. Berapakah hasil dari F2(1, 1)? 36. Berapakah hasil dari F1(3, 2)? 37. Berapakah nilai yang dikembalikan fungsi ini? function R() : integer; var j : integer; i : array [0..3] of integer; begin for j := 0 to 3 do i[j] := (j + 1) mod 4; i[i[i[i[0]]]] := i[i[i[i[1]]]]; i[i[i[i[2]]]] := i[i[i[i[3]]]]; R := i[0] + i[1] + i[2] + i[3]; end; 38. Perhatikan potongan kode program dalam pseudopascal berikut ini: k := 0; n1 := ?; n2 := 8; n3 := 45; for p1 := 1 to n1 do k := k + 1; for p2 := 1 to n2 do k := k + 1; for p3 := 1 to n3 do k := k + 1; Dengan nilai berapakah n1 harus diinisialisasi sehingga setelah potongan kode program tersebut dieksekusi, k bernilai 70?. 39. Perhatikan potongan kode program dalam pseudopascal berikut ini: k := 0; n1 := 8; n2 := 4; n3 := ?; for p1 := 1 to n1 do begin k := k + 1 for p2 := 1 to n2 do begin k := k + 1 for p3 := 1 to n3 do k := k + 1; end; end; Dengan nilai berapakah n3 harus diinisialisasi sehingga setelah potongan kode program tersebut dieksekusi, k bernilai 160?. Halaman 5 dari 11
Sesi 1
OSN VIII
40. Faktor persekutuan terbesar dari dua buah bilangan bulat non‐negatif m dan n (fpb(m, n)) didefinisikan sebagai bilangan bulat terbesar yang habis membagi kedua bilangan m dan n (dengan sisa 0). Diberikan algoritma untuk menghitung fpb berikut: Langkah 1: isi variabel t dengan nilai minimum dari (m, n) Langkah 2: bagi m dengan t. Jika sisa pembagian adalah 0, lanjutkan ke langkah 3; jika tidak, lanjutkan ke langkah 4 Langkah 3: bagi n dengan t. Jika sisa pembagian adalah 0, berhenti ‐‐ t adalah hasil; jika tidak, lanjutkan ke langkah 4. Langkah 4: kurangi nilai t dengan 1. Ulangi langkah 2. Apabila nilai n diisi dengan sebuah bilangan bulat positif yang dipilih secara acak, adakah nilai m tertentu yang dapat mengakibatkan algoritma di atas menghasilkan nilai yang salah? Apabila ada, tuliskan bilangan tersebut (dalam bentuk angka, apabila ada lebih dari satu, tuliskan mulai dari yang terkecil, masing‐masing dipisahkan dengan sebuah spasi). Apabila tidak ada, tuliskan kata “TIDAK ADA” (seluruhnya kapital, tanpa tanda kutip) Untuk soal 41 sampai 44: Turnamen Tinju (IPSC08A) Untuk menyemarakkan acara ulang tahun kemerdekaan RI, SMP Merdeka dan SMA Mulia mengadakan pertandingan tinju persahabatan. Masing‐masing sekolah (SMP Merdeka dan SMA Mulia) diwakili oleh 1 tim yang terdiri atas beberapa siswa yang memiliki berat badan berbeda‐beda. (Berat badang masing‐ masing siswa dapat dinyatakan dengan sebuah bilangan bulat positif, makin besar bilangan berarti makin berat.) Pertandingan ini dilakukan dalam cara yang sedikit berbeda dari pertandingan tinju biasa. Pada pertandingan ini, semua peserta langsung memasuki arena tinju bersama‐sama dan dapat melawan petinju manapun dari pihak lawan. Untuk tiap rondenya, petinju yang paling banyak menerima pukulan pada ronde itu dikeluarkan dari arena. Jika ada lebih dari satu petinju dengan banyak pukulan maksimal, petinju yang dikeluarkan adalah: jika semuanya berasal dari sekolah yang sama, akan dipilih salah satu secara acak; jika berasal dari sekolah berbeda, yang dikeluarkan adalah salah satu petinju SMA Mulia (dipilih secara acak). Pertandingan selesai jika salah satu tim telah kehabisan petinju di arena. Tim yang masih memiliki petinju di arena menang, sedangkan tim lawannya kalah. Dari hasil pengamatan tahun‐tahun sebelumnya, ditemukan bahwa jumlah pukulan yang diterima seorang petinju pada tiap rondenya berbanding terbalik secara proporsional dengan berat badannya (dengan kata lain, petinju dengan berat badan terbesar akan menerima pukulan paling sedikit, dan sebaliknya.) Dengan melihat data berat badan anggota kedua tim, tentukan tim mana yang akan memenangi pertandingan. Spesifikasi masukan Masukan diawali dengan dua buah bilangan bulat NP – banyaknya anggota tim SMP Merdeka – dan NA – banyaknya anggota tim SMA Mulia. Dua baris berikutnya berisikan data berat badan masing‐masing petinju. Baris yang pertama terdiri atas NP buah bilangan bulat positif yang menyatakan berat badan petinju‐petinju dari SMP Merdeka. Sedangkan baris kedua berisi NA buah bilangan bulat positif yang menyatakan berat badan petinju‐petinju SMA Mulia. Halaman 6 dari 11
Sesi 1
OSN VIII
Spesifikasi keluaran Jika SMP Merdeka yang menang, tuliskan string “MERDEKA” (seluruhnya berupa huruf kapital, tanpa tanda kutip). Jika SMA Mulia yang menang, tuliskan string “MULIA” (seluruhnya berupa huruf kapital, tanpa tanda kutip). Jika bukan keduanya, tuliskan string “ENTAH” (seluruhnya berupa huruf kapital, tanpa tanda kutip). Contoh Masukan 1 1 1 1
Contoh Keluaran MERDEKA
Contoh Masukan 3 2 1 3 2 5 5
Contoh Keluaran MULIA 41. Apakah keluaran program apabila data yang diberikan adalah: 5 5 2 8 12 10 24 2 6 11 26 24 42. Apakah keluaran program apabila data yang diberikan adalah: 7 5 2 2 7 3 12 5 4 2 5 6 5 8 43. Apakah keluaran program apabila data yang diberikan adalah: 9 8 2 8 17 2 26 6 10 55 66 2 5 13 15 11 4 15 10 44. Apakah keluaran program apabila data yang diberikan adalah: 12 7 2 3 2 27 22 29 51 33 34 74 40 93 2 7 10 21 5 31 12 Halaman 7 dari 11
Sesi 1
OSN VIII
Untuk soal 45 sampai 47: Diberikan n buah bilangan bulat: x1, x2, ..., xn, dimana n adalah bilangan genap. Andaikan kita hendak mengelompokkan n bilangan ini menjadi n/2 pasangan dan kemudian menjumlahkan kedua bilangan pada masing‐masing pasangan. Nilai dari sebuah pengelompokan adalah nilai maksimum dari penjumlahan‐ penjumlahan tiap pasangan tersebut. Sebagai contoh, jika bilangan yang menjadi masukan adalah 5, 7, 8, ‐2, 6, 4, 5, 2 dan dikelompokkan menjadi (5,‐2), (7,4), (5,6), (2,8), maka nilai hasil penjumlahan tiap‐tiap pasang adalah 3, 11, 11, dan 10. Dengan demikian, nilai pengelompokan ini adalah nilai maksimum dari {3, 11, 11, 10} yaitu 11. Untuk tiap himpunan bilangan yang disediakan, tentukan pengelompokan yang harus dilakukan sehingga nilai pengelompokan menjadi seminimal mungkin. 45. Berapakah nilai pengelompokan dari 103, 24, 77, 65, 12, 108, 69, 25, 66, 83? 46. Berapakah nilai pengelompokan dari 83, 112, ‐16, 72, 161, 75, 152, ‐23, 77, 247 47. Berapakah nilai pengelompokan dari 19, 81, 2, 41, 61, 59, 28, 69, 76, 88
Untuk soal 48 sampai 50: Ada sebuah permainan yang dimainkan 2 orang. Anggaplah orang yang mendapat giliran pertama bernama Budi, dan yang kedua bernama Siska. Diberikan 2 angka yang berlainan, A dan B, A < B. Kemudian, kedua pemain bergantian mengurangi angka yang lebih besar dengan kelipatan angka yang lebih kecil (tidak boleh 0 dan hasilnya tidak boleh lebih kecil dari 0). Orang yang berhasil mengurangi salah satu angka tersebut menjadi 0 adalah pemenangnya. Sebagai contoh dari angka 25 dan 7: 25 7 Budi mengurangi 25 dengan 7 * 1 = 7 18 7 Siska mengurangi 18 dengan 7 * 2 = 14 4 7 Budi mengurangi 7 dengan 4 * 1 = 4 4 3 Siska mengurangi 4 dengan 3 * 1 = 3 1 3 Budi mengurangi 3 dengan 1 * 3 = 3 1 0 Budi menang. Seorang pemain dikatakan bermain optimal apabila untuk tiap langkahnya, pengurangan yang dilakukan akan memberikan peluang maksimal baginya untuk menang (dan sebaliknya, peluang minimal untuk kalah). Catatan: setelah dilakukan pengurangan, ada kemungkinan A = B, pada kasus ini, pemain bebas memilih angka yang mana yang akan dikurangi dan yang akan digunakan sebagai pengurang. 48. Diberikan 2 angka : 13 dan 10. Jika kedua pemain bermain optimal, siapakah yang akan menang? 49. Diberikan 2 angka : 25 dan 11. Jika kedua pemain bermain optimal, siapakah yang akan menang? 50. Diberikan 2 angka : 46 dan 20. Jika kedua pemain bermain optimal, setelah permainan berlangsung, selain angka 0, angka berapakah yang akan tersisa?
Halaman 8 dari 11
Sesi 1
OSN VIII
Untuk soal 51 sampai 53: Seorang pencuri memasuki sebuah toko yang menjual berbagai bahan pangan. Dia memiliki sebuah karung yang dapat digunakan untuk membawa bahan pangan apa saja seberat maksimum W kilogram (kg). Untuk setiap bahan pangan, sang pencuri mengetahui banyaknya bahan pangan yang tersedia di toko dan harga total dari masing‐masing bahan pangan. Sang pencuri ingin menentukan berapa kilogram dari masing‐ masing bahan pangan yang harus ia curi sehingga harga total dari bahan pangan yang ia curi menjadi maksimal. (Satuan terkecil yang dapat diambil dari sebuah bahan pangan adalah 1 kg) Sebagai contoh, andaikan pencuri tersebut dapat membawa 20 kg bahan pangan (W = 20) dan ada tiga macam bahan pangan yang tersedia: garam, beras, dan gula. Di dalam toko terdapat 18 kg garam dengan harga total Rp 24000, 10 kg beras dengan harga total Rp 15000 dan 15 kg gula dengan harga total Rp 18000. Kita dapat menyatakan nilai‐nilai ini dalam tabel berikut:
Garam
Beras
Gula
W = 20
Banyaknya (kg)
18
10
15
Harga (Rp)
24000
15000
18000
Jika pencuri mengisi karungnya dengan 18 kg garam dan 2 kg gula, ia akan membawa pergi bahan pangan senilai Rp 24000 + (2/15 * 18000) = Rp 24000 + 2400 = Rp 26400. Diberikan beberapa situasi yang dihadapi pencuri, tentukan harga total maksimum bahan pangan yang dapat dicurinya. 51. Berapakah total bahan pangan yang dapat dicuri apabila kondisi yang dihadapi pencuri adalah seperti yang tercantum pada tabel berikut? Tuliskan jawabannya dalam bentuk bilangan bulat. Apabila hasil berupa pecahan, ambil bagian bulatnya saja (misalnya jika hasilnya adalah 2.84, tuliskan 2)
A
B
C
W = 20
Banyaknya (kg)
15
10
18
Harga (Rp)
1800
1500
2400
52. Berapakah total bahan pangan yang dapat dicuri apabila kondisi yang dihadapi pencuri adalah seperti yang tercantum pada tabel berikut? Tuliskan jawabannya dalam bentuk bilangan bulat. Apabila hasil berupa pecahan, ambil bagian bulatnya saja (misalnya jika hasilnya adalah 2.84, tuliskan 2)
A
B
C
D
W = 30
Banyaknya (kg)
25
10
15
9
Harga (Rp)
3000
1400
1800
1200
Halaman 9 dari 11
Sesi 1
OSN VIII
53. Berapakah total bahan pangan yang dapat dicuri apabila kondisi yang dihadapi pencuri adalah seperti yang tercantum pada tabel berikut? Tuliskan jawabannya dalam bentuk bilangan bulat. Apabila hasil berupa pecahan, ambil bagian bulatnya saja (misalnya jika hasilnya adalah 2.84, tuliskan 2)
A
B
C
D
W = 30
Banyaknya (kg)
25
10
15
20
Harga (Rp)
2250
1100
1500
1900
Untuk soal 54 sampai 56: Adi, Budi, dan Choki bersekolah di sekolah yang sama. Semua jalan di kota tempat tinggal mereka bersifat searah (hanya dapat dilalui dari suatu titik ke titik lainnya sesuai arah yang ditentukan) sehingga rute perjalanan mereka dari rumah ke sekolah harus memperhatikan hal ini. Diberikan peta kota berikut ini. Huruf A, B, dan C secara berturut‐turut menandakan lokasi rumah Adi, Budi, dan Choki, dan S menunjukkan lokasi sekolah mereka. Arah jalan ditandakan dengan tanda panah.
54. Berapakah banyak rute berbeda yang dapat dilalui Adi untuk menuju sekolahnya? Tuliskan jawabannya dalam bentuk angka. 55. Berapakah banyak rute berbeda yang dapat dilalui Budi untuk menuju sekolahnya? Tuliskan jawabannya dalam bentuk angka. 56. Berapakah banyak rute berbeda yang dapat dilalui Choki untuk menuju sekolahnya? Tuliskan jawabannya dalam bentuk angka.
Halaman 10 dari 11
Sesi 1
OSN VIII
Untuk soal 57 sampai 60: Di sebuah desa antah berantah, terdapat 5 buah rumah yang terhubung satu sama lain baik secara langsung maupun tidak langsung melalui jalan‐jalan setapak. Diberikan peta desa berikut ini:
Angka yang tertulis di samping setiap ruas jalan adalah panjang jalan setapak tersebut (dalam kilometer). 57. Berapakah kilometerkah jarak minimum yang harus dilewati untuk mencapai rumah b dari a? 58. Berapakah kilometerkah jarak minimum yang harus dilewati untuk mencapai rumah d dari a? 59. Berapakah kilometerkah jarak minimum yang harus dilewati untuk mencapai rumah c dari a? 60. Berapakah kilometerkah jarak minimum yang harus dilewati untuk mencapai rumah e dari a?
Halaman 11 dari 11
SOAL SESI 1
OLIMPIADE SAINS NASIONAL IX BIDANG INFORMATIKA 3 AGUSTUS 2010 MEDAN, SUMATERA UTARA
Selamat Bekerja, Berkompetisi, Jadilah Yang Terbaik!
Sesi 1 1. Gudang olah raga X memiliki aturan penyimpanan bola sebagai berikut. Hanya satu bola boleh diletakkan di satu kotak putih atau kotak hitam. Bola volley hanya boleh dimasukkan ke kotak putih saja. Bola basket boleh diletakkan di kotak manapun. Dalam deretan kotak, dua kotak putih tidak boleh diletakkan saling bersisian. Jika terdapat 4 kotak hitam, 3 kotak putih, 2 bola volley dan 2 bola basket, berapa banyak konfigurasi penyimpanan bola dan urutan kotak yang mungkin? 2. Sebuah pesta reuni dihadiri oleh 101 pasang alumni yang datang bersama, serta 100 alumni yang datang sendiri. Semua hadirin di pesta tersebut saling bersalaman dengan hadirin yang lainnya. Jika tiap alumni tidak bersalaman dengan pasangannya, berapakah jumlah salaman yang terjadi? 3. Sebuah kalkulator memiliki konfigurasi tombol sebagai berikut. 7 8 9 4 5 6 1 2 3 0 Dari satu tombol, kita hanya boleh menekan tombol yang tepat bersisian (kiri, kanan, atas, bawah) dengan tombol tersebut pada kesempatan berikutnya. Berapakah kemungkinan urutan penekanan tombol jika kita dapat menekan tombol kalkulator maksimal tiga kali?
OSN IX satu butir kelapa ke dalam muatan truk. Jika pada awalnya sebuah truk mengangkut 10000 butir kelapa, berapakah jumlah kelapa yang tersisa di muatan truk ketika truk tersebut tiba di pos ke 60? 6. Berapakah banyak bilangan yang dapat dibagi 8 atau 6 di antara 1 hingga 2010? 7. Berapakah banyaknya bilangan biner berdigit tujuh yang tidak memiliki dua digit 0 yang saling bersisian? 8. Wagimin, menghabiskan 1/6 masa hidupnya sebagai seorang anak, 1/12 hidupnya sebagai pemuda, kemudian menikah setelah umurnya bertambah 1/7 hidupnya. 5 tahun kemudian, anaknya lahir. Namun sayangnya, anaknya mati muda. Umur anak Wagimin hanya setengah dari umur bapaknya. Karena depresi yang berat setelah kematian anaknya, 4 tahun kemudian, Wagimin pun meninggal. Berapakah umur Wagimin sebenarnya? 9. Perhatikan gambar peta berikut ini
X
Sebuah Robot diluncurkan dari bumi ke mars. Sayangnya, karena pendaratan yang tidak mulus, mesin robot rusak sehingga tidak bisa bergerak berlawanan arah setelah sekali bergerak ke satu arah. Artinya, jika robot bergerak ke utara, maka dia tidak bisa bergerak kembali ke selatan dan sebaliknya. Begitu pula jika ia bergerak ke barat, maka ia tidak akan bisa bergerak menuju timur, dan sebaliknya. Jika posisi awal robot ditandai dengan huruf X, maka berapa banyak kemungkinan rute yang diambil robot hingga ia tidak dapat bergerak lagi, berdasarkan peta tersebut?
4. Dua buah bilangan bulat jika dijumlahkan hasilnya -20. Jika dikalikan hasilnya 91. Berapakah nilai kedua bilangan tersebut? 5. Sebuah truk pengangkut kelapa mengangkut sejumlah kelapa dan mengantarkannya ke beberapa pos. Setiap kali truk berhenti di sebuah pos, truk wajib menurunkan separuh muatannya (dibulatkan ke bawah). Sebagai imbalannya, pos tersebut akan menambahkan
10. Dari 10 digit bilangan (0 hingga 9) diambil 7 digit secara acak dan tidak berulang. Jika semua kemungkinan urutan pengambilan kita urutkan
Halaman 1 dari 6
Sesi 1
OSN IX Apabila panjang masing-masing jembatan seragam yaitu 250 m dan Pak Dengklek memulai perjalanan antarpulaunya dari pulau A, berapa detikkah waktu minimum yang diperlukan Pak Dengklek untuk melewati jembatan menuju pulau B (pembulatan ke bawah dalam satuan detik) ?
secara ascending, dan diketahui kemungkinan ke-n adalah “4 2 7 6 3 5 1”, maka kemungkinan ke-(n+10) adalah? 11. Diberikan dua buah bilangan bulat positif (> 0), x dan y. Didefinisikan sebuah fungsi R(x, y) yang bernilai x apabila x = y, bernilai R(x-y, y) jika x > y, atau bernilai R(x, y-x) apabila x < y. Berapakah nilai dari R(36, 24)? 12. Lembaga Penerbangan dan Antariksa Nasional berencana meluncurkan 3 satelit komunikasi pada tahun 2100. Satelit pertama akan mengudara tanggal 3 Februari 2100 dan dapat mengorbit bumi dalam waktu 6 hari. Satelit kedua akan mengudara tanggal 13 Februari 2100 dan dapat mengorbit bumi dalam waktu 10 hari. Sedangkan satelit ketiga akan mengudara tanggal 18 Februari 2100 dan dapat mengorbit bumi dalam waktu 15 hari. Jika ketiga satelit tersebut diluncurkan dari lokasi yang sama dan memiliki jalur orbit yang sama, kapankah ketiga satelit tersebut akan berpapasan di angkasa? (format output: dd/mm/yyyy) 13. Lima buah pulau A, B, C, D, dan E terhubung melalui beberapa jembatan satu arah. Untuk alasan keamanan, setiap kendaraan bermotor yang melintasi jembatan-jembatan tersebut harus mengikuti batas kecepatan yang telah ditetapkan oleh dinas terkait. Karena kekuatan dan bahan tiap jembatan berbeda, batas kecepatan masing-masing jembatan pun berbeda-beda pula. Satu-satunya cara melintas dari satu pulau ke pulau lainnya adalah melewati jembatan tersebut. Diberikan batas maksimal kecepatan melintas pada masing-masing jembatan berikut: A B = 10 m/detik A C = 80 m/detik B E = 60 m/detik C B = 40 m/detik C D = 85 m/detik C E = 50 m/detik D B = 15 m/detik D E = 30 m/detik
14. Ada berapa banyak bilangan bulat di antara 1.000 dan 10.000 (termasuk 1.000 dan 10.000) yang habis dibagi 4 tetapi tidak habis dibagi 6? 15. Digit ke-4 dari belakang/kanan dari (19!) adalah… 16. Diberikan dua buah keranjang. Keranjang pertama berisi 1 bola biru, 2 bola merah, dan 3 bola hijau. Keranjang kedua berisi 2 bola biru, 3 bola merah, dan 1 bola hijau. Jika Anda mengambil 2 bola dari keranjang pertama secara acak dan 2 bola dari keranjang kedua secara acak, ada berapa kemungkinan kombinasi warna dari 4 bola yang telah Anda ambil? 17. Misalkan jumlah penduduk kota New York adalah 7 juta orang, dan setiap orang akan menyebar benih pohon untuk mendukung program penghijauan. Diketahui bahwa banyak benih pohon yang mampu disebar oleh seseorang paling sedikit 50.000 benih dan paling banyak 300.000 benih. Mereka menyepakati agar sebagian besar (Y) penduduk menyebar sebanyak X. Berapa nilai Y minimal agar penyebar benih sebanyak X maksimal? Untuk soal 18 sampai dengan 19: Ada 4 orang pemain tenis putra bernama M1, M2, M3, M4 dan 4 orang pemain tenis putri bernama F1, F2, F3, F4. Setiap pemain memiliki daftar pasangan yang kompak bermain bersama pada ganda campuran, diurutkan dari yang paling kompak sampai ke yang kurang kompak. Nama Urutan kekompakan M1 F3, F2, F1, F4 M2 F1, F3, F2, F4 M3 F2, F4, F1, F3 M4 F3, F1, F2, F4
Halaman 2 dari 6
Sesi 1
OSN IX
F1 M1, M3, M2, M4 F2 M2, M3, M4, M1 F3 M3, M1, M2, M4 F4 M1, M4, M3, M2 Diketahui 4 pemuda dan 4 pemudi ini sudah ditunjuk berpasang-pasangan oleh pelatih mereka. Mx dan Fy akan mengajukan keberatan jika Mx bermain dengan Fy lebih kompak dari Mx bermain dengan pasangannya, dan Fy bermain dengan Mx lebih kompak dari Fy bermain dengan pasangannya. Misalnya, jika M1 berpasangan dengan F1 dan M2 berpasangan dengan F3, M1 dan F3 akan mengajukan keberatan. 18. Misalkan keempat pasangan yang terbentuk adalah M1-F1, M2-F2, M3-F3, M4-F4. Ada berapa pasangan pemain yang akan mengajukan keberatan? 19. Ada berapa kemungkinan konfigurasi empat pasang pemain tersebut sehingga M1 dan F1 bukan berpasangan tetapi akan mengajukan keberatan? Untuk soal 22 sampai dengan 25: Berikut ini adalah peta pipa air yang melewati ladangladang A, B, C, D, E, F. Arah panah menunjukkan arah air yang mengalir dalam pipa tersebut. Untuk pipa yang menghubungkan B-F dan pipa yang menghubungkan C-E, air dapat mengalir ke arah mana saja tapi pada satu waktu hanya pada satu arah saja. Angka-angka yang tertera menunjukkan kapasitas (debit) pipa dalam kiloliter per detik. Misalnya, pipa yang menghubungkan B dan C dapat menyalurkan maksimum 12 kiloliter per detik, dari B ke C. Tanpa adanya penimbunan air di sebuah ladang, tentu banyak air yang masuk ke sebuah ladang harus tepat sama dengan banyak air yang keluar dari ladang tersebut. Misalnya, jika 4 kiloliter/detik masuk dari A ke B dan 5 kiloliter/detik masuk dari F ke B, maka 9 kiloliter/detik air harus keluar dari B ke C.
20. Tentu banyak air yang masuk ke A per detik harus sama dengan banyak air yang keluar dari D per detik. Berapa kiloliter/detik air paling banyak yang dapat mengalir masuk ke A (atau keluar dari D) yang dapat ditampung jaringan pipa ini? 21. Jaringan di atas diubah sehingga pipa yang menghubungkan B dan F hanya memiliki kapasitas 1 kiloliter/detik? Berapa kiloliter/detik air paling banyak yang dapat mengalir masuk ke A (atau keluar dari D) yang dapat ditampung jaringan pipa ini? 22. Ladang B membutuhkan sebanyak-banyaknya air, dan Anda dapat mengatur banyaknya air yang masuk ke A (atau yang keluar dari D) dan ke arah mana dan berapa banyak air mengalir dalam setiap pipa. Berapa kiloliter/detik air paling banyak yang dapat melalui B sehingga tidak melanggar kapasitas setiap pipa dalam jaringan? 23. Jika ladang B membutuhkan minimum aliran 10 kiloliter/detik air melalui B, dan Anda dapat mengatur banyaknya air yang masuk ke A (atau yang keluar dari D) dan ke arah mana dan berapa banyak air mengalir dalam setiap pipa. Berapa kiloliter/detik air paling banyakkah yang dapat mengalir melalui E sehingga tidak melanggar kapasitas setiap pipa dalam jaringan?
24. Perhatikan algoritma di bawah ini. st berisi string “OLIMPIADESAINS” dan panjang string disimpan dalam sebuah variabel k. Variabel tab adalah array integer berukuran yang cukup (lebih kecil atau sama dengan k). k:=length(st); Halaman 3 dari 6
Sesi 1
OSN IX function P(x, y: integer): integer; begin if (x = 0) then P := y else begin P := P(x-1, y+1); end; end; Berapakah nilai writeln(P(5,10), ‘ dan ‘, P(2010,2011)); ?
for i:=1 to k do tab[i]:=1; for i:=1 to k-1 do for j:=i+1 to k do if (st[i]<st[j]) and (tab[i]>=tab[j]) then tab[j]:=tab[i]+1; writeln(tab[k]); Apa output yang akan dihasilkan? 25. Perhatikan kode program di bawah ini “cek” adalah sebuah array dengan indeks mulai dari 1 s/d 100 yang setiap elemennya bernilai true atau false. Pada awal program semua elemen array “cek” diberi nilai “false”. for i:=2 to n do if not cek[i] then begin writeln('#',i); j:=i; repeat cek[j]:=true; j:=j+i; until j>n; end; Jika n berharga 50, berapa kalikah karakter ‘#’ muncul di output? 26. Perhatikan kode program di bawah ini “cek” adalah sebuah array dengan indeks mulai dari 1 s/d 1000 yang setiap elemennya bernilai true atau false. Pada awal program semua elemen array “cek” diberi nilai “false”. for i:=1 to n do begin j:=i; repeat cek[j]:=not cek[j]; j:=j+i; until j>n; end; for i:=1 to n do if cek[i] then write(i,'*'); Jika n berharga 100, maka output yang akan dihasilkan adalah ..... 27. Diberikan sebuah fungsi dalam Pseudopascal berikut:
Untuk soal nomor 28 sampai dengan 30: Perhatikan potongan kode program dalam pseudopascal berikut ini: function R(n: integer; x: integer; y: integer; z: integer) : integer; begin if (n = 0) R := 1; else R := S(x - 1, y, z) + S(x, y - 1, z) + S(x, y, z - 1) + n; end; function S(x: integer; y: integer; z: integer) : integer; begin S := R(min(x,y,z), x, y, z); // min adalah fungsi menentukan // nilai minimum dari ketiga // parameternya end; 28. Berapakah nilai yang dikembalikan R(1, 2, 2, 2)? 29. Jika R(1, 1, 1, z) mengembalikan nilai 1000, berapakah z? 30. Misalkan tipe data integer dapat menyimpan bilangan bulat sebesar atau sekecil apapun. Berapakah nilai maksimum m sehingga memanggil R(m, m - 1, m - 2, m - 3) membuat fungsi R tidak pernah selesai dieksekusi? Untuk soal 31 sampai dengan 32: // isi dari array a[0..9] {2,1,6,8,9,7,5,3,4,0}; for i := 0 to n do begin for j := 0 to 9 do
Halaman 4 dari 6
adalah
Sesi 1
OSN IX 38. Setiap dung adalah ding. Ada lima ding yang juga dong. Tidak ada dung yang dong. Jika banyaknya ding adalah 15 dan tiga diantaranya tidak dung dan tidak dong, maka banyaknya dung adalah...
begin if a[i] < a[j] then begin temp := a[i]; a[i] := a[j]; a[j] := temp; end; end; end; 31. Jika n = 0, berapakah nilai yang dicetak perintah writeln(a[4]) setelah menjalankan algoritma ini? 32. Berapakah nilai minimum n sehingga setelah menjalankan algoritma ini a[9] = 9 ? 33. Jika 4! berarti 4.3.2.1 = 24, maka digit terakhir dari 1! + 2! + 3! +...+1999! adalah.... 34. Suatu bilangan x terdiri dari dua angka. Jika bilangan itu ditambah 45, akan diperoleh bilangan yang terdiri dari dua angka itu juga dalam urutan terbalik. Jika di antara angka puluhan dan angka satuan disisipkan angka nol, maka diperoleh bilangan yang nilainya 7
2 kali 3
bilangan x. Bilangan x tersebut adalah.... 35. Pada dasar sebuah tong terdapat 3 buah keran. Dari keadaan penuh, dengan membuka keran pertama dan kedua saja, tong tersebut dapat dikosongkan dalam waktu 70 menit; jika yang dibuka keran pertama dan ketiga saja, tong tersebut kosong dalam waktu 84 menit; jika yang dibuka keran kedua dan ketiga saja, tong itu kosong dalam waktu 140 menit. Jika ketiga keran itu dibuka bersama, tong dapat dikosongkan dalam waktu....menit.
39. Matematikawan August DeMorgan hidup pada tahun 1800-an. Pada tahun terakhir dalam masa hidupnya dia menyatakan bahwa : “Dulu aku berusia x tahun pada tahun x2 ”. Pada tahun berapakah ia dilahirkan... 40. Wati menuliskan suatu bilangan yang terdiri dari angka 6 angka (6 digit) di papan tulis, tetapi kemudian Iwan menghapus 2 buah angka 1 yang terdapat pada bilangan tersebut sehingga bilangan yang terbaca menjadi 2002. Berapa banyak bilangan dengan enam digit yang dapat dituliskan Wati agar hal seperti diatas dapat terjadi? 41. Jika x dan y bilangan bulat yang memenuhi
y 2 3x 2 y 2 30 x 2 517 , maka 3x 2 y 2 .... 42. Bilangan palindrom adalah bilangan yang sama jika dibaca dari kiri ke kanan atau sebaliknya. Sebagai contoh 35353 adalah bilangan palindrom, sedangkan 14242 bukan palindrom. Tentukan banyaknya bilangan bulat positif terdiri dari 5-angka bersifat palindrom yang habis dibagi 3. 43. Cari bilangan bulat positif terkecil n sehingga memberikan sisa berturut-turut 1, 2, 3, 4 dan 5 jika dibagi 2, 3, 4, 5, dan 6. 44. Tentukan bilangan yang terdiri dari 4 digit ABCD yang memenuhi 4 ABCD DCBA .
36. Jika x 2 xy 15 dan xy y 2 10 , x 0 maka nilai x sama dengan 37. Suatu kunci kombinasi terdiri dari lima angka. Ada berapa banyak cara membentuk kombinasi yang memuat paling sedikit satu angka 7?
45. Pada sebuah klub olahraga diketahui bahwa 10 orang menyukai tenis, 15 orang menyukai tenis meja, 12 orang menyukai bulutangkis, 5 orang menyukai tenis dan tenis meja, 4 orang menyukai tenis dan bulutangkis, 3 orang menyukai tenis meja dan bulutangkis dan 2 orang menyukai ketiga olahraga tersebut.
Halaman 5 dari 6
Sesi 1 Berapa banyak anggota klub yang menyukai sedikitnya satu dari ketiga cabang olahraga ini? 46. Untuk menentukan usulan peraturan yang dapat disetujui oleh publik diadakan survey terhadap sejumlah responden. Peraturan yang diusulkan terdiri atas usulan I, II dan III. Setelah dihitung, 78% responden menyatakan dapat menyetujui sekurang-kurangnya satu usulan diantara usulan I, II, dan III. 50% responden menyetujui usulan I, 30% responden menyetujui usulan II dan 20% responden menyetujui usulan III. Jika 5% dari responden menyetujui ketiga usulan tersebut, maka persentase responden yang menyetujui lebih dari satu usulan diantara ketiga usulan tersebut adalah ....%. 47. Suatu susunan 10-angka 0,1,2,3,4,5,6,7,8,9 dikatakan susunan cantik jika memenuhi tiga aturan sebagai berikut: a. Jika yang dibaca dari dari kiri ke kanan hanya angka 0, 1, 2, 3, 4 membentuk barisan naik b. Jika yang dibaca dari kiri ke kanan hanya angka 5, 6, 7, 8, 9 membentuk barisan turun, dan c. Angka 0 bukan pada posisi pertama. Sebagai contoh, 9807123654 adalah susunan cantik. Berapa banyak-kah susunan cantik tersebut.
OSN IX Para pemuda dan pemudi ini sedang dalam pencarian pasangannya masing-masing. 48. Misalkan ada aturan bahwa seorang pemuda yang ingin berpasangan dengan seorang pemudi harus memiliki usia minimal sama dengan usia sang pemudi. Ada berapa kemungkinan empat pasang pemuda-pemudi yang mungkin yang dapat dibentuk dari data di atas? 49. Misalkan ada aturan bahwa seorang pemuda yang ingin berpasangan dengan seorang pemudi harus memiliki usia minimal sama dengan usia sang pemudi. Ada berapa cara M1, M3, dan M4 memilih pasangan masing-masing sehingga membuat M2 tidak mempunyai pilihan yang mungkin? 50. Misalkan tidak ada batasan usia, tetapi ada aturan bahwa jika seorang pemuda Mx ingin berpasangan dengan seorang pemudi Fy, Mx harus menyukai Fy di urutan ke-1, 2, atau 3, dan Fy harus menyukai Mx di urutan ke-1, 2, atau 3. Ada berapa kemungkinan empat pasang pemuda-pemudi yang mungkin yang dapat dibentuk dari data di atas?
Untuk soal 48 sampai dengan 50: Ada 4 orang pemuda bernama M1, M2, M3, M4 dan 4 orang pemudi bernama F1, F2, F3, F4. Setiap pemuda/pemudi memiliki daftar pemudi/pemuda yang disukai, diurutkan dari yang paling disukai sampai ke yang kurang disukai. Nama Usia Urutan yang disukai M1 24 F3, F2, F1, F4 M2 23 F1, F3, F2, F4 M3 28 F2, F4, F1, F3 M4 26 F3, F1, F2, F4 F1 F2 F3 F4
22 26 24 21
M1, M3, M2, M4 M2, M3, M4, M1 M3, M1, M2, M4 M1, M4, M3, M2 Halaman 6 dari 6
Bundel Soal Sesi 1 Bidang Informatika Olimpiade Sains Nasional X Manado - Sulawesi Utara - 13 September 2011
Anda dilarang membuka dan membaca isi bundel soal ini sebelum dipersilakan oleh juri. Bundel soal ini berisi 36 (tiga puluh enam) soal yang terdiri dari 8 (delapan) paket (tiap paket tidak memiliki keterkaitan dengan paket lain) dari halaman 1 sampai dengan halaman 12.
Bundel Soal Sesi 1
OSN X
Bidang Informatika
Ikan Dek Makrit Dek Makrit adalah keponakan dari Pak Dengklek. Karena melihat hobi Pak Dengklek yang memelihara bebek, bulan September 2011 tahun ini Dek Makrit mulai memelihara ikan dengan membeli 26 ekor ikan yang berwarna biru, merah, atau hijau. Ikan Dek Makrit memiliki keunikan, yaitu hanya bertambah tiba-tiba menjadi dua kali lipat pada salah satu hari tahun kabisat. Selain itu, tepat di setiap awal tahun, 10% ikan yang dimiliki olehnya akan mati. Sebagai catatan, tahun kabisat adalah tahun berbilangan kelipatan 4. Pengecualian diberikan kepada tahun berbilangan kelipatan 100, mereka harus habis dibagi 400 baru disebut tahun kabisat. Jadi, 2000 dan 2004 adalah tahun kabisat sedangkan 2100 bukan. Banyaknya hari di tahun kabisat ada 366, bukan 365. Gunakan pembulatan ke bawah jika diperlukan dalam perhitungan. 1. Berapakah banyak ikan Dek Makrit pada akhir tahun 2017? Jawab: ... 2. Pada tahun 2015 Dek Makrit berencana ingin menjual ikannya. Saat itu rasio warna ikannya 25% biru, 40% merah, dan sisanya hijau. Dek Makrit kemudian mengambil 50% dari keseluruhan ikan saat itu secara acak untuk dijual. Berapa banyaknya kombinasi ikan yang dijual agar ikan berwarna biru jumlahnya paling sedikit dibandingkan dengan ikan yang berwarna merah atau berwarna hijau? Jawab: ... 3. Setelah mencari informasi lebih lanjut mengenai pertambahan populasi ikannya di mesin pencari Google, Dek Makrit kemudian mengetahui bahwa ikannya akan bertambah pada hari yang kemunculannya paling banyak dibanding hari lainnya di tahun kabisat. Berapakah peluang ikan akan berkembang biak pada hari Selasa? Jawab: ... 4. Dek Makrit memelihara ikannya dalam sebuah akuarium. Pada akuarium tersebut ternyata muncul bakteri yang berkembang biak dengan menghasilkan sebuah tunas setiap satu jam. Tunas tersebut kemudian tumbuh menjadi bakteri dewasa dalam waktu satu jam juga, menghasilkan tunas satu jam kemudian, dan begitu seterusnya siklus tersebut berulang. Jika pada awalnya terdapat sebuah tunas bakteri dan tidak ada bakteri yang mati selama siklus perkembang-biakan, berapa banyak tunas bakteri yang ada setelah 15 jam? Jawab: ... 5. Agar ikannya tetap sehat, Dek Makrit membuat rencana untuk membersihkan akuarium jika jumlah bakteri yang ada sudah lebih dari atau sama dengan 10000 bakteri. Tapi sekeras apapun usaha Dek Makrit untuk membersihkan akuarium, tetap akan selalu tersisa 1 tunas
Halaman 1
Bundel Soal Sesi 1
OSN X
Bidang Informatika
bakteri setelah akuarium dibersihkan. Setiap berapa jam-kah Dek Makrit harus membersihkan akuarium? Jawab: ...
Halaman 2
Bundel Soal Sesi 1
OSN X
Bidang Informatika
Kantong Makanan Ternyata ikan Dek Makrit sangat kreatif dan pandai bermain pada saat lapar. Oleh karena itu Dek Marit memberi hadiah berupa makanan berbentuk butiran saat ikannya bermain dan diberikan dalam kantong. Permainan ini akan dimainkan oleh beberapa ikan dengan membentuk lingkaran. Permainan dimulai dengan memberikan kantong makanan yang terdiri dari N makanan kepada ikan pertama. Ikan pertama kemudian dapat mengambil 1, 2, atau 3 butir makanan dari kantong makanan, kemudian menyerahkannya ke teman di tepat sebelahnya searah jarum jam. Hal ini berlangsung terus untuk ikan yang selanjutnya hingga makanan dalam kantong makanan habis. Agar permainan ini lebih seru, Dek Makrit membuat aturan bahwa ikan yang mengambil makanan terakhir dari kantong makanan, harus keluar dari lingkaran, mengambil sebuah kantong makanan baru, menyerahkan ke kelompok ikan sisanya dan tidak bermain lagi. Kelompok yang baru akan memulai permainan yang sama dengan kantong makanan yang baru. Ikan yang tepat berada di sebelah kanan ikan yang keluar menjadi pemegang kantong makanan pertama untuk putaran selanjutnya. Ikan terakhir yang berhasil bertahan akan mendapat hadiah spesial dari Dek Makrit. Ternyata ikan yang berani bermain hanya ada tiga ekor. Ketiga ikan ini tentu ingin berjuang sebaikbaiknya agar mereka mendapatkan hadiah spesial. Karena mereka telah bermain berkali-kali, mereka semua telah menemukan cara untuk dapat bermain optimal. Apabila mereka memiliki kesempatan untuk mengeluarkan teman setelahnya, maka mereka akan mengambil kesempatan itu. Dek Makrit kemudian membuat aturan tambahan bahwa yang tidak mungkin menang pada satu permainan, hanya boleh mengambil satu buah makanan. Dek Makrit jago matematika, jadi dia tahu kalau ikannya curang. Ikan diberi nomor 1 hingga 3 searah jarum jam, dan ikan nomor 1 akan menerima menerima kantong makanan pertama kali. 6. Jika saat awal permainan jumlah makanan adalah 3 dan pada putaran kedua jumlah makanan adalah 5, maka ikan manakah yang akan menang? A. B. C. D. E.
1 2 3 Tidak dapat dipastikan Tidak ada jawaban yang benar
Halaman 3
Bundel Soal Sesi 1
OSN X
Bidang Informatika
7. Apabila pada saat awal permainan jumlah makanan adalah 6 dan pada putaran kedua jumlah makanan adalah 6, maka ikan manakah yang akan menang? A. B. C. D. E.
1 2 3 Tidak dapat dipastikan Tidak ada jawaban yang benar
8. Manakah kombinasi jumlah makanan di bawah yang dapat membuat ikan nomor 3 menang? A. B. C. D. E.
5,4 6,5 6,7 Tidak dapat dipastikan Tidak ada jawaban yang benar
9. Apabila jumlah makanan di kantong pertama adalah 5925 dan jumlah makanan di kantong kedua adalah 4381, maka ikan nomor berapa yang akan menang? A. B. C. D. E.
1 2 3 Tidak dapat dipastikan Tidak ada jawaban yang benar
Halaman 4
Bundel Soal Sesi 1
OSN X
Bidang Informatika
Menghias Akuarium Dek Makrit ingin menghias akuariumnya dengan batu yang beragam ukuran (tidak ada dua batu dengan ukuran yang sama) yang diatur dengan susunan tertentu. Pada baris terdepan, hanya boleh ada satu batu di tengah-tengah. Menurutnya, akuariumnya akan semakin indah jika setiap batu memiliki satu atau dua batu yang disusun di posisi kiri belakang atau kanan belakang, Gambaran batu dan akuarium tampak atas dalam dua dimensi adalah sebagai berikut : depan
kiri
kanan
bawah
Sebuah rancangan susunan batu dapat dinyatakan dalam pola A, B atau C. Misal, pada contoh gambar satu, rancangan dapat dinyatakan dalam ketiga pola sebagai berikut : Jenis Pola
Pola
A
12,5,2,9,18,15,13,17,19
B
2,5,9,12,13,15,17,18,19
C
2,9,5,13,17,15,19,18,12
*cara menulis susunan batu dengan pola A, B, atau C ini penting anda pahami untuk menjawab soal
Pak Dengklek kemudian memberi tantangan kepada Dek Makrit agar menyusun sesuai kriteria tertentu, sehingga apabila Dek Makrit berhasil menyusun sesuai kriteria tersebut, Pak Dengklek akan memberi hadiah lain untuk akuarium Dek Makrit. Berikut adalah kriteria yang diberikan oleh Pak Dengklek:
Sebuah batu akan berada di kiri belakang batu lain, jika dan hanya jika ukurannya lebih kecil daripada ukuran batu yang didepannya. Dan sebuah batu akan berada di kanan belakang jika ukurannya lebih besar
Halaman 5
Bundel Soal Sesi 1
OSN X
Bidang Informatika
Jika menambahkan batu ke susunan yang telah ada, harus menyusuri dari barisan depan, dan menyesuaikan dengan kriteria pertama. Pada gambar berikut adalah proses penambahan batu berukuran 13 ke susunan yang sudah ada.
mbar 1,
Ga
Untuk mengeluarkan batu dari susunan yang telah ada, berlaku aturan berikut: o
Keluarkan langsung batu tersebut jika tidak memliki batu lain di belakangnya (a)
o
Jika hanya ada 1 batu tepat di belakang batu yang akan dikeluarkan, keluarkan batu tersebut. Batu-batu dibelakangnya dimajukan ke satu barisan didepannya. (b)
o
Jika ada dua batu yang berada dibelakang batu yang akan diambil. Ambil batu yang berada di susunan bagian kanan belakang paling kiri dan tidak punya batu di kiri belakangnya sebagai pengganti batu yang diambil. Batu lain yang berada di belakang batu pengganti dimajukan ke satu barisan didepannya. (c)
(a)
(b)
Halaman 6
Bundel Soal Sesi 1
OSN X
Bidang Informatika
(c)
10. Dek Makrit mengambil 10 batu sembarang yang berturut-turut memiliki ukuran 8, 4, 3, 5, 9, 17, 14, 1, 2, 10. Bagaimanakah susunan batu yang terbentuk agar Dek Makrit mendapat hadiah dari pak Dengklek jika dinyatakan dengan pola A? Jawab: ..., ..., ..., ... 11. Dek Makrit kemudian mengeluarkan batu satu per satu secara berturut-turut yang berukuran 17, 9 dan 3. Bagaimanakah susunan batu sekarang jika dinyatakan dengan pola C? Jawab: ..., ..., ..., ... 12. Dek Makrit kemudian menambahkan batu berukuran 15, 6, 11, dan 7. Ternyata Dek Makrit menemukan sebuah batu yang posisinya jauh paling belakang. Sebutkan urutan batu jika disusuri dari paling depan hingga ke batu paling belakang tersebut (dipisahkan oleh koma). Jawab: ..., ..., ..., ... 13. Dek Makrit kemudian menyadari bahwa susunan ini dapat menjadi susunan yang sangat jelek, yaitu saat seluruh batu membentuk susunan yang berupa garis lurus. Berikan salah satu contoh pengambilan batu yang membentuk susunan yang sangat jelek dengan batu yang berukuran 1 hingga 5 (dipisahkan oleh koma). Jawab: ..., ..., ..., ...
Halaman 7
Bundel Soal Sesi 1
OSN X
Bidang Informatika
Hash Table Dek Makrit sedang belajar mengenai Hash Table. Hash Table adalah sebuah struktur data yang dapat melakukan operasi insert (peletakan data) dan search (pencarian data) dengan sangat cepat. Hash Table diimplementasi dengan tabel, namun berbeda dengan menggunakan tabel saja, dengan hash table Dek Makrit tidak harus menelusuri seluruh tabel untuk mencari sebuah bilangan. Dek Makrit mengimplementasi hash table dengan cara sebagai berikut: -
Dek Makrit membuat sebuah tabel yang memiliki K buah elemen, yang diberi indeks 0 sampai dengan K – 1.
-
Dek Makrit kemudian membuat sebuah fungsi hash f(x) = y, yang memetakan nilai x ke y. Nilai y haruslah berada dalam range 0 sampai dengan K – 1, inklusif.
-
Setiap kali Dek Makrit meng-insert data x, Dek Makrit akan menghitung f(x), lalu memasukkan x ke dalam tabel pada indeks ke-f(x).
-
Setiap kali Dek Makrit mau mencari apakah data x ada atau tidak di dalam hash table, ia akan menghitung f(x), lalu melihat apakah indeks ke-f(x) berisi data yang ingin dicarinya.
Misalnya Dek Makrit ingin membuat hash table untuk menyimpan integer. Ia memilih K = 6 dan fungsi hash f(x) = x mod 6. Pada mulanya semua elemen tabel masih kosong. Setelah Dek Makrit meng-insert 14, 33, dan 60, isi tabel menjadi seperti berikut.
Gambar 2
Dek Makrit melihat bahwa mudah sekali terjadi konflik. Misalnya, jika ia meng-insert 42, f(42) = 0, sehingga jika ia meletakkan 42 di posisi 0, 60 akan terhapus. Agar satu indeks dapat menyimpan lebih dari satu nilai, ia menambahkan sebuah daftar di setiap indeks elemen agar dapat menyimpan
Halaman 8
Bundel Soal Sesi 1
OSN X
Bidang Informatika
lebih dari satu nilai. Misalnya, setelah peletakan 42, tabel menjadi seperti gambar 3 (ke kanan adalah daftar yang ditambahkan pada indeks sebuah elemen) dan panjang daftar di indeks 0 adalah 2. Catatan: urutan angka yang dimasukkan dalam daftar tidak menjadi masalah.
Gambar 3.
14. Misalkan setelah itu, Dek Makrit memasukkan angka-angka 70, 80, 90, …, 600. Setelah selesai, berapakah banyak nilai pada daftar dari indeks ke-2? Jawab: ... 15. Tetap pada kondisi yang sama, berapakah banyaknya nilai tersimpan pada daftar indeks ke1? Jawab: ... Menurut Dek Makrit, menyimpan terlalu banyak angka di dalam hash table yang kecil adalah ide yang buruk, karena semakin panjang daftar yang ada, semakin lambat pula operasi pencarian. Dek Makrit mendapat saran dari seorang pakar untuk memilih K yang cukup besar agar panjang daftar per indeks tidak lebih dari satu atau dua. 16. Dek Makrit kemudian mengosongkan hash tablenya, dan sekarang ia memilih K = 600 dan f(x) = x mod 600. Lalu ia memasukkan angka-angka 10, 20, 30, dst, yang selalu lebih besar 10 dari bilangan sebelumnya. Ada berapa bilangan yang harus dimasukkan agar panjang daftar di indeks ke-470 mencapai 3? Jawab: ... 17. Ternyata memilih f(x) = x mod 600 untuk tabel berukuran K = 600 bukan ide yang bagus, karena seperti contoh di atas, panjang daftar di indeks yang berbeda-beda sangat tidak merata untuk masukan 10, 20, 30, …. Dek Makrit kemudian mengubah fungsi hash-nya menjadi f(x) = (x mod 601) mod 600 dan ia kemudian mengosongkan hash table dan mulai memasukkan 10, 20, 30, dst.
Ada berapa bilangan yang harus dimasukkan sehingga
panjang daftar di indeks ke-470 mencapai 3? Jawab: ... 18. Pada saat tersebut, berapakah selisih antara panjang daftar yang terpanjang dan panjang daftar yang terpendek? Jawab: ...
Halaman 9
Bundel Soal Sesi 1
OSN X
Bidang Informatika
19. Misalkan Dek Makrit tidak lagi menyimpan angka di hash table, tetapi menyimpan string. Ia mencoba untuk K = 5 dan f(x) = banyaknya karakter ‘a’ di dalam string tersebut, mod 5. Ada berapa banyak kemungkinan string yang terdiri atas tujuh huruf yang tersusun atas karakter ‘a’-‘c’ yang akan dimasukkan ke indeks ke-0? Jawab: ... 20. Jika Dek Makrit mengubah f(x) = (banyaknya ‘a’ x banyaknya ‘b’ x banyaknya ‘c’), mod 5, dari antara semua string tujuh huruf yang tersusun atas karakter ‘a’-‘c’, ada berapa banyak kemungkinan string yang akan dimasukkan ke indeks ke-0? Jawab: ...
Halaman 10
Bundel Soal Sesi 1
OSN X
Bidang Informatika
Prime Number Dek Makrit sedang belajar matematika dengan ikan-ikannya. Mereka sedang belajar tentang bilangan prima. Bilangan prima adalah bilangan yang hanya memiliki dua faktor pembagi, yaitu 1 dan bilangan itu sendiri. Salah satu teknik untuk menentukan bilangan prima dikenal dengan nama teknik Shieve of Eratos. Teknik ini menentukan bilangan prima dengan mendaftar semua bilangan antara 2 hingga N, kemudian menghilangkan bilangan-bilangan yang habis dibagi oleh bilangan prima berikutnya, yaitu bilangan yang tidak terhapus pada tahap sebelumnya. Dek Makrit mencoba metode ini pada daftar bilangan antara 2 hingga 100. 21. Sejauh ini Dek Makrit telah menghapus semua bilangan kelipatan 2, 3 dan 5. Berapakah bilangan yang masih tersisa pada daftar saat ini? Jawab: ... 22. Dek Makrit kemudian mencari bilangan prima terbesar antara 2 sampai 100. Bilangan yang ia temukan adalah ... 23. Karena ingin mengerjakan soal yang lebih menantang, Dek Makrit kemudian mencari bilangan terbesar yang memiliki faktor prima terbanyak. Bilangan yang dia temukan adalah? Jawab: ...
Halaman 11
Bundel Soal Sesi 1
OSN X
Bidang Informatika
Road Network Sebuah kota digambarkan dengan sebuah graph sebagai berikut
Kota digambarkan oleh lingkaran/simpul dan garis/jalur menggambarkan jalan dua arah menghubungkan dua kota beserta jaraknya.
yang
24. Berapakah banyak jalur yang dapat ditempuh dari kota A ke kota E tanpa melalui kota yang sama dua kali? Jawab: ... 25. Berapakah jarak terpendek yang dapat ditempuh dari kota A ke kota E? Jawab: ... 26. Jika panjang jarak antara dua kota juga melambangkan jumlah moda transportasi antara dua kota tersebut, berapakah jumlah kemungkinan kombinasi moda transportasi yang dapat digunakan dalam perjalanan dari A menuju E tanpa melalui kota yang sama dua kali? Jawab: ... 27. Pada perayaan 17 Agustus 2015, beberapa jalan akan dipilih untuk dibangun menjadi jaringan jalan tol sehingga setiap orang dapat berpergian dari dan ke kota manapun melalui jalan tol tersebut dan tepat hanya ada satu rute jalan tol yang menghubungkan antara dua kota. Berapakah total panjang jalan tol minimal yang dapat dibangun? Jawab: ... 28. Setelah jalan tol selesai dibangun pada tahun 2016, beberapa jalan baru kemudian dibangun untuk menghubungkan dua kota yang sebelumnya tidak saling terhubung langsung oleh sebuah jalan. Ternyata, jaringan jalan tol yang sebelumnya telah dibuat tetap yang paling minimal meskipun ada jalan baru yang terbentuk. Bila panjang jalan selalu bilangan bulat positif, berapakah total panjang jalan baru terkecil yang mungkin dibangun? Jawab: ...
Halaman 12
Bundel Soal Sesi 1
OSN X
Bidang Informatika
Memisahkan Ikan Dek Makrit baru selesai belajar logika. Pada pelajaran tersebut, dia mengenal operator logika AND dan OR. Operator tersebut membutuhkan dua operan, yang menghasilkan nilai benar atau salah. Ekspresi yang diberi tanda kurung akan dikerjakan lebih dahulu. Hasil operasi dengan kedua operator tersebut adalah sebagai berikut: P (operan)
Q (operan)
P AND Q
P OR Q
Benar
Benar
Benar
Benar
Benar
Salah
Salah
Benar
Salah
Benar
Salah
Benar
Salah
Salah
Salah
Salah
Kebetulan dia akan membersihkan akuarium tempat ikan-ikannya. Untuk itu dia perlu memindahkan ikan-ikannya ke tempat sementara. Sambil mengulang pelajaran, dia ingin membuat kalimat logika yang akan menentukan ikan yang mana akan masuk ke baskom yang mana (baskom 1 atau 2). Variabel yang digunakan: Variable
Pernyataan
X
Ikan dengan umur lebih dari 16 bulan
Y
Ikan dengan umur lebih dari 12 bulan
Z
Ikan yang diawasi orang tua
W
Ikan yang beratnya kurang dari 1 kg
H
Ikan yang hidup
Tentukan kalimat logika yang dibuat oleh Dek Makrit. : 29. Ikan berumur lebih dari 16 bulan atau ikan yang berumur lebih dari 12 bulan dan diawasi orang tuanya. Jawab: ... ... ...
Halaman 13
Bundel Soal Sesi 1
OSN X
Bidang Informatika
30. Kalimat di soal sebelumnya juga dapat dinyatakan sebagai berikut: (Ikan yang berumur lebih dari 16 bulan atau lebih dari 12 bulan), dan, (ikan yang berumur lebih dari 16 bulan atau diawasi orang tuanya). Jawab: ... ... ... Keesokan harinya, Dek Makrit melanjutkan belajar dan mengenal operator NOT yang membutuhkan satu operan dan memiliki hasil operasi sebagai berikut. P (operan)
NOT P
Benar
Salah
Salah
Benar
31. Ikan dengan berat kurang dari 1 kg dan mati atau ikan dengan berat lebih dari atau sama dengan 1 kg tetapi hidup. Jawab: ... ... ... 32. Seluruh ikan yang tersisa dari pernyataan pada soal nomor 29 s/d 31. Jawab: ... ... ...
Halaman 14
Bundel Soal Sesi 1
OSN X
Bidang Informatika
Kesukaan Ikan Ikan Dek Makrit saat ini berjumlah 120 ekor yang dinomorinya 1 sampai 120. Seluruh ikan dek Makrit yang bernomor genap suka makanan rasa bayam, ikan yang nomornya habis dibagi 5 suka makanan rasa pisang, dan ikan yang nomornya habis dibagi 7 suka makanan rasa kangkung. 33. Berapa banyak ikan yang menyukai rasa kangkung tapi tidak menyukai rasa bayam? Jawab: ... 34. Berapa banyak ikan yang yang tidak menyukai ketiga rasa? Jawab: ... Dek Makrit kemudian membeli 80 ekor ikan lagi, sehingga sekarang jumlahnya 200 ekor. Ternyata Nek Dengklek, ibunya Pak Dengklek, hobby mewarnai makanan ikan sehingga selain beragam rasa, makanan juga berwarna warni. Dengan makanan yang berwarna warni, ikan-ikan Dek Makrit semakin suka makan. Dari 200 ekor itu, 100 ekor menyukai makanan berwarna kuning, 70 ekor menyukai makanan berwarna biru, dan 140 menyukai makanan berwarna merah. 40 diantaranya menyukai makanan berwarna kuning dan juga menyukai yang berwarna biru, 30 menyukai makanan berwarna biru dan juga menyukai yang berwarna merah, dan 60 menyukai makanan berwarna kuning dan juga menyukai yang berwarna merah. Ada 10 ekor yang menyukai ketiganya. 35. Berapakah jumlah ikan yang tidak menyukai semua warna? Jawab: ... 36. Berapakah jumlah ikan yang hanya menyukai satu warna? Jawab: ...
Halaman 15