SOAL SIMULASI SELEKSI OLIMPIADE SAINS TINGKAT PROVINSI 2013 CALON TIM OLIMPIADE KOMPUTER INDONESIA 2014
Waktu: 150 menit
PROGRAMMING CLUB SMP/SMA SUTOMO 1 MEDAN TAHUN 2013
SIMULASI OLIMPIADE SAINS NASIONAL 2013 TINGKAT PROVINSI BIDANG INFORMATIKA/ KOMPUTER Peserta hanya dibolehkan membawa tanda pengenal, alat tulis dan penghapus saat memasuki ruang ujian. Bagian Informasi
Model ujian ini adalah isian singkat. Tuliskan jawaban anda sesingkat-singkatnya pada lembar jawaban di kolom nomor soal yang bersesuaian. Jika jawaban yang diminta merupakan ANGKA tuliskan dengan ANGKA TANPA SATUAN [Contoh: penulisan angka 5 dengan tulisan “lima” tidak diperkenankan.] Jawaban BENAR bernilai 1, jawaban SALAH bernilai 0. Jumlah Soal 50, untuk dikerjakan dalam 2½ JAM (atau 150 menit). Notasi algoritma pada bagian algoritmika menggunakan pseudopascal yang pada intinya seperti Pascal tetapi tidak serinci pascal karena diutamakan pada konsep logika di dalam algoritma. Halaman-halaman yang berisi pertanyaan ada di halaman no 2 sampai dengan 10. Jika berkas anda tidak lengkap/rusak/cacat/tak terbaca, mintalah kepada panitia untuk penggantian berkas. Peserta DILARANG: 1. menggunakan perangkat komputasi (laptop, kalkulator, komputer) 2. menggunakan alat komunikasi (handphone, pager, PDA, dll) selama mengerjakan ujian ini, 3. menggunakan buku/referensi/catatan selain berkas soal ini, serta 4. bekerja sama dengan atau mencontek hasil pekerjaan peserta lain. Peserta yang melakukan pelanggaran akan dibatalkan dari keiutsertaan ujian dan dinyatakan gugur. Berkas soal BOLEH digunakan untuk coretan tetapi TIDAK BOLEH dilepas dari bundelannya. Jika bundelan lepas secara tidak disengaja, pengawas diharapkan membundelnya kembali atau diganti dengan berkas baru. Berkas soal TIDAK BOLEH dibawa pulang dan panitia setempat harus menghancurkannya atau menyimpannya hingga seluruh propinsi di Indonesia selesai melaksanakan OSP ini. Penjelasan sejumlah notasi yang mungkin digunakan dalam naskah soal.
N! adalah bilangan faktorial N yang berharga hasil perkalian semua bilangan bulat mulai dari 1 sampai dengan N. Bilangan positif adalah bilangan yang tidak berharga negatif (nol termasuk bilangan positif). Notasi “A mod B”, dengan A dan B bilangan-bilangan bulat menghasilkan sisa pembagian A dengan B, misalnya 10 mod 3 = 1 karena 10 jika dibagi 3 akan menyisakan 1. Notasi “A div B”, dengan A dan B bilangan-bilangan bulat menghasilkan hasil pembagian A dengan B, dengan hanya mengambil bilangan bulatnya saja misalnya 10 div 3 = 3, karena 10 dibagi 3 berharga 3,333… dan bilangan bulatnya 3. Contoh lain, untuk 10 div 4, hasilnya adalah 2, karena mengambil bilangan bulat dari 2,5. Operasi boolean adalah operasi logika . Untuk membantu mengingatnya berikut ini table operasi-operasi yang muncul dalam naskah soal. A B not A A and B A or B FALSE FALSE TRUE FALSE FALSE FALSE TRUE TRUE FALSE TRUE TRUE FALSE FALSE FALSE TRUE TRUE TRUE FALSE TRUE TRUE Ekspresi Boolean adalah ekspresi yang dibentuk atas satu atau lebih operasi Boolean dari satu atau lebih variable Boolean.
INFORMASI LISENSI Hak cipta logo “Tut Wuri Handayani” dan logo “OSN Informatika” dipegang oleh Kementerian Pendidikan dan Kebudayaan Soal bersumber dari OSN Informatika Sesi 1 tahun 2010, 2009, 2008; Penyisihan PCS JOINTS UGM tahun 2011, 2010; Penyisihan BNPCHS 2010; Penyisihan ILPC Ubaya 2011
Bidang Informatika/ Komputer
Halaman 1 dari 9
Simulasi OSP 2013
1.
2.
3. 4. 5. 6.
7. 8.
Bagian Pertanyaan Analitika/ Logika (25 pertanyaan) 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? Dua buah bilangan bulat jika dijumlahkan hasilnya -20. Jika dikalikan hasilnya 91. Berapakah selisih kedua bilangan tersebut? Jika dan maka berapakah nilai x? Berapakah bilangan bulat positif terkecil n sehingga memberikan sisa berturut-turut 1, 2, 3, 4 dan 5 jika dibagi 2, 3, 4, 5, dan 6? Ada berapa banyak bilangan positif yang habis membagi 1.200.000? 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? Jika terdapat 10 pertanyaan yang masing‐masing dapat dijawab benar atau salah (B atau S), berapakah kemungkinan kombinasi jawaban yang dapat dibuat? 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)? 10
9. Berapakah 3 digit terkanan dari 11 ? 10. 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? 11. 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? 12. Di rumahmu ada kumpulan kumbang yang sangat aktif. Kamu telah mengamatinya beberapa kali dan menemukan beberapa fakta: o Setiap minggu jumlah kumbang menjadi dua kali lipat minggu sebelumnya; o Ketika kumbang-kumbang tersebut pertama kali datang ke rumahmu jumlahnya ganjil. Jika sekarang ada 544 kumbang di rumahmu, berapa minggu telah berlalu sejak kedatangan kumbangkumbang tersebut untuk pertama kali? Berikut merupakan deskripsi untuk soal 13—15 Setiap hari, saat aku bangun pagi, aku selalu melihat jamku lima menit lagi menunjukkan pukul enam tepat. Sepuluh menit kemudian, aku pergi ke kamar mandi untuk mandi, tetapi sedang dipakai temanku yang katanya sudah mulai mandi tepat pada saat aku bangun, dan dia sudah menggunakan 1/3 waktu total biasa dia mandi dihitung pada saat aku melihat kamar mandi. Aku kembali tertidur, lalu terbangun satu jam kemudian. Pada saat itu, aku menyadari bahwa yang menggunakan kamar mandi adalah temanku yang ketiga, dimana: - Kedua temanku berikutnya mulai mandi tepat saat temanku sebelumnya selesai mandi. - Temanku yang kedua biasa mandi dengan waktu total 5/6 total waktu biasa mandi temanku yang pertama. - Temanku yang ketiga biasa mandi dengan waktu total dua kali waktu biasa mandi temanku yang kedua. 13. Setelah teman ketigaku selesai mandi, seharusnya giliranku mandi. Tetapi aku bermalas-malasan selama 2/3 kali waktu teman pertamaku mandi dihitung pada saat teman ketigaku keluar dari kamar mandi. Pada pukul berapa aku mulai mandi? 14. Teman ketigaku sempat minta tolong untuk diambilkan handuknya karena dia lupa membawa handuk saat hendak mandi. Bila dia meminta tolong tepat pada saat dia selesai mandi, pukul berapakah saat itu? (Anggap waktu yang dibutuhkan untuk mengambil handuk = 0, karena gantungan handuk ada tepat di depan kamar mandi) 15. Suatu hari, teman keduaku terburu-buru, jadi dia mandi hanya 2/5 dari waktu biasanya dia mandi. Jika temanku yang lain mandi dengan waktu yang seperti biasa (tidak bertambah ataupun berkurang), kapan aku mulai mandi? (Anggap kali ini aku langsung mandi begitu teman ketigaku selesai mandi)
Bidang Informatika/ Komputer
Halaman 2 dari 9
Simulasi OSP 2013
Berikut merupakan deskripsi untuk soal 16—17 Ada n buah lampu dengan n buah saklar. Pada awalnya semua lampu dalam keadaan mati. Jika saklar pertama ditekan, maka akan mengubah keadaan semua lampu (mati jadi hidup dan hidup jadi mati). Jika saklar kedua ditekan, maka akan mengubah keadaan semua lampu kelipatan dua. Jika saklar ketiga ditekan, maka akan mengubah keadaan semua lampu kelipatan tiga; dan seterusnya. 16. Jika n = 10, maka berapakah jumlah lampu yang menyala setelah n saklar tersebut ditekan? 17. Berapakah jumlah n minimum agar setelah semua saklar ditekan jumlah lampu yang mati sebanyak 12? Berikut merupakan deskripsi untuk soal 18—19 Sebelum memulai hariku, aku biasanya sarapan di warung dekat tempat tinggalku. Di sana, ada beberapa menu makanan. Hari ini, aku pergi ke warung tersebut dan memesan satu menu makanan, dimana: - Aku tidak pernah makan makanan dengan harga yang paling murah. - Makanan yang kupesan harganya lima kali harga makanan yang paling murah. - Makanan yang paling mahal harganya 4/3 kali harga makanan yang kupesan. 18. Aku ingat pernah makan dengan menu paling mahal di warung tersebut. Saat membayar hanya makanannya saja, aku membayar Rp20.000,00 dan mendapat kembalian sebanyak enam kali harga makanan paling murah ditambah 1/10 harga makanan paling mahal tersebut. Maka, berapa harga makananku hari ini? 19. Suatu hari, saat sedang makan bersama seorang temanku, dia meminjam uangku untuk membayar makanannya karena dompetnya ketinggalan. Dia makan makanan paling murah di warung tersebut sebanyak dua porsi. Berapa jumlah uang yang harus kupinjami? (anggap aku memiliki pecahan uang yang pas untuk meminjamkan uang padanya) Berikut merupakan deskripsi untuk soal 20—23 Sebuah keluarga yang terdiri atas ayah, ibu, putra dan putri hendak menyeberangi sebuah jembatan gantung pada malam hari. 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. 20. Berapa menitkah waktu minimal yang dibutuhkan agar seluruh anggota keluarga tersebut dapat pindah ke sisi lain jembatan? 21. Berapa menitkah waktu tempuh orang/pasangan yang pertama kali menyeberang jika diinginkan agar waktu tempuh total seminimal mungkin? 22. Siapakah orang pertama yang kembali dari sisi lain jembatan untuk mengantar senter? Tuliskan jawaban dalam huruf balok seluruhnya dan dalam tepat satu kata. 23. 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? Berikut merupakan deskripsi untuk soal 24-25 Di sebuah desa antah berantah, terdapat 7 buah rumah yang terhubung satu sama lain baik secara langsung maupun tidak langsung melalui jalan‐jalan setapak. Angka yang tertulis di samping setiap ruas jalan adalah panjang jalan setapak tersebut (dalam kilometer). Diberikan peta desa berikut ini: 3
A 5
1 3
E
B
F
1
D 1
5
2
2
2 3
Bidang Informatika/ Komputer
C 4
G
24. Pak Dengklek sedang berada di rumahnya (A) dan ingin mengunjungi rumah Pak Ganesh (C) serta mengantarkan surat ke rumah Pak Teddy (di F). Berapa kilometerkah yang harus ditempuh Pak Dengklek? Anggap Pak Dengklek boleh mengantarkan surat ataupun mengunjungi Pak Ganesh terlebih dahulu. 25. Suatu hari kepala desa melakukan pengadaan pengaspalan jalan setapak yang menghubungkan rumah-rumah tersebut sehingga terdapat jalan aspal dari suatu rumah ke rumah lain (mungkin saja mengunjungi rumah lain terlebih dahulu). Biaya yang diperlukan adalah Rp1 juta per kilometer. Paling sedikit, berapa rupiahkah yang harus disediakan untuk membangun jalan aspal di desa tersebut?
Halaman 3 dari 9
Simulasi OSP 2013
Bagian Pertanyaan Algoritmika (25 pertanyaan) 26. 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 ‘#’
31. 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? 32. 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
muncul di output? 27. 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('*'); Jika n berharga 100, berapa banyak tanda bintang (*) yang di-output-kan?
sehingga setelah potongan kode program tersebut dieksekusi, k bernilai 200? 33. Perhatikan potongan kode program berikut ini function f(N: longint): longint; begin if N = 0 then write('A') else f(N div 2); end; Berapa kalikah huruf 'A' tercetak jika fungsi di atas dipanggil dengan f(17)?
Kode program berikut ini untuk soal nomor 28—29 function P(x, y: integer):integer; begin if (x = 0) then P := y else P := P(x-1, y+1); end; 28. Berapakah nilai dari P(2010, 2011)? 29. Berapakah nilai k dalam pemanggilan P(10, k) agar output yang dihasilkan berupa 42?
34. Perhatikan potongan kode program berikut ini function f(a, b: longint): longint; begin if b = 0 then f := a else if a < b then f := f(b, a) else f := f(b, a-b); end;
Apa hasil dari fungsi di atas jika dipanggila dengan f(123456, 765432)? 35. Perhatikan potongan kode program berikut ini.
30. Perhatikan potongan kode program berikut ini function f(N: longint): longint; begin if N = 0 then write('A') else begin write('A'); f(N div 2); write('A'); end; end;
Berapa kalikah huruf 'A' tercetak jika fungsi di atas dipanggil dengan f(37)?
Bidang Informatika/ Komputer
Halaman 4 dari 9
repeat if ((i mod 4) = 0) then i := i div 4 else if ((i mod 4) = 1) then i := i + 3 else if ((i mod 4) = 2) then i := i div 2 else i := i + 5; n := n + 1; until (i = 1); Jika nilai awal n adalah 0 dan nilai awal i adalah 686, berapakah nilai n pada akhir program?
Simulasi OSP 2013
Kode program berikut ini untuk soal nomor 36—42 type point = record x,y:longint; end; var r,c, x,y, xo,yo: longint; xg,yg, tx,ty, i: longint; a: array[1..100,1..100] of char; vis: array[1..100,1..100] of longint; q: array[0..10000] of point; dir: array[1..4] of point; head, tail: longint; begin readln(r,c); xo:=1; yo:=1; for y:=1 to r do begin for x:=1 to c do begin read(a[y,x]); if (a[y,x] = 'P') then begin xo := x; yo := y; end else if (a[y,x] = 'O') then begin xg := x; yg := y; end; vis[y,x] := 1000000007; end; readln; end; dir[1].x := 1; dir[1].y := 0; dir[2].x := -1; dir[2].y := 0; dir[3].x := 0; dir[3].y := 1; dir[4].x := 0; dir[4].y := -1; head := 0; tail := 0; q[head].x := xo; q[head].y := yo; vis[q[head].y, q[head].x] := 0; while (head <= tail) do begin x := q[head].x; y := q[head].y; for i:=1 to 4 do begin ty := y + dir[i].y; tx := x + dir[i].x; if ((ty > 0) and (ty <= r)) and ((tx > 0) and (tx <= c)) and (a[ty, tx] <> '#') //soal 41 and (vis[y, x]+ 1 < vis[ty, tx]) then begin vis[ty, tx] := vis[y,x] + 1; tail := tail+1; q[tail].x := tx; q[tail].y := ty; end; end; head := head+1; end; writeln(vis[yg, xg]); end.
Bidang Informatika/ Komputer
36. Apakah kompleksitas dari program di tersebut? Tuliskan dalam notasi O besar (big-O notation); dan dalam variabel R dan C. 37. Tuliskan singkatan nama algoritma yang dijalankan dalam satu kata saja! Testcase berikut ini untuk soal nomor 38—41 10 10 ......#... ..###....# .....##... ###..#..#. .#.#.#..#. #.#..##.#. ...#.#..#. .#...#..#. .########. .....O#.P.
38. Jika program di-input dengan testcase di atas, maka apakah output program tersebut? 39. Berapakah nilai maksimum di antara semua nilai yang disimpan di vis? 40. Berapakah nilai minimum di antara semua nilai yang disimpan di vis? 41. Jika baris yang bertanda “//soal 41” diganti dengan “and (a[ty, tx] <> '.')”, apakah output program tersebut? Testcase berikut ini untuk soal nomor 42 10 10 .#....#... ..###....# #....##... .##..#..#. .#.#...... .##.#.#.#. .#.##..#.# ..#.#...#. .#...#...# ...#.O#.P.
42. Jika program (tidak diubah di soal nomor 41) di-input dengan testcase di atas, maka apakah output program tersebut?
Halaman 5 dari 9
Simulasi OSP 2013
Potongan kode program berikut ini untuk soal nomor 43—44 function wah(x,y: integer): integer; begin if ((x = 0) and (y = 0)) then wah := 0 else if (x > y) then begin if (x > -y) then wah := wah(x - 1, y) + 1 else wah := wah(x, y + 1) + 1; end else begin if (x > -y) then wah := wah(x, y - 1) + 1 else wah := wah(x + 1, y) + 1; end; end;
43. Berapa hasil dari pemanggilan fungsi wah(3,3)? 44. Berapa banyak pasangan nilai x dan y yang menyebabkan pemanggilan wah(x,y) bernilai 3? Potongan kode program berikut ini untuk soal nomor 45—47 function lalala(n: longint): longint; var m: longint; begin m := 0; while n > 0 do begin m := m * 10 + n mod 10; n := n div 10; end; lalala := m; end;
45. Apakah nilai yang dikembalikan jika dipanggil lalala(100)? 46. Apakah nilai yang dikembalikan jika dipanggil lalala(-9889)? 47. Berapakan nilai n terkecil (n bilangan bulat 5 digit) sehingga pemanggilan lalala(n) menghasilkan nilai yang sama dengan n? Potongan kode program berikut ini untuk soal nomor 48—50 function lilili(x: longint): longint; var i, j: longint; begin j := 0; for i := 2 to x do while x mod i = 0 do begin j := j + 1; x := x div i; end; lilili := j; end;
48. Apakah nilai yang dikembalikan jika dipanggil lilili(12)? 49. Apakah nilai yang dikembalikan jika dipanggil lilili(360)? 50. Berapakan nilai k (k bilangan bulat nonnegatif) terkecil agar pemanggilan lilili(k) menghasilkan 0?
Bidang Informatika/ Komputer
Halaman 6 dari 9
Simulasi OSP 2013
Akhir dari berkas soal
Bidang Informatika/ Komputer
Halaman 7 dari 9
Simulasi OSP 2013
LEMBAR JAWABAN SIMULASI OLIMPIADE SAINS NASIONAL 2013 TINGKAT PROVINSI BIDANG INFORMATIKA/ KOMPUTER
NO PESERTA/ NAMA: ______________________________________________________________ SEKOLAH/ KELAS: _________________________________________________________________
NO
JAWABAN
NO
JAWABAN
NO
1
21
41
2
22
42
3
23
43
4
24
44
5
25
45
6
26
46
7
27
47
8
28
48
9
29
49
10
30
50
11
31
12
32
13
33
14
34
15
35
16
36
17
37
18
38
19
39
20
40
JAWABAN
TOTAL NILAI
Bidang Informatika/ Komputer
Halaman 8 dari 9
Simulasi OSP 2013
KUNCI JAWABAN SIMULASI OLIMPIADE SAINS NASIONAL 2013 TINGKAT PROVINSI BIDANG INFORMATIKA/ KOMPUTER
NO
JAWABAN
NO
JAWABAN
NO
JAWABAN
1
19999
21
2
41
5
2
6
22
AYAH
42
1000000007
3
3
23
5
43
6
4
59
24
4
44
12
5
96
25
10000000
45
1
6
48
26
15
46
0
7
1024
27
10
47
10001
8
759
28
4021
48
3
9
601
29
32
49
6
10
142857
30
13
50
0
11
1 atau 0
31
17
12
5
32
5
13
08.00
33
1
14
07.40
34
24
15
07.25
35
12
16
3
36
O(RC)
17
16
37
BFS
18
7500
38
41
19
3000
39
1000000007
20
12
40
0
Bidang Informatika/ Komputer
Halaman 9 dari 9
Simulasi OSP 2013
