materi pembinaan pra olimpiade sains · pdf filemampu membentuk model aritmatika/matematika...

MATERI PEMBINAAN

PRA OLIMPIADE SAINS NASIONAL VII BIDANG INFORMATIKA

8-14 AGUSTUS 2008 MAKASSAR, SULAWESI SELATAN

Selamat Belajar dan Berlatih, Jadilah Yang Terbaik!

1/110

DAFTAR ISI DAFTAR ISI ............................................................................................................................................1 PSEUDOPASCAL...................................................................................................................................5 A. Pengantar.................................................................................................................................5 B. Terminologi dan Penjelasan Umum.............................................................................5 C. Elemen‐elemen Algoritma dengan Pseudopascal ..................................................6 C.1. Variabel ...........................................................................................................................7 C.2. Perintah...........................................................................................................................9 C.3. Assignment & Ekspresi ......................................................................................... 10 C.4. Ekspresi Aritmatis................................................................................................... 10 C.5. Ekspresi Lojik ............................................................................................................ 11 C.6. Struktur kendali aliran .......................................................................................... 12 C.7. Algoritma Utama/Fungsi/prosedur ................................................................ 13

D. Aturan‐aturan Penulisan Struktur Kendali Aliran .............................................. 14 D.1. Struktur begin‐end.................................................................................................. 15 D.2. Strktur if‐then............................................................................................................ 15 D.3. if‐then‐else.................................................................................................................. 15 D.4. for‐do............................................................................................................................. 15 D.5. while‐do ....................................................................................................................... 16 D.6. repeat‐until................................................................................................................. 16 D.7. case‐of‐end ................................................................................................................. 16

E. Aturan‐aturan Penulisan Prosedur dan Fungsi.................................................... 17 E.1. Prosedur ...................................................................................................................... 17 E.2. Fungsi............................................................................................................................ 17

MATERI UJI OLIMPIADE SAINS BIDANG INFORMATIKA............................................... 18 A. Pengantar.............................................................................................................................. 18 1. Olimpiade Sains Nasional.......................................................................................... 18 2. International Olympiad in Informatics ............................................................... 18 3. Metoda dan Proses Seleksi di OSN........................................................................ 19 4. Metoda dan Proses Seleksi pra OSN..................................................................... 19 5. Klasifikasi Soal‐soal Nonprogramming............................................................... 19

B. Materi Uji Aritmatika ....................................................................................................... 20 1. Mampu Membentuk Model Aritmatika/Matematika serta melakukan deduksi/induksi Model........................................................................................................ 20 2. Memahami Sifat‐sifat Bilangan............................................................................... 20 3. Mengkaitkan dengan Konteks Masalah .............................................................. 21 4. Memahami Formula Rekursif.................................................................................. 21 5. Eksplorasi dalam Masalah Kombinatorik .......................................................... 21 6. Berpikir secara “Cerdas” ........................................................................................... 22

C. Materi Uji Analitika dan Logika................................................................................... 23 D. Materi Uji Algoritmika..................................................................................................... 25 E. Materi Uji Programming................................................................................................. 31 F. Penutup.................................................................................................................................. 33

DESKRIPSI RINGKAS SITUS TOKI LEARNING CENTER................................................... 34 Tujuan Bahan Ini ......................................................................................................................... 34 Batasan Aplikasi........................................................................................................................... 34

2/110

Halaman Utama............................................................................................................................ 34 Fasilitas Yang Tersedia ............................................................................................................. 35 Tanya Jawab .................................................................................................................................. 36 Memilih Soal Pilihan Berganda ............................................................................................. 37 Menjawab Soal Pilihan Ganda................................................................................................ 37 Lembar Jawab Pilihan Ganda ................................................................................................. 38 Pilihan Ganda ................................................................................................................................ 38 Menu Deskripsi Soal (Untuk mengakses soal) ............................................................... 39 Soal Problem Solving (dengan membuat program)..................................................... 39 Rekapitulasi Submisi ................................................................................................................. 40 Meminta Untuk Dinilai.............................................................................................................. 40 Forum Diskusi............................................................................................................................... 40 Ubah Password............................................................................................................................. 41 Logout .............................................................................................................................................. 41

CONTOH SOAL DAN PEMBAHASAN ........................................................................................ 42 Soal Aritmatika, Analitika dan Logika ................................................................................ 42 Soal Algoritmika........................................................................................................................... 60 Soal Pemrograman ..................................................................................................................... 67 Faktorial ..................................................................................................................................... 67 Ulang Tahun.............................................................................................................................. 70

MATERI PJJ PRA OSN 2008.......................................................................................................... 73 Readln dan Writeln..................................................................................................................... 73 Contoh Masukan ..................................................................................................................... 74 Contoh Keluaran ..................................................................................................................... 74

While Loop ..................................................................................................................................... 75 Contoh Masukan ..................................................................................................................... 75 Contoh Keluaran ..................................................................................................................... 75

While Loop + Counter................................................................................................................ 76 Contoh Masukan ..................................................................................................................... 77 Contoh Keluaran ..................................................................................................................... 77

Menjumlah per Kolom............................................................................................................... 78 Contoh Masukan ..................................................................................................................... 79 Contoh Keluaran ..................................................................................................................... 79

Menjumlah dalam Satu Baris ................................................................................................. 80 Contoh Masukan ..................................................................................................................... 81 Contoh Keluaran ..................................................................................................................... 81

If Then .............................................................................................................................................. 82 Contoh Masukan 1.................................................................................................................. 82 Contoh Keluaran 1 ................................................................................................................. 82 Contoh Masukan 2.................................................................................................................. 82 Contoh Keluaran 2 ................................................................................................................. 82 Contoh Masukan 3.................................................................................................................. 83 Contoh Keluaran 3 ................................................................................................................. 83

If Then, Multi Condition............................................................................................................ 84 Contoh Masukan 1.................................................................................................................. 84 Contoh Keluaran 1 ................................................................................................................. 85 Contoh Masukan 2.................................................................................................................. 85 Contoh Keluaran 2 ................................................................................................................. 85

If Then Else..................................................................................................................................... 86

3/110

Contoh Masukan 1.................................................................................................................. 87 Contoh Keluaran 1 ................................................................................................................. 87 Contoh Masukan 2.................................................................................................................. 87 Contoh Keluaran 2 ................................................................................................................. 87 Contoh Masukan 3.................................................................................................................. 87 Contoh Keluaran 3 ................................................................................................................. 87

Case ................................................................................................................................................... 88 Contoh Masukan 1.................................................................................................................. 89 Contoh Keluaran 1 ................................................................................................................. 89 Contoh Masukan 2.................................................................................................................. 89 Contoh Keluaran 2 ................................................................................................................. 89

Procedure ....................................................................................................................................... 90 Contoh Masukan ..................................................................................................................... 91 Contoh Keluaran ..................................................................................................................... 91

Function........................................................................................................................................... 92 Contoh Masukan 1.................................................................................................................. 94 Contoh Keluaran 1 ................................................................................................................. 94 Contoh Masukan 2.................................................................................................................. 94 Contoh Keluaran 2 ................................................................................................................. 94

Var Parameter............................................................................................................................... 95 Contoh Masukan ..................................................................................................................... 97 Contoh Keluaran ..................................................................................................................... 97

Break, Continue, Exit.................................................................................................................. 98 Contoh Masukan 1.................................................................................................................. 99 Contoh Keluaran 1 ................................................................................................................. 99 Contoh Masukan 2................................................................................................................100 Contoh Keluaran 2 ...............................................................................................................100

Operasi String .............................................................................................................................101 Contoh Masukan ...................................................................................................................102 Contoh Keluaran ...................................................................................................................102

Manhattan Distance .................................................................................................................105 Format Masukan...................................................................................................................105 Format Keluaran...................................................................................................................105 Contoh Masukan ...................................................................................................................105 Contoh Keluaran ...................................................................................................................105

Floor and Ceiling........................................................................................................................106 Format Masukan...................................................................................................................106 Format Keluaran...................................................................................................................106 Contoh Masukan ...................................................................................................................106 Contoh Keluaran ...................................................................................................................106

Dua Pangkat.................................................................................................................................107 Format Masukan...................................................................................................................107 Format Keluaran...................................................................................................................107 Contoh Masukan 1................................................................................................................107 Contoh Keluaran 1 ...............................................................................................................107 Contoh Masukan 2................................................................................................................107 Contoh Keluaran 2 ...............................................................................................................107

POLA 1............................................................................................................................................108 Format Masukan...................................................................................................................108

4/110

Format Keluaran...................................................................................................................108 Contoh Masukan ...................................................................................................................108 Contoh Keluaran ...................................................................................................................108

POLA 2............................................................................................................................................109 Format Masukan...................................................................................................................109 Format Keluaran...................................................................................................................109 Contoh Masukan 1................................................................................................................109 Contoh Keluaran 1 ...............................................................................................................109 Contoh Masukan 2................................................................................................................109 Contoh Keluaran 2 ...............................................................................................................109

POLA 3............................................................................................................................................110 Format Masukan...................................................................................................................110 Format Keluaran...................................................................................................................110 Contoh Masukan 1................................................................................................................110 Contoh Keluaran 1 ...............................................................................................................110 Contoh Masukan 2................................................................................................................110 Contoh Keluaran 2 ...............................................................................................................110 Contoh Masukan 3................................................................................................................110 Contoh Keluaran 3 ...............................................................................................................110

Pseudopascal Penulis: Suryana Setiawan, M.Sc. v. 060518

5/110

PSEUDOPASCAL Versi Olimpiade Sains Bidang Informatika/Komputer

A. Pengantar Mengingat dalam seleksi tertulis Olimpiade Informatika/Komputer algoritma‐algoritma yang terkait dalam soal‐soal tersebut dituliskan dengan Pseudocode Pascal, atau selanjutnya kita singkat dengan Pseudopascal saja, maka kami merasa perlu untuk mengeluarkan dokumen untuk dijadikan acuan peserta untuk memahaminya. Dokumen ini diharapkan juga menjadi acuan peserta dalam mempersiapkan diri dalam seleksi tersebut maupun para pembina dalam mengarahkan pelatihan siswa‐siswanya. Bagi pembimbing atau peserta seleksi yang cukup menguasai bahasa pemrograman Pascal, sebagian besar aturan penulisan Pseudopascal merupakan subset dari aturan Bahasa Pascal itu sendiri. Kecuali, ada beberapa hal yang di dalam Bahasa Pascal boleh dilakukan, dalam pseudopascal tidak ada atau tidak disarankan untuk dilakukan. Hal ini untuk memungkinkan kompatibilitas algoritma dengan bahasa lain seperti bahasa C sehingga peserta yang lebih menguasai bahasa selain Pascal dapat cukup mudah untuk memahaminya juga. Jadi berkenaan dengan ini anda tinggal menemukan hal‐hal yang menjadi “pantangan” tersebut. Mengingat dokumen ini dituliskan lebih untuk acuan maka anda hanya akan menemukan penulisan substansi yang seringkas‐ringkasnya tanpa disertai contoh‐contoh yang memadai. Dalam kesempatan lain, semoga kami dapat menyediakan materi yang lebih sesuai untuk digunakan langsung dalam pembinaan‐pembinaan peserta dalam pemrograman.

B. Terminologi dan Penjelasan Umum Untuk memudahkan anda dalam pemaham dokumen ini beberapa terminologi terkait akan dijelaskan. Jika agak berbeda dari yang anda sudah ketahui kami harapkan itu tidak terlalu dipermasalahkan karena hal tersebut bukan tujuan utama dari dokumen ini. Berikut ini mengenai algoritma

• Algoritma adalah urutan langkah‐langkah sistematis yang terkait pada pemecahan suatu masalah; didalamnya bisa terdapat sejumlah variabel, perintah, ekspresi & assignment, struktur kendali aliran (control flow) dari algoritma, serta definisi fungsi/prosedur.

• Pseudocode adalah suatu cara penulisan algoritma agar ide dan logika dari algoritma dapat disampaikan/diekspresikan.

• Pseudopascal (alias Pseudocode Pascal) adalah pseudocode yang menggunakan (mengadopsi) beberapa notasi Bahasa Pascal berikut struktur penulisan programnya.


6/110

Berikut ini mengenai program komputer • Program komputer atau kita singkat dengan kata program (istilah

lainnya code) adalah susunan perintah‐perintah dan operasi‐operasi yang mengimplementasikan algoritma tertentu disertai yang ditulis dalam bahasa pemrograman tertentu.

• Bahasa pemrograman adalah bahasa yang di dalamnya terdapat aturan penulisan program.

• Bahasa Pascal adalah salah satu bahasa pemrograman, dan saat ini terdapat sejumlah versi dari bahasa Pascal diantaranya: Ansi Pascal, Turbo Pascal, Free Pascal, dlsb.

Algoritma yang ditulis dalam suatu pseudocode dibedakan dari programnya yang ditulis dalam suatu bahasa pemrograman akibat adanya perbedaan tujuan dari kedua hal itu. Algoritma dengan pseudocode bertujuan untuk menyampaikan ide dari algoritma bagi pembaca (dalam hal ini peserta seleksi), sementara program dalam suatu bahasa pemrograman untuk dapat dijalankan nantinya oleh komputer. Mengingat komputer “bodoh” maka dalam penulisannya suatu program harus 100% taat pada aturan‐aturan penulisan programnya (istilahnya tidak ada kesalahan sintaks) sementara karena pembaca algoritma adalah manusia maka demi menyederhanakan dan memudahkan pemahaman maka aturan‐aturan penulisannya digunakan secara fleksibel. Terkadang pesudocode dituliskan nyaris sama dengan versi programnya sendiri tetapi kadang‐kadang diringkaskan menggunakan kalimat‐kalimat bahasa manusia (dalam hal seleksi ini adalah bahasa Indonesia) bahkan beberapa bagian sengaja yang bukan fokusnya dihilangkan. Prinsip dalam penulisan pseudocode adalah “tuliskan seringkas‐ringkasnya sejauh tidak mengurangi pengertian dari algoritma yang menjadi fokus pembahasan tersebut.” Dalam kaitannya dengan materi seleksi, pseudocode yang digunakan adalah pseudopascal berdasarkan kenyataan bahwa notasi‐notasi Bahasa Pascal jauh lebih mudah dipahami daripada notasi bahasa pemrograman populer lainnya saat ini terutama bagi pemula (misalnya bahasa C). Selain itu setiap notasi yang digunakan dijaga untuk selalu berpadanan dengan notasi yang ada dalam bahasa lain tersebut sehingga peserta yang lebih menguasai bahasa selain Pascal tetap dapat memahami ide dari algoritma terkait. Terakhir, untuk menghindari polemik akan cara‐cara penulisannya, sekali lagi Pseuodopascal yang dimaksud dalam dokumen ini adalah Pseudopascal versi Olimpiade Sains Bidang Informatika/Komputer & TOKI.

C. Elemen‐elemen Algoritma dengan Pseudopascal Seperti pada terminologi di atas terdapat sejumlah elemen dasar dalam pseudopascal.

• Variabel • Perintah • Assignment & Ekspresi • Struktur kendali aliran


7/110

• Fungsi/prosedur • Komentar

Sebelum penjelasan masing‐masing komponen itu (di bagian C.1 s.d. C.7) berikut ini suatu contoh algoritma dalam pseudopascal. Algoritma ini tidak berarti apa‐apa karena hanya ditulis untuk membantu di bagian penjelasan masing‐masing elemen algoritma tsb kemudian. function kubik(a: integer): integer; begin kubik := a*a*a; end; procedure sw(var a: real; var b: real); begin

menukarkan isi a dan b end; var status: array[0..99] of boolean; { array 1 dimensi } Tbl: array[0..99,0..1] of integer; { array 2 dimensi } sum: record x,y: real end; { struktur komposit } begin

Proses mengisikan data ke dalam matriks Tbl dan array status sum.x := 0; sum.y := 0; for I := 0 to 99 do begin t0 := (Tbl[I,0] + Tbl[I,1])/2 - I*2; status[I] := (Tbl[I,0] = Tb l[I,1]) or (sum.x <> sum.y); if (status[I] or status[99-I]) then begin sum.x := sum.x + kubik(Tbl[I,1] - t0); sum.y := sum.y + kubik(Tbl[I,0] - t0); sw(sum.x, sum.y); end; end;

Proses pencetakan hargaharga sum.x dan sum.y .... .... end.

C.1. Variabel Variabel adalah elemen dari algoritma untuk menyimpan suatu harga tertentu pada suatu saat dan pada saat lain harga dalam variable itu bisa diubah ke harga lain sesuai kebutuhan. Berikut ini aturan‐aturan untuk variabel.


8/110

• Suatu variabel dituliskan dengan suatu nama secara unik dan nama variabel dapat terbentuk dengan karakter alfanumeris1 (hanya huruf dan angka) kecuali karakter pertama adalah alfabet. Misalnya:

o Variabel‐variabel dalam contoh di atas bernama sum, Tbl, status, I dan t0.

• Huruf besar dan huruf kecil sama saja (case insensitive2) namun

penulisan variabel diharapkan selalu konsisten dalam penggunaan huruf besar/kecilnya.

• Suatu variabel tidak diberikan nama dengan kata yang akan digunakan

secara khusus dalam notasi penulisan algoritma (lihat daftar kata reserved word) dengan tujuan untuk menghindari kerancuan arti. Misalnya:

o kata‐kata function, begin, end, for, do, integer, real, var, array, dan boolean di contoh di atas memiliki arti khusus (reserved word),

• Variabel bisa berbentuk tunggal, komposit, atau bisa juga berbentuk

majemuk yang ditandai elemen‐elemennya dengan indeks.

• Variabel berbentuk majemuk atau yang dikenal dengan nama array, harga indeks‐indeks array berkisar dari 0 hingga bilangan positif tertentu3 dan penulisan indeksnya setelah nama variabel tersebut di dalam sepasang kurung siku. Nomor indeks dari array dapat digantikan oleh harga suatu variabel lain dengan menuliskan nama variabel tersebut. Misalnya:

o status[I] menunjukan elemen array status ke I dan harga I sendiri dalam algoritma dapat berubah‐ubah sehingga status[I] mengacu pada berbagai elemen.

• Array bisa berindeks lebih dari satu (disebut berdimensi lebih dari 1)

misalnya array dua dimensi dan di dalam tanda kurung siku ada dua harga indeks yang dipisahkan oleh tanda koma4 dengan alternatif sepasang kurung siku tutup & buka5 (“][“). Misalnya:

o status adalah array dengan indeks berkisar dari 0 s.d. 99. o Tbl adalah array dua dimensi (dengan 2 indeks) yang masing‐

masing indeks memiliki kisaran dari 0 s.d. 99 dan 0 s.d. 1. Penulisan elemen Tbl[i,0] dapat juga diganti dengan Tbl[i][0].

1 Dalam bahasa Pascal selain alfanumeris, sejumlah karakter lain dapat pula digunakan. Disini kita batasi saja hanya alfanumeris. 2 Dalam bahasa C nama variabel case sensitive sementara bahasa Pascal case insensitive 3 Indeks dibatasi demikian untuk menjaga portabilitas (kemudahan untuk diimplementasikan) dengan bahasa C walaupun dalam bahasa Pascal indeks ini bisa menggunakan banyak cara. 4 Mengikuti aturan dalam bahasa Pascal 5 Mengikuti atuaran dalam bahasa C


9/110

• Jika cukup jelas jenis dan penggunaanya maka suatu variabel tidak perlu dideklarasikan6. Jika dideklarasikan maka penulisan mengikuti aturan deklarasi variabel dalam bahasa Pascal yaitu dituliskan di awal program atau di awal fungsi/prosedur. Misalnya:

o Tbl, status dan sum dideklarasikan tetapi I dan t0 tidak.

• Struktur komposit (variabel yang di dalamnya terdiri atas subvariabel7) sedapat mungkin akan dihindari. Seandainya diperlukan maka akan mengikuti aturan penulisan Record dalam bahasa Pascal dan penggunaan komponennya menggunakan aturan dalam bahasa Pascal yaitu nama variabel dan nama subvariabel dituliskan dengan dipisahkan tanda titik.

o Misalnya variabel sum memiliki dua subvariabel yaitu x dan y. Masing0masing bisa dianggap sebagai variabel tersendiri dengan nama sum.x, dan sum.y.

C.2. Perintah Perintah adalah satuan operasional dari suatu algoritma maupun algoritma.

• Perbedaannya, perintah‐perintah dalam algoritma bisa dinyatakan dalam kalimat‐kalimat bahasa sehari‐hari sementara untuk program perintah‐perintah harus bisa “dipahami” dan dijalankan oleh komputer sehingga karena keterbatasan komputer harus mengikuti aturan‐aturan penulisan yang rinci. Misalnya:

o Algoritma contoh di atas berisikan perintah‐perintah yang menggunakan kalimat bahasa Indonesia biasa dan perintah‐perintah mengikuti aturan penulisan program bahasa Pascal.

• Perintah dalam bahasa sehari‐hari dibedakan dalam font penulisannya

dari perintah yang mirip perintah program. Misaalnya: o dalam algoritma contoh dituliskan dengan huruf miring sementara

perintah dengan aturan bahasa pemrograman dengan huruf biasa dan diakhiri tanda “;” (sebagai kebiasaan saja, keduanya menggunakan huruf courier untuk dibedakan dari bagian teks yang lain).

• Kadang‐kadang perintah dalam bahasa sehari‐hari digunakan untuk mewakili sejumlah baris perintah dalam bahasa pemrograman sehingga diharapkan penulisan algoritma tidak terlalu bertele‐tele namun tetap atau bahkan dapat lebih mudah untuk dipahami.

o Misalnya: “Proses mengisikan data ke dalam ….. (dst)” menggantikan sederetan operasi mengenai pengisian Tbl dan ”Proses pencetakan ….” yang menggantikan perintah‐perintah untuk mencetak harga variabel tsb.

6 Deklarasi variabel dilakukan dalam sebagian besar bahasa pemrograman untuk menyatakan jenis kemungkinan harga yang dapat diisikan padanya, ukuran/dimensi (khusus untuk array), dan scope (bagian‐bagian mana) dari program ia bisa digunakan. 7 Record dalam Pascal atau struct dalam bahasa C.


10/110

• Sederetan perintah yang tidak menjadi fokus untuk ditampilkan dalam algoritma kadang‐kadang diganti dengan sejumlah baris yang berisi titik‐titik (“.…”). Misalnya pada contoh di atas pada baris terakhir.

• Notasi‐notasi penulisan perintah mengikuti notasi yang digunakan dalam

bahasa Pascal yaitu ada yang bersifat assignment yang diikuti oleh suatu ekspresi atau hanya satu pemanggilan prosedur tertentu.

C.3. Assignment & Ekspresi Assignment adalah pemberian nilai pada suatu variable yang bisa berupa harga literal8, harga dari variable lain, atau harga yang dihasilkan dari suatu ekspresi. Sementara ekspresi adalah operasi yang akan menghasilkan harga untuk diberikan pada variabel tersebut yang bisa merupakan ekspresi aritmatis maupun atau ekspresi lojik (Lihat Dalam bahasa C, harus diikuti notasi “break;” karena tanpa itu maka alirannya jadi sangat berbeda. C.4 Ekspresi Aritmatis & C.5 Ekspresi Lojik di bagian berikutnya). Aturan dalam penulisan assignment adalah sebagai berikut.

• Aturan penulisannya adalah: nama variabel penerima diikuti tanda assignment “:=”9 selanjutnya nilai atau ekspresi yang menghasilkan nilai. Misalnya:

o “sum.x:=0” artinya variabel sum.x diberi nilai literal 0 o “t0:=(Tbl[I,0]+Tbl[I,1])/2–I*2;” artinya variabel t0 diberi

harga hasil ekspresi yang aritmatis di ruas kanan setelah tanda assignment.

C.4. Ekspresi Aritmatis Suatu ekspresi aritmatis berisikan sederetan operasi aritmatis dan jika yang jika dijalankan akan menghasilkan suatu bilangan (integer atau real). Suatu operasi aritmatis terjadi antara dua harga yang akan dioperasikan (disebut operand) dan sebuah operator kecuali untuk operasi unary yang hanya memerlukan satu operand.

• Notasi‐notasi operator arimatis: perkalian (*), pembagian (/), penambahan (+), pengurangan (‐), sisa pembagian (mod), pembagian dengan pembulatan ke bawah (div).

• Jika ekspresi berisi beberapa operasi maka operasi dengan orde tertinggi yang akan dilakukan terlebih dahulu.

• Urutan orde untuk operasi aritmatis mulai dari yang tertinggi hingga terendah adalah: perkalian/pembagian/modulo/divisi, kemudian penambahan/pengurangan (tanda / menyatakan berorde sama).

• Untuk yang berorde sama, urutan operasinya dilakukan dari kiri ke kanan dalam penulisan ekspresi namun jika berpotensi membingungkan kadangkadang urutan bisa dipertegas dengan bantuan tanda kurung dan

8 Harga literal adalah harga‐harga yang pasti misalnya integer 0, 100, ‐33; bilangan real 29.13, 21.41; string “Indonesia Raya”, “Olimpiade sains”. 9 Dalam bahasa C assignment hanya dengan tanda “=” tetapi dalam pascal tanda “=” digunakan pada pembandingan kesamaan harga; dalam pseudopascal ini dibahas di bagian C.4. Ekspresi.


11/110

penggunaan tanda kurung memungkinkan bagian operasi yang ada di dalam tanda kurung dilakukan terlebih dahulu. Misalnya:

o ”(Tbl[I,0]+Tbl[I,1])/2–I*2“ akan dilakukan penjumlahan Tbl[I,0] + Tbl[I,1] terlebih dahulu kemudian hasilnya akan dibagi 2 dan dikurangi oleh hasil perkalian antara I and 2.

• Operand‐operand bisa variabel, literal, atau hasil dari pemanggilan fungsi. Misalnya:

o dalam “sum.x+kubik(Tbl[I,1]–t0)” yang terlibat dalam operasi adalah sum.x, dan hasil dari pemanggilan fungsi kubik(Tbl[I,1]–t0) (Penjelasan pemanggilan fungsi ada di bagian fungsi).

• Operasi unary adalah operasi yang hanya berlaku sebagai operasi terkiri dalam ekspresi dengan operator minus (sama dengan pengurangan) dengan cara penulisan: operator mendahului operand. Efek dari operasi ini adalah memperhalikan harga operand di sampingnya itu dengan ‐1. Jika operand berharga positif akan menjadi negatif dan sebaliknya jika berharga negatif menjadi positif.

• Operasi tidak mengubah isi variabel‐variabel yang menjadi operand tersebut kecuali jika ia adalah variabel yang akan menerima hasil operasi tersebut di dalam operasi assignment hasil dari ekspresi (lihat bagian C.3 Assignment & Ekspresi sebelumnya).

C.5. Ekspresi Lojik Suatu ekspresi lojik bisa merupakan salah satu dari berikut ini: (1) satu harga literal lojik, (2) suatu variabel lojik, (3) suatu ekspresi pembandingan harga, (4) operasi lojik dari dua ekspresi lojik atau (5) negasi suatu ekspresi lojik. Keempat dan kelima memungkinkan ekspresi kombinasi yang kompleks.

• Ekspresi pembandingan terdiri atas dua antitas yang akan dibandingkan dan kriteria pembandingannya; penulisan berurutan entitas kiri kriteria pembandingan dan entitas kanan.

• Kriteria pembanding yang dikenali adalah “=” (sama10), “<” (lebih kecil), “>” (lebih besar), “<=” (lebih kecil atau sama dengan), “>=” (lebih besar atau sama dengan), “<>” (tidak sama11).

• Entitas yang akan dibandingkan bisa berupa variabel biasa atau ekspresi aritmatis (ekspresi aritmatis harus dituliskan di dalam tanda kurung!) atau suatu harga literal asalkan kedua entitas yang dibandingkan berjenis harga sama.

• Operasi lojik terjadi antara dua variabel lojik dan atau harga lojik (bisa dari hasil ekspresi pembandingan atau ekspresi lojik lain) dengan suatu operator kecuali jika operasi negasi dianggap sebagai operasi lojik maka ia hanya menggunakan satu operand.

• Operator‐operator lojik yang memerlukan dua operand adalah: and, or, dan xor sementara operator negasi adalah not.

10 Dalam bahasa C tanda pembandingan kesamaan ini dituliskan ganda (“==”) untuk membedakannya dengan assignment. 11 Dalam bahasa C tanda pembandingan ketidaksamaan ini dituliskan dengan “!=”.


12/110

• Operator‐operator tsb dijalankan dengan urutan sesuai dengan ordenya: dari yaang tertinggi ke yang terendah, jika sama dari kiri ke kanan dalam ekspresi.

• Urutan orde dari operator‐operator tersebut (dari tertinggi ke terendah): not, and, or/xor (tanda / menyatakan berorde sama).

• Seperti halnya dalam ekspresi aritmatis, tanda kurung dapat digunakan untuk mengatur urutan operasinya. Untuk menambah kejelasan algoritma kadang‐kadang tanda kurung disertakan.

• Hasil ekspresi bisa diassign ke suatu variabel boolean atau bisa juga digunakan dalam perintah kendali aliran (Dibahas di C.6 Struktur kendali aliran).

o Misalnya: dalam “status[I] := (Tbl[I,0] = Tb l[I,1]) or (sum.x <> sum.y)” di ruas kanan terdapat operasi lojik “or” antara dua hasil pembandingan. Pembadingan pertama adalah memeriksa kesamaan dan pembandingan kedua adalah memeriksa ketidaksamaan. Hasil ekspresi ini diberikan ke dalam variabel status[I] (pada posisi berindeks I dari array status).

C.6. Struktur kendali aliran Struktur kendali aliran adalah suatu bentuk/struktur yang memiliki peranan khusus untuk mengatur aliran urutan pengerjaan operasi atau beberapa operasi tertentu. Terdapat sejumlah bentuk kendali aliran (atau dikenal juga dengan istilah struktur) sebagai berikut (penjelasannya masing‐masing tedapat pada bagian D.1 s.d. D.7):

• beginend o struktur untuk menjadikan sejumlah perintah atau elemen lain

sebagai satu kesatuan • ifthen

o struktur untuk menjalankan perintah (atau perintah‐perintah jika disatukan dalam struktur beginend) setelah notasi “then” jika ekspresi yang diperiksa (antara notasi “if” dan notasi “then”) berharga boolean “true”.

• ifthenelse o struktur untuk menjalankan perintah (atau perintah‐perintah jika

disatukan dalam struktur beginend) setelah notasi “then” jika ekspresi yang diperiksa (antara notasi “if” dan notasi “then”) berharga boolean “true” dan sebaliknya jika “false” menjalankan perintah (atau perintahperintah jika disatukan dalam struktur beginend) setelah notasi “false”.

• fordo o pengulangan perintah (atau perintah‐perintah jika disatukan

dalam struktur beginend) setelah notasi “do” dengan jumlah pengulangan sejalan dengan perubahan harga iterator yang dinyatakan di antara notasi “for” dan notasi “do”.

• whiledo o pengulangan (iterasi) perintah (atau perintah‐perintah jika

disatukan dalam struktur beginend) setelah notasi “do” selama


13/110

ekspresi yang diperiksa (antara notasi “while” dan notasi “do”) berharga boolean “true”. Jika pertama kali diperiksa langsung berharga “false” maka iterasi sama sekali tidak dilakukan

• repeatuntil o pengulangan (interasi) perintah atau perintah‐perintah antara

notasi “repeat” dan notasi ”until” hingga ekspresi yang diperiksa (setelah notasi “until”) berharga boolean “true”. Jadi minimal satu kali dijalankan.

• caseofend o jika if‐then‐else adalah pencabangan aliran dengan dua cabang

maka struktur ini bisa memiliki pencabangan yang sangat banyak.

• Bentuk‐bentuk kendali tersebut bisa bersarang yaitu suatu bentuk di dalam bentuk yang lain.

o Misalnya: di dalam for I := 0 to 99 do ada beginend; di dalam begin‐end tsb ada ifthen dan kemudian di dalamnya ada lagi beginend dst.

• Untuk if‐then, if‐then‐else, while‐do, repeat‐until, kriteria pengendalian aliran adalah suatu ekspresi.

o Misalnya dalam “if (status[I] or status[99‐I]) then ...” sebagai ekspresi yang diperiksa adalah hasil operasi lojik antara status[I] dengan status[99‐I] dengan operator lojik “or”.12

C.7. Algoritma Utama/Fungsi/prosedur • Algoritma utama adalah badan utama dari algoritma sebagai analogi

program utama dalam program. Namun berbeda dengan program, algoritma bisa jadi hanya merupakan bagian tertentu dari suatu program bahkan bagian dari suatu fungsi/prosedur dari program tsb.

• Fungsi/prosedur adalah sederetan perintah/operasi seperti halnya algoritma itu sendiri yang dipisahkan dari algoritma utamanya guna menjadikannya sebagai subfokus dalam algoritma. Dalam suatu algoritma jika apa yang dikerjakan dalam fungsi/prosedur itu dapat dianggap jelas maka fungsi/prosedur tersebut tidak dituliskan atau digantikan dengan kalimat bahasa sehari‐hari.

• Pascal menyediakan sejumlah fungsi/prosedur yang siap pakai (tanpa pemrogram menuliskan lagi fungsi/prosedur itu), dalam Pseudopascal ini beberapa fungsi/prosedur Pascal tertentu yang sangat umum juga digunakan.

o Misalnya read (untuk membaca masukan), readln (membaca masukan termasuk karakter “end of line”), write (untuk mencetak keluaran), writeln (mencetak keluaran dan suatu “end of line”), eof (untuk memeriksan apakah masukan sudah mencapai “end of file”).

12 Dalam Pascal ekspresi tidak harus dibatasi tanda kurung sementara dalam C harus. Dalam contoh ini ekspresi tsb dibatasi dengan tanda kurung. Walaupun dalam Pseudopascal tidak diharuskan, untuk situasi tertentu disarankan adanya tanda kurun tsb untuk membantu memperjelas penulisan algoritma.


14/110

• Mengikuti definisi Pascal, fungsi dibedakan dari prosedur dari adanya harga yang dihasilkan oleh fungsi sebagai akibat dari pemanggilan/penggunaan fungsi tersebut.

• Suatu fungsi/prosedur bisa didefinisikan dengan sejumlah argumen (istilah lain: parameter). Pada saat pemanggilan fungsi/prosedur yang bersangkutan, argumen ini jika ada dituliskan di dalam tanda kurung setelah nama fungsi/prosedur itu.

• Ada dua jenis argumen: argumen bersifat “call by value” dan argumen “call by reference”. Untuk “call by value” dalam pemanggilannya yang dikirimkan ke fungsi/prosedur adalah harganya sementara “call by reference” yang dikirimkan adalah variabel itu sendiri. Perbedaan kedua argumen ini dinyatakan di daftar argumen di bagian definisi fungsi dengan mengawali nama variabel ybs dengan notasi “var”.

o Misalnya: fungsi kubik di atas memerlukan satu argumen ‘call by value” dan prosedur sw memerlukan dua argumen “call by reference”.

• Untuk “call by value” selain suatu harga literal, harga suatu variabel, bisa juga hasil dari suatu operasi aritmatis atau ekspresi lojik.

o Misalnya “kubik(Tbl[I,1] – t0)” memanggil fungsi kubik dengan argumen adalah harga yang dihasilkan dari operasi “Tbl[I,1] – t0”.

• Khususnya pada pemanggilan fungsi yang akan menghasilkan harga setelah pemanggilan itu dilaksanakan, harga hasilnya itu kemudian menggantikannya di dalam operasi/ekspresi yang bersangkutan.

o Misalnya: dalam “sum.x := sum.x + kubik(Tbl[I,1] – t0)” setelah pemanggilan “kubik(Tbl[I,1] – t0)”, harga yang dihasilkannya beserta harga dalam sum.x dijumlahkan dan hasilnya diassign kembali ke sum.x

• Untuk “call by reference” argumen di bagian yang melakukan pemanggilan hanya dapat berupa variabel saja dan ke variabel itu di bagian fungsi/prosedur jika mengalami perubahan isi (walau dengan nama variabel yang lain), saat kembali ke pemanggil perubahan itu tetap berlaku.

o Misalnya: dalam pemanggilan “sw(sum.x, sum.y)” variabel sw.x dan sw.y saat berada di prosedur sw dengan nama baru a dan b akan dipertukarkan, sehingga saat kembali isi sw.x dan sw.y sudah tertukar.

D. Aturan‐aturan Penulisan Struktur Kendali Aliran Secara umum aturan‐aturan penulisan struktur kendali aliran ini mengikuti aturan bahasa Pascal. Seperti hanya Pascal (dan bahasa‐bahasa lain, penulisan notas‐notasi, perintah‐perintah atau ekspresi‐ekspresi tidak harus dibaris tersendiri/tertentu; bisa saja beberapa elemen imi dituliskan bergabung dengan baris yang sama. Namun, demi kejelasan dalam pembacaan algoritma beberapa kebiasaan dilakukan (tapi tidak harus).


15/110

• Perintah yang ditulis dalam bahasa sehari‐hari dituliskan tidak dicampur dalam satu baris dengan elemen algoritma yang lain.

• Indentasi yang sama untuk blok struktur yang sama sangat disarankan..

D.1. Struktur begin‐end • Perintah‐perintah dalam satu deret yang menjadi satu kesatuan

struktural (satu blok) dituliskan di antara notasi begin dan notasi end. Perintah yang ditulis dalam notasi bahasa Pascal dituliskan dengan tanda separator “;” di akhir setiap perintah sementara perintah dalam bahasa sehari‐hari dituliskan tanpa tanda separator tsb.

• Jika terdapat struktur lain di antara satu beginend, maka struktur itu diperlakukan sebagaimana perintah yang ditulis dalam bahasa pascal (diakhiri separator “;”).

D.2. Strktur if‐then • Kondisi yang akan diperiksa dalam struktur ini adalah ekspresi lojik yang

diletakan di antara notasi if dan notasi then. Perintah (atau perintah‐perintah) yang akan dilakukan jika ekspresi lojik itu berharga boolean true diletakkan setelah notasi then.

• Jika lebih dari satu perintah maka perintah‐perintah itu dijadikan satu kesatuan struktur dengan tambahan notasi beginend yang mengapitnya.

D.3. if‐then‐else • Seperti pada ifthen, kondisi yang akan diperiksa dalam struktur ini

adalah ekspresi lojik yang diletakan di antara notasi if dan notasi then. Perintah (atau perintah‐perintah) yang akan dilakukan jika ekspresi lojik itu berharga boolean true diletakkan setelah notasi then dan perintah (atau perintah‐perintah) yang akan dijalankan jika berharga false diletakkan setelah notasi else.

• Baik untuk then maupun untuk else, jika lebih dari satu perintah maka masingmasing perintah‐perintah itu dijadikan kesatuan‐kesatuan struktur dengan tambahan notasi beginend yang mengapitnya (masing‐masing).

D.4. for‐do • Di antara notasi for dan notasi do ekspresi iteratif (ekspresi yang

menyatakan bagaimana iterasi itu harus terjadi) dituliskan. o Penulisan ekspresi iteratif berisi o nama variabel iterator (variabel integer yang harganya akan

berubah‐ubah sejalan dengan iterasi yang terjadi), o setelah tanda assignment dituliskan harga awal iterator (yang bisa

merupakan suatu harga literal atau ekspresi aritmatis), o notasi to atau downto yang menyatakan arah harga iterator

menaik atau menurun, harga terakhir interasi itu masih akan


16/110

dilakukan (yang bisa merupakan suatu harga literal atau suatu ekspresi aritmatis), dan

o jika kenaikan/penurunan bukan bilangan 1, harga perubahan yang terjadi pada iterator setiap satu iterasi dilalui dinyatakan dengan notasi step dan diikuti harga perubahannya (misalnya “step 2”).

• Setelah notasi do perintah (atau perintah‐perintah) yang akan dilakukan pada setiap kali iterasi dituliskan. Jika lebih dari satu perintah maka perintah‐perintah itu dijadikan satu kesatuan struktur dengan tambahan notasi beginend yang mengapitnya.

D.5. while‐do • Kondisi yang akan diperiksa adalah ekspresi lojik yang diltakan di antara

notasi while dan notasi do. Perintah (atau perintah‐perintah) yang akan dilakukan secara berulang‐ulang selama ekspresi lojik itu berharga boolean true diletakkan setelah notasi do.

• Jika lebih dari satu perintah maka perintah‐perintah itu dijadikan satu kesatuan struktur dengan tambahan notasi begin‐end yang mengapitnya.

D.6. repeat‐until • Kondisi yang akan diperiksa adalah ekspresi lojik yang diltakan setelah

notasi until. Perintah (atau perintah‐perintah) yang akan dilakukan dan kemudian diulang‐ulang selama ekspresi lojik itu berharga boolean false diletakkan antara notasi repeat dan notasi until.

D.7. case‐of‐end • Hal yang akan diperiksa adalah variabel atau ekspresi arinmatis yang

memiliki harga‐harga tertentu. Variabel atau ekspresi aritmatis itu diletakkan di antara notasi case dan notasi of.

• Di antara notasi of dan notasi end terdaftar sejumlah kemungkinan harga/kasus dan perintah (atau perintah‐perintah) yang akan dijalankan untuk kemungkinan harga tersebut.

• Satu harga literal13 yang mungkin14 diletakkan di sebelah kiri, diikuti notasi “:” (titik dua) lalu diikuti oleh perintah yang akan dijalankan selanjutnya sebuah “;” (titik koma)15.

• Jika ada beberapa perintah yang akan dijalankan maka perintah‐perintah itu dijadikan satu kesatuan struktur dengan tambahan notasi beginend yang mengapitnya.

13 Dalam Bahasa C, sebelum harga literal tsb, ada notasi “case” mendahuluinya. 14 Dalam Pascal harga yang mungkin ini bisa dinyatakan sebagai range harga yang mungkin misalnya bilangan‐bilangan antara 1 sampai dengan 10 dengan menulisnya sebagai “1..10” atau beberapa kemungkinan harga dengan dipisahkan koma misalnya “2, 5, 9”. Hal ini tidak ada di bahasa C sehingga dalam Pseudopascal ini hal itu dihindari. 15 Dalam bahasa C, harus diikuti notasi “break;” karena tanpa itu maka alirannya jadi sangat berbeda.


17/110

E. Aturan‐aturan Penulisan Prosedur dan Fungsi Secara umum aturan kerangka penulisannya mengikuti aturan dalam bahasa Pascal kecuali beberapa hal termasuk bahwa badan algoritma di dalam fungsi atau prosedur sesuai dengan pembahasan algoritma di atas (memungkinkan baris perintah dalam bahasa sehari‐hari, perintah‐perintah rinci yang bukan fokus diperlihatkan sebagai baris “….”. Seperti halnya nama variabel nama‐nama prosedur maupun function bersifat case insentitive namun demi untuk memberikan kejelasan dalam pembacaan, penamaan prosedur/function maupun variabel direkomendasikan untuk konsisten di setiap bagian algoritma. Dalam bahasa Pascal, suatu prosedur/function dapat memiliki prosedur/function lokalnya sendiri. Dalam pseudocode ini demi kompatibilitas dengan bahasa lain, hal itu ditiadakan.

E.1. Prosedur Mengawali suatu prosedur notasi procedure dituliskan dan diikuti nama prosedur. Jika ada argumen, mana argumen‐argumen didaftarkan di dalam tanda kurung dan setiap argumen tersebut dituliskan dengan dipisahkan dengan tanda koma (“,”). Dalam bahasa Pascal jenis variabel harus dispesifikasikan, namun dalam Pseudopascal ini seandainya cukup jelas maka demi mempersingkat, jenis variabel bisa dihilangkan. Untuk menunjukkan suatu argumen bersifat pass‐by‐reference maka di depan nama argumen itu dituliskan notasi var (seperti pada bahasa Pascal). Berikutnya jika ada variabel lokal yang perlu ditonjolkan didaftarkan (beserta jenis variabel tersebut) setelah notasi var. Badan algoritma prosedur dituliskan di antara begin dan end dan diikuti tanda “;” (titik koma).

E.2. Fungsi Mirip seperti pada prosedur kecuali tiga hal berikut ini. Pertama, yang mengawali fungsi adalah notasi function. Kedua, setelah nama (serta argumen‐argumennya yang dituliskan di dalam tanda kurung), suatu notasi “:” (titik dua) dan jenis harga yang akan dihasilkan fungsi dituliskan. Ketiga dalam badan algoritma nama fungsi digunakan seolah suatu variabel penerima assignment yang apabila algoritma dalam fungsi selesai dijalankan maka harga terakhir yang diberikan padanya adalah harga yang akan dikembalikan ke algoritma pemanggil fungsi ini. Jika nama fungsi berada sebagai operand dari suatu operasi maka yang terjadi adalah pemanggilan fungsi terhadap disinya sendiri yang dikenal dengan istilah rekursif.

Materi Uji Olimpiade Sains Bidang Informatika Penulis: Suryana Setiawan, M.Sc. v. 070619 alpha

18/110

MATERI UJI OLIMPIADE SAINS BIDANG INFORMATIKA Contoh‐contoh dan Pembahasan

A. Pengantar

1. Olimpiade Sains Nasional Dalam beberapa tahun terakhir Departemen Pendidikan Nasional telah meyelenggarakan Olimpiade Sains Nasional (OSN) yang di antaranya terdapat bidang Informatika. Pemilihan peserta yang akan bertanding di OSN dilakukan melalui seleksi bejenjang dan serentak di seluruh Indonesia, yaitu:

tingkat kabupaten/kota, kemudian tingkat provinsi.

Tahun 2006, untuk bidang informatika di tingkat provinsi tercatat diikuti 1480 siswa peserta seleksi sementara di tingkat kabupaten/kota tentunya sekian kali lebih banyak lagi (estimasi kasar ada di atas 8 ribuan siswa1). Hasil dari seleksi tingkat propinsi menentukan siapa yang akan menjadi salah seorang dari ke 90 siswa peserta OSN. Selain sebagai ajang prestasi tingkat nasional, OSN bertujuan juga untuk mendapatkan calon peserta pembinaan dan seleksi lebih lanjut hingga dipilih empat siswa terbaik alias anggota TOKI (Tim Olimpiade Komputer Indonesia). Mereka itulah yang akan mewakili negara dan bangsa untuk bertanding di tingkat dunia yaitu International Olympiad in Informatics (IOI).

2. International Olympiad in Informatics IOI sendiri adalah lomba yang menguji kemampuan peserta dalam problem solving dengan pemrograman komputer2. Setiap peserta dalam waktu yang amat terbatas harus mengerjakan sejumlah masalah yang diberikan, mulai dari memahami masalahnya, merancang solusinya, dan memindahkan solusinya dengan menuliskannya sebagai suatu program komputer. Pemecahan masalahnya harus komprehensif (meliputi berbagai kasus) yang harus diidentifikasi sendiri oleh setiap peserta, programnya harus efisien saat dijalankan (dalam waktu yang singkat untuk setiap kasus), dan tentunya menghasilkan keluaran yang sesuai dengan yang diharapkan. Kemampuan dalam coding (menulis program) hanyalah salah satu aspek saja, yang sulit adalah dalam melakukan problem solving itu sendiri termasuk memilih metodologi yang tepat. Pemilihan metodologi akan menentukan efisiensi dari program yang dibuat saat dijalankan.

1 Ini hanya dugaan saja karena di tingkat kabupaten/kota, penyelenggaraan beserta proses seleksi diserahkan ke masing‐masing kabupaten/kota yang bersangkutan sehingga data peserta tidak tercatat dengan lengkap. Sementara, di tingkat propinsi, proses seleksi di lakukan di pusat sehingga bisa diketahui jumlah keseluruhan peserta. 2 Harap bagian yang digarisbawahi tersebut dipahami secara lengkap; bukan HANYA menguji kemampuan membuat program komputer, bukan pula HANYA menguji kemampuan memecahkan masalah, tetapi KEDUANYA!!!


19/110

3. Metoda dan Proses Seleksi di OSN Proses seleksinya idealnya adalah mengacu ke IOI. Namun berbeda dengan bidang OSN lain seperti Fisika, Matematika, Kimia dan Biologi, bidang informatika khususnya pemrograman belum menjadi pelajaran resmi. Kalaupun ada, hanya di sekolah‐sekolah tertentu saja dan itupun belum tentu mengajarkan pemrograman. Oleh sebab itu, materi uji disesuaikan agar peserta potensial secara akademis/skolastik tinggi masih dapat terjaring untuk diberikan pembinaan yang intensif. Penyesuaiannya adalah mengurangi aspek yang sangat bergantung pada ketrampilan peserta dalam pemrograman dan sebagai gantinya, digunakan materi yang biasanya disebut sebagai materi uji “analisa dan logika”. Pada dasarnya materi ini menguji potensi akademis/skolastik peserta yang menjadi bagian terpenting dalam kemampuan problem solving peserta.

4. Metoda dan Proses Seleksi pra OSN Di tingkat kabupaten/kota serta propinsi komponen uji pemrograman tidak mungkin untuk diadakan mengingat sejumlah alasan tertentu sehingga uji pemrograman disubstitusi dengan materi uji kemampuan algoritmika.3 Selain itu, metoda pengujiannya pun tidak bisa dihindari bersifat test obyektif (pilihan ganda). Metoda ini memang banyak sekali kelemahannya yaitu memungkinkan jawaban asal tapi benar, namun, memungkinkan pemeriksaan yang segera. Dampak negatif tersebut bisa dikurangi dengan pembuatan soal dan pilihan jawaban yang dirancang dengan matang.

5. Klasifikasi Soal‐soal Nonprogramming Secara umum materi uji tertulis terbagi atas tiga komponen utama: materi uji analitika dan logika, materi uji aritmatika, dan materi uji algoritmika.

Materi analitika dan logika bertujuan untuk menguji potensi akademis (skolastik) peserta namun sedapat mungkin memiliki relevansi yang tinggi dengan problem solving dan elemen penting dalam menguasai pemrograman komputer. Kemampuan ini merupakan faktor penting dalam memahami persoalan yang diberikan dan merancang algoritma pemecahan masalahnya.

Materi arimatika sebenarnya sejalan dengan analitika dan logika di atas karena soal aritmatika disini bukan sekedar menguji ketrampilan dalam hitung‐menghitung, tetapi lebih pada cara berpikir yang logis dan analitis namun dengan soal bertemakan aritmatika

Materi algoritmika bertujuan untuk menguji kemampuan peserta dalam memahami dan menyusun suatu algoritma. Aspek‐aspek yang terkait dengan pengetahuan dan bahasa pemrograman direduksi seminimal mungkin ke tingkat pseudocode.

3 Uji pemrograman di tingkat provinsi, apalagi di tingkat kabupaten/kota, masih perlu beberapa tahun lagi hingga infrastruktur di setiap daerah sudah merata.


20/110

B. Materi Uji Aritmatika Sekali lagi, walaupun mengambil topik mengenai aritmatika, aspek terpenting dari materi ini bukan pada hitung menghitungnya tetapi pada uji kemampuan analitisnya. Aspek‐aspek analitis dalam persoalan aritmatika dijelaskan pada bagian berikut ini.

1. Mampu Membentuk Model Aritmatika/Matematika serta melakukan deduksi/induksi Model

Dalam problem solving, seringkali diperlukan tahapan pemodelan masalah yang sebagian menggunakan model matematika/aritmatika dan menyederhana‐kannya sehingga menjadi model yang lebih sederhana dan siap dikomputasikan dalam bentuk algoritma. Model yang tidak tepat berakibat pada kegagalan dalam pemecahan masalah. Contoh:

Uang Amir lebih banyak dari uang Ali. Jika dijumlahkan uang keduanya lebih dari 50 ribu rupiah, sementara selisih uang Amir dengan uang Ali lebih dari 30 ribu rupiah. Berapakah kemungkinan uang Amir yang paling tepat? Model permasalahan: Uang Amir = x, Uang Ali = y, dan dari deskripsi di atas

Pers‐I: x > y Pers‐II: x+y > 50000 Pers‐III: |x‐y| > 30000

Dari Pers‐I dan Pers‐III: menghasilkan Pers‐IV: x‐y > 30000 Dari Pers‐II dan Pers‐IV: jika dijumlahkan menghasilkan 2x>80000. Maka, x > 40000

2. Memahami Sifat‐sifat Bilangan Untuk sejumlah masalah, sifat‐sifat dari bilangan harus dipahami secara logis Contoh:

Jika n dan p adalah dua bilangan bulat, dan n + p berharga ganjil, manakah dari berikut ini bil ganjil? (A) n – p + 1 (B) np (C) n2 + p2 – 1 (D) 3p + 5n (E) (p – n)(n – p) A bukan, karena (n+p) adalah ganjil maka dari n dan p salah satu ganjil dan yang lain genap. Selisih antara n dan p pasti ganjil sehingga jika ditambah 1 menjadi genap. B bulan karena perkalian antara suatu bilangan genap dengan bilangan apapun akan menjadi genap. C bukan karena pangkat bulat positif berapapun dari bilangan genap, tetap genap, dan ganjil tetap ganjil, kemudian ganjil ditambah genap dan dikurang ganjil menjadi genap.


21/110

D bukan karena pangkat bulat positif berapapun dari bilangan ganjil tetap bilangan ganjil, dan jumlah dua bilangan ganjil menjadi genap. E benar, karena perkalian antara dua bilangan ganjil menghasilkan bilangan ganjil.

3. Mengkaitkan dengan Konteks Masalah Konteks dari soal perlu diperhatikan dan konteks tersebut kadang‐kadang hanya tersirat saja. Yang dimaksud dengan konteks di sini adalah pemahaman umum akan sesuatu yang sewajarnya diketahui pula. Contoh:

jika lonceng berdentang setiap 1 detik, dalam jumlah dentang yang sesuai waktu yang ditunjukkan, maka tepat pada pukul berapa dentang terakhir yang menunjukkan jam 6? Apakah pukul 6:00:06? Salah, seharusnya pukul 6:00:05 karena dentang‐dentang tsb pada pukul 6:00:00, pukul 6:00:01, pukul 6:00:02, pukul 6:00:03, pukul 6:00:04 dan pukul 6:00:05!! Konteks disini adalah dentang pertama terjadi pada tepat pukul 6, dan penomoran detik/menit dimulai dari 0, 1, ... dst.

4. Memahami Formula Rekursif Banyak masalah pemodelan dengan tingkat kesulitan yang tinggi atau pemrogramannya sendiri memerlukan pemecahan dengan algoritma rekursif. Pemahaman fungsi rekursif membantu dalam pemahaman memahami bagaimana bekerjanya algoritma rekursif. Contoh:

Jika didefinisikan f(n) = n f(n–1) untuk setiap n > 0 dan f(0) = 1, maka berapakah f(10)/(f (7) x f(6))? Pahami perilaku fungsi rekursif tsb, sbb, f(n) = n.f(n–1) = n.(n–1).f(n–2) = n.(n–1).(n–2).f(n–3) = ... = n(n–1)(n–2)(n–3)....2.1 = n! Sehingga, f(10) = 10! dan f(7) = 7! serta f(6) = 6!. 10!/7! = (10.9.8.7.6.5.4.3.2.1)/(7.6.5.4.3.2.1) = 10.9.8 Dan (10.9.8) /(6.5.4.3.2.1) = 1

5. Eksplorasi dalam Masalah Kombinatorik Dalam problem solving seringkali masalah yang diberikan bersifat kombinatorik (mendapatkan setiap kemungkinan kombinasi/permutasi jawaban). Untuk memecahkannya terkadang seluruh kemungkinan tersebut harus diperiksa untuk mendapatkan pemecahan yang umum. Contoh:

Jika diketahui dalam perkalian matriks A (mxn) dengan B (nxp) diperlukan biaya mnp. Sementara untuk perkalian tiga matriks A.B.C dengan A(mxn), B(nxp) dan C(pxq) ternyata terdapat dua kemungkinan biaya yang bergantung pada urutannya: ‐ Urutan (A.B).C (yaitu A dikali B dahulu kemudian dikali C), dan ‐ urutan A.(B.C) (yaitu B dikali C dahulu kemudian dikali A).


22/110

Urutan (A.B).C memerlukan harga mnp + mpq sementara urutan A.(B.C) memerlukan harga npq + mnq. Kedua harga bisa berbeda sesuai dengan harga‐harga m, n, p, q tsb. Pertanyaannya, untuk perkalian empat matriks A.B.C.D dengan A(10x4), B(4x15), C(15x2), dan D(2x20) manakah urutan dengan biaya minimum? Kemungkinan‐kemungkinan urutan adalah (diperoleh dengan permutasi ketiga tanda perkalian “.”): - urutan (((A.B).C).D), biaya 10x4x15+10x15x2+10x2x20 = 1300 - urutan ((A.B).(C.D)), biaya10x4x15+15x2x20+10x15x20 = 4200 - urutan ((A.(B.C)).D), biaya 4x15x2+10x5x2+10x2x20 = 600 - urutan (A.((B.C).D)), biaya 4x15x2+4x2x20+10x4x20 = 1080 - urutan ((A.B).(C.D)), biaya 15x2x20+10x4x15+10x15x20 = 4200 - urutan (A.(B.(C.D))), biaya 15x2x20 + 4x15x20+10x4x20 = 4200

6. Berpikir secara “Cerdas” Jika menghadapi suatu masalah komputasi yang kelihatannya tidak mungkin, pasti ada sesuatu di balik itu!! Dapatkanlah dengan bantuan pemahaman akan sifat‐sifat operasi aritmatika untuk mendapatkan model matematis yang lebih sederhana. Contoh 1:

Berapa digit terakhir dari 22003? Apakah anda ingin menghitungnya sendiri (secara manual)? Tentu tidak, pasti ada penyederhanaannya. Dengan mengubah n=1, 2, 3, …, dst, perhitungan 2n menghasilkan deret 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, dst. Amati angka terakhir dari setiap bilangan, kita mendapatkan perulangan dari 6 – 2 – 4 – 8 pada n mod 4 = 0, 1, 2, 3. Jadi jika n=2003, diperoleh 2003 mod 4 = 3, yaitu memiliki digit terakhir 8.

Contoh 2:

Ketiga digit awal dari hasil perkalian 22002 x 52005 jika dijumlahkan adalah? Ini juga tidak mungkin dihitung manual. Perhatikan bilangan dasarnya 2 dan 5 yang jika dikalikan menjadi 10. Karena setiap pasang faktor 2 dan 5 menghasilkan 10 berarti hanya menambah 0 di digit terkanan. Ada 2002 pasang faktor‐faktor tsb sehingga 22002 x 52005 = 53 x 102002= 125 102002. Penjumlahan tiga digit awal 1+2+5=8

Contoh 3:

Hitunglah (80! x 38!) /(77! x 40!). Menggunakan sifat sbb untuk a dan b bulat positif, a > b, maka a!/b! = a.(a – 1).(a – 2)…(b + 1). Maka (80! x 38!) /(77! x 40!) = (80!/77!) / (40!/38!) = (80x79x78) / (40x39) = (80/40) x (78/39) x 79 = 2 x 2 x 79 = 316 yang dapat dihitung tanpa kalkulator.


23/110

C. Materi Uji Analitika dan Logika Dalam pemodelan masalah pemrograman selain dengan model aritmatika, juga keterhubungan antara entitas/aspek dalam masalah perlu dipahami secara relational untuk mendapatkan model algoritmis yang lebih akurat. Kemampuan analitis tsb diperlukan dalam menghasilkan model keterhubungan/relasional tsb. Sayangnya tidak ada metodologi yang sistematik karena pada dasarnya sangat bergantung pada kreatifitas peserta uji. Namun, ada kesamaan umum dalam pemecahan masalahnya, yaitu

penggunaan model diagram sangat membantu untuk menggambarkan keterhubungannya secara menyeluruh berdasarkan keterhubungan yang fragmental (dari pernyataan‐pernyataan terpisah atau asumsi‐asumsi yang dibuat),

keterhubungan itu sendiri seringkali bersifat implisit sehingga perlu pemahaman yang hati‐hati dan perlu pemahaman akan gaya bahasa “penceritaannya”,

khususnya untuk asumsi yang dibuat segera dieliminasi jika kontradiksi dengan model diagram, dan

model diagram yang telah dibentuk perlu diverifikasi (dikaji ulang) dengan pernyatan‐pernyataan yang diberikan agar terjaga konsistensi, dan

Selalu berpikir adanya kemungkinan yang tertinggal atau tersamar yang belum dikaji ke dalam model

Contoh 1:

Terdapat 7 bilangan bulat A, B, C, D, E, F, dan G yang jika diurutkan membentuk deret bilangan cacah berurutan (misalnya 4,5,6,…) dengan pernyataan‐pernyataan berikut: (1) D berharga 3 kurangnya dari A (2) B adalah angka di tengah jika semua diurutkan (3) Kurangnya F dari B = kurangnya D dari C (4) G lebih besar dari F Jika diurutkan, urutannya adalah?

Untuk memudahkan urutan tsb misalnya [x1–x2–x3–x4–x5–x6–x7] Dari perny. (2) diketahui x4=B, maka menjadi [x1–x2–x3–B–x5–x6–x7] Dari perny. (3) F berada di ruas sebelah kiri B (bisa x1, x2 atau x2). Jika F=x1 maka

D adalah x2 dan C adalah x5 ([F–D–x3–B–C–x6–x7]), atau D adalah x3 dan C adalah x6 ([F–x2–D–B–x5–C–x7]).

Akan tetapi dari perny. (1) membatalkan kedua kemungk. asumsi ini karena A harus berada 3 posisi di kanan D yang sudah ditempati C. Jika F=x2 maka

D adalah x1 dan C adalah x3 ([D–F–C–B–x5–x6–x7]), atau D adalah x3 dan C adalah x5 ([x1–F–D–B–C–x6–x7]), atau D adalah x5 dan C adalah x7 ([x1–F–x3–B–D–x6–C]).


24/110

Akan tetapi dari perny. (1) hanya yang kedua yang mungkin karena yang pertama posisi A = posisi B atau yang ketiga posisi A berada di luar (setelah x7). Untuk sementara [x1–F–D–B–C–A–x7] dicatat sebagai salah satu solusi. Jika F=x3 maka

D adalah x1 dan C adalah x2 ([D–C–F–B–x5–x6–x7]), atau D adalah x5 dan C adalah x6 ([x1–x2–F–B–D–C–x7]), atau D adalah x6 dan C adalah x7 ([x1–x2–F–B–x5–D–C]).

tetapi dari (1) semua tidak mungkin (yang pertama posisi A = posisi B, kedua yang lain posisi A ada di luar). Jadi ternyata hanya tinggal satu kemungkinan yaitu [x1–F–D–B–C–A–x7]. Dari perny. (4) diperoleh G=x7, sehingga diperoleh juga E=x1. Hasilnya diketahui urutannya adalah E, F, D, B, C, A, G

Contoh 2:

Delegasi‐delegasi dari negara W dan negara R duduk berhadap‐hadapan pada meja perundingan. Masing‐masing delegasi terdiri atas seorang ketua, dua atase militer dan dua wakil kamar dagang negara masing‐masing. Delegasi W beranggotakan A, B, C, D, dan E. Delegasi R beranggotakan F, G, H, I, dan J. Masing‐masing delegasi berada pada sisi‐sisi memanjang berlainan (satu negara pada sisi yang sama dan ketua duduk di tengah delegasinya). Batasan dalam mengatur urutan duduk mereka: (1) Delegasi W menempatkan A dan B di kedua ujung barisannya. (2) Kuping kanan G tuli shg ia harus paling kanan dari delegasi R. (3) Baik D maupun F bukan ketua. (4) Para atase militer W, salah seorangnya B, didudukkan berdampingan, dan tidak ada satupun yang berseberangan dengan atase militer R (5) G bukan atase militer. (6) C wakil dari kamar dagang, duduk berseberangan dengan H. Manakah yang paling mungkin mengenai F berikut? (A) Wakil kamar dagang yang duduk di sebelah I (B) Wakil kamar dagang yang duduk di sebelah H (C) Wakil kamar dagang yang duduk berseberangan dengan B (D) Atase militer yang duduk di sebelah I (E) Atase militer yang duduk di sebelah J

Seperti pada contoh sebelumnya, dibuat diagram sbb x1–x2–x3–x4–x5 negara W y1–y2–y3–y4–y5 negara R Dari (1) kemungkinan {x1,x5} adalah {A,B} atau {B,A} Dari (2) maka y5=G yang karena pernyataan (4) dan (5) (G bukan a.m dan B adalah a.m) menyebabkan x5=B, sehingga (atase militer dengan bold) A –x2–x3–x4– B y1–y2–y3–y4–G Dari pernyataan (6) dan (4) diperoleh C = x2 dan y2 = H, sehingga


25/110

A –C –x3–x4– B y1–H –y3–y4–G Dari pernyataan (3) dan diagram di atas D = x4 dan F = y1 atau y4 A –C –E –D –B y1–H –y3–y4– G Jadi tinggal 2 kemungkinan F=y1 (atase militer), atau F=y4 (wakil kamar dagang). Jika atase militer maka (D) dan (E) salah karena sebelah y1 adalah H. Jika wakil kamar dagang maka (B) salah karena H atase militerdan (C) salah karena B ada di depan G. Jadi tinggal pilihan (A) yang paling mungkin. (Note: ini bukan satu‐satunya kemungkinan. Kemungkinan lainnya masih ada tapi tidak ada di kelima pilihan itu).

D. Materi Uji Algoritmika Sebagaimana dalam penjelasan awal, materi uji algoritmika adalah selain menguji kemampuan dalam memahami suatu algoritma yang diberikan, juga menguji kemampuan merancang suatu algoritma pemecahan masalah yang diberikan. Namun, untuk tingkat OSK/OSP pada saat ini belum memungkinkan untuk dilakukan terutama terkendala masalah teknis pemeriksaan kebenaran jawabannya. Kemampuan dalam perancangan tersebut baru akan diujikan kemudian di tingkat OSN. Karena pada tingkat OSK/OSN ini peserta harus dapat memahami algoritma yang diberikan maka hal yang penting untuk dikuasai adalah penulisan notasi algoritma yang digunakan oleh soal‐soal. Penulisan algoritma mungkin menggunakan suatu cerita (bahasa sehari‐hari) atau mengikuti notasi/tatacara yang didefinisikan sebagai pseudopascal4. Proses dari algoritma umumnya bersifat prosedural/imperatif saja5. Aspek‐aspek yang biasanya diujikan adalah:

1. penggunaan variabel (berarti sifat‐sifatnya juga) dalam kaitannya dengan proses algoritma tetapi tidak berkaitan dengan sifat variabel yang spesifik pada bahasa pemrograman tertentu6.

4 Lebih tepatnya, “TOKI Pseudopascal” dengan dokumen yang diposting di webite dengan URL di http://www.toki.or.id/toki2006/pseudopascal.pdf 5 Hingga IOI 2006 soal‐soal yang diujikan masih mementingkan efisiensi dalam problem solvingnya sehingga rancangan yang object‐oriented ataupun deklaratif belum perlu (atau malah tidak disarankan demi efisiensi solusi) untuk digunakan. Bahasa pemrograman yang populer di IOI adalah FreePascal, C dan C++. Khususnya C++ digunakan terutama untuk memudahkan sejumlah codingnya saja, bukan karena aspek object‐orientednya. 6 Dalam bahasa C terdapat kerumitan definisi mengenai array yang tidak terjadi dalam bahasa Pascal. Dalam bahasa Java character yang digunakan dalam String adalah unicode (16 bit) sementara dalam bahasa C atau Pascal adalah byte (8 bit). Dalam bahasa Pascal terdapat variabel tipe string standard pascal yang byte ke‐0 berisi panjang logical string di dalamnya sementara dalam C variabel String adalah array character dengan indeks dari 0. Dalam bahasa Pascal array bisa berindeks suatu range bilangan bulat apa saja termasuk bulat negatif, juga dapat menggunakan indeks non numerik.


26/110

2. aliran kendali proses7: blok beginend, pecabangan ifthen, pencabangan ifthenelse, pencabangan caseoption, loop whiledo, loop repeatuntil, dan loop for.

3. ekspresi lojik dengan operator lojik and, or, xor, not, 4. pemanggilan prosedur dan fungsi dan 5. aliran proses dari algoritma (prosedur atau fungsi) rekursif 6. struktur array (satu dimensi atau lebih)

Contohcontoh

1. Diberikan fungsi berikut

function apaini(a: integer; b: integer): integer; var x,y,r: integer; begin x := a; y := b; while (y <> 0) do begin r := x mod y; x := y; y := r; end; apaini := x; end; Pertanyaan: Jika fungsi tsb dipanggil dengan “writeln(apaini(414, 662));” berapakah yang dicetaknya? Pembahasan: Pemanggilan tsb akan dijalankan dengan variabel a mula‐mula berharga 414 dan b berharga 662. Kedua variabel dalam algoritma tidak mengalami perubahan apapun, jadi fungsinya hanya menyampaikan harganya ke variabel x dan y masing‐masing. Dalam fungsi tersebut terdapat struktur loop while‐do dengan variabel yang aktif (berubah‐ubah) dalam loop tersebut bernama x dan y. Terdapat variabel lain yaitu r yang berfungsi sebagai variabel pembandu operasi. Dalam struktur begin‐end di dalam loop while‐do tsb terjadi perubahan harga x diganti dengan y dan y diganti dengan harga r yang sebelum x dan y berubah r diisi x mod y. Jadi algoritma ini saling memodulokan dua bilangan. Dalam memahami loop while‐do, penting diperhatikan inisialisasi dan kondisi iterasi berakhir. Inisialisasinya adalah mengisi variabel x dengan 414 dan y dengan 662. Iterasi akan berakhir apabila y sebagai variabel yang akan memodulokan x berharga 0. Jadi urutannya:

414 mod 662 = 414 662 mod 414 = 248 414 mod 248 = 166 248 mod 166 = 82 166 mod 82 = 2 82 mod 2 = 0

Iterasi berhenti karena y berikutnya berharga 0. Terminasi algoritma mengembalikan harga x yaitu 2 kepemanggil fungsi. Terakhir, pemanggil fungsi melakukan pencetakan harga yang diperoleh dari pemanggilan tersebut yaitu 2. Jadi jawabnya adalah 2.

2. Diberikan fungsi berikut

7 Dalam edisi pseudopascal yad sedang dipertimbangkan struktur exception handling trycatch. Untuk edisi sekarang belum termasuk.


27/110

function apaitu(a: integer; b: integer): integer; begin count := count + 1; if (a > b) then apaitu := apaitu(b, a) else if (a = 0) then apaitu := b else apaitu := apaitu (b mod a, a) end;

Pertanyaan: Jika fungsi tsb dipanggil dengan “writeln(apaitu(1001, 1331));” berapakah yang dicetaknya? Pembahasan: Fungsi tersebut adalah fungsi rekursif dengan nama apaitu. Itu ditandai adanya pemanggilan fungsi bernama sama dengan dirinya. Di dalam fungsi ada struktur bersarang (nested structure) if‐then‐else membentuk 3 pencabangan. - Cabang pertama, jika harga dalam variabel a lebih besar dari b,

algoritma akan melakukan pemanggilan rekursif dengan penukaran posisi variabel a menjadi b dan b menjadi a.

- Cabang kedua, jika a berharga 0 maka akan dikembalikan harga b. - Cabang ketiga, tentu untuk a lebih kecil dari b, akan memanggil secara

rekursif dengan posisi harga a diberi harga (b mod a) dan posisi harga b diberi harga a.

Untuk semua cabang, tidak ada operasi lain sehingga hasilnya langsung dikembalikan ke pemanggil sebelumnya. Operasi pada variabel count tidak berarti apa‐apa berkenaan dengan pertanyaan ini. Pemanggilan apaitu(1001, 1331) akan membawa ke cabang ketiga lalu memanggi apaitu(330, 1001). Kemudian akan membawa ke cabang ketiga lagi lalu memanggil apaitu(11, 330). Kembali lagi ke cabang ketiga dan memanggil apaitu(0, 11). Pemanggilan terakhir ini akan memberikan harga variabel b menjadi harga yang dikembalikan dari fungsi tersebut, kemudian diteruskan ke pemanggilan sebelumnya, hingga ke pemanggilan pertama. Jadi jawabannya 11. Catatan: Jika anda dapat memahami algoritma‐algoritma pada kedua contoh di atas dengan baik, maka contoh ini dan contoh di atas menghasilkan harga fungsi yang tepat sama.

3. Diberikan fungsi berikut if (a and b) or ((not c) and d) then if ((a or not b) and c) or (b and (not a)) then writeln(1) else if (a or (d and b)) and (not b) then writeln(2) else writeln(4) else if not (d and c) and (not a) then writeln(5) else writeln(6);

Pertanyaan: Jika dijalankan dan ternyata mencetakkan harga 4 maka urutan harga‐harga a, b, c, d yang mungkin adalah? (A) TRUE, FALSE, TRUE, FALSE


28/110

(B) TRUE, TRUE, TRUE, FALSE (C) FALSE, FALSE, TRUE, TRUE (D) TRUE, TRUE, FALSE, FALSE (E) TRUE, FALSE, FALSE, TRUE

Pembahasan: Untuk soal ini pilihan harus diujikan pada setiap ekspresi boolean/lojik dalam algoritma di atas. Untuk memudahkan kita sebut E1, E2, E3 dan E4 untuk keempat ekspresi lojik di atas dimulai dari ekspresi paling atas. Pilihan (A): E1 berharga FALSE, lalu memeriksa E4 yang juga FALSE sehingga menjalankan writeln(6). Pilihan (B): E1 berharga TRUE, lalu memeriksa E2 dan juga TRUE, kemudian menjalankan writeln(1). Pilihan (C): E1 berharga FALSE, lalu memeriksa E4 yang berharga TRUE, kemudian menjalankan writeln(5). Pilihan (D): E1 berharga TRUE, lalu memeriksa E2 yang berharga FALSE, kemudian E3 berharga FALSE kemudian menjalankan writeln(4). Jadi untuk mencetak 4, maka pilihan D yang benar. Untuk cross‐check dan masih ada waktu dalam melakukannya, pilihan (E) bisa diperiksa: E1 berharga TRUE lalu memeriksa E2 yang berharga FALSE dan kemudian E3 TRUE sehingga menjalankan writeln(2). Catatan: untuk pemeriksaan ekspresi lojik, jika cukup berlatih maka pemeriksaan tersebut bisa dipercepat dengan hanya memeriksa sebagian dari ekspresi. Misalnya operator or hanya mensyaratkan salah satu dari kedua operand yang TRUE menyebabkan ekspresi tersebut TRUE, sebaliknya jika salah satu operand dari operator and berharga FALSE maka ekspresi tersebut menjadi FALSE.

4. Suatu robot berdasarkan harga a bilangan positif yang diberikan, akan menjalankan sederetan perintah berikut (algoritma dengan penulisan bahasa sehari‐hari):

begin

melangkah dengan jarak a ke depan, memutar arah ke kanan tegak lurus, melangkah sepanjang 2a, memutar ke arah kiri tegak lurus, melangkah sepanjang ½ a, memutar ke arah kiri tegak lurus, melangkah sepanjang 3½ a, memutar ke arah kiri tegak lurus, melangkah sepanjang a. memutar ke arah kanan tegak lurus.

end; Pertanyaan: ika posisi awal ada di (0, 0) dan robot sedang menghadap ke arah sumbu‐y positif, dengan a = 2 maka posisi akhir robot adalah ?


29/110

Pembahasan: Perhatikan diagram lintasan tsb. Ternyata, robot pada saat awal di (0,0) menghadap ke sumbu‐y, setelah menjalani lintasannya akan berada di (‐1.5a,0.5a) dan menghadap ke kiri (270o ) dari semula. Dengan a=2 maka akan berada di (‐3,1). Deretan langkah di atas digambarkan pada Gambar 1 ternyata efeknya sama saja dengan hanya melakukan langkah‐langkah seperti pada Gambar 2. Jadi selanjutnya, cukup memperhatikan kondisi awal dan kondisi akhir tersebut, kemudian putarkan ke kanan 90o.

Pertanyaan: Sekarang dengan pertanyaan baru: jika posisi awal ada di (0, 0) dan robot sedang menghadap ke arah sumbu‐x positif, dengan a = 4 maka dimanakah posisi akhirnya? Pembahasan: Dengan memutarkan Gambar 2 maka diperoleh posisi akhir di (0.5a, 1.5a) seperti terlihat pada Gambar 3. Dengan a = 4, posisi menjadi menjadi (2, 3) dan menghadap ke sumbu‐y positif.

(0,0)

(0,a)

(2a,a)

(2a,1.5a)(-1.5a,1.5a)

(-1.5a, 0.5a)

Gambar 1

(-1.5a, 0.5a)

(0,0)

Gambar 2


30/110

Pertanyaan: Kalau posisi awal bukan di (0,0) melainkan di (b, c) maka dimanakah posisi akhir tsb? Pembahasan: Sederhana saja seperti terlihat pada Gambar 4, tinggal geser posisi awal dari (0,0) ke (b, c), menjadi (b+0.5a, c+1.5a). Pertanyaan: Jika posisi awal ada di (0, 0) dan robot sedang menghadap ke arah sumbu‐x positif, deretan perintah tersebut dilakukan secara berulang sebanyak 2 kali (3 kali, 4 kali, dst) maka posisi akhir robot adalah?

Pembahasan: Jadi ingat untuk selalu memperhatikan posisi awal dan akhir saja seperti pada Gambar 2:

– Pertama: arah sumbu‐x positif, posisi (0,0) berhenti di (0.5a, 1.5a), dengan arah sumbu‐y positif

– Kedua: arah sumbu‐y positif, posisi (0.5, 1.5a) berhenti di …………, dengan arah ………………

– Ketiga: arah ………...., posisi …………… berhenti di …………, dengan arah ………………

Pertanyaan: Jika posisi awal ada di (0, 0) dan robot sedang menghadap ke arah sumbu‐x positif, deretan perintah tersebut dilakukan berulang sebanyak 3 kali dengan harga a pertama = 2 , harga a kedua = 4 dan harga a ketiga = 1. Dimanakan posisi akhir robot? Pertanyaan: Jika posisi akhir ada di (0,0) dengan robot sedang menghadap ke arah sumbu‐y positif setelah deretan perintah tersebut dilakukan berulang sebanyak 5 kali dengan a=4, berada di manakah robot itu sebelumnya? Pembahasan: Silakan mencoba menjawab kedua pertanyaan tersebut.

(0,0)

(0.5a, 1.5a)

Gambar 3

(b,c)

(b+0.5a, c+1.5a)

Gambar 4


31/110

E. Materi Uji Programming Pada tingkat OSN peserta akan diuji dalam materi pemrograman yang sebenarnya. Selain peserta harus menguasai pemrograman dengan bahasa yang digunakan yaitu FreePascal atau C atau C++, tetapi juga peserta harus mampu melakukan problem solving itu sendiri. Soal‐soal yang diberikan bukan berupa soal spesifikasi pemrograman yang eksplisit, namun permasalahan yang mana pemrograman hanya sebagai alat dalam pemecahan masalah itu sendiri. Kemampuan analitikal peserta diperlukan karena program yang nantinya dituliskan akan dijalankan dengan masukan yang sangat ekstrim sehingga dengan cara yang naif (tanpa analisis mendalam) program peserta tidak akan dapat berjalan dalam batas waktu yang diberikan. Aspek pertandingan lainnya adalah bahwa peserta harus mengerjakan soal ini dalam waktu yang terbatas pula! Permasalahan: buatlah program yang dapat menghitung berapa banyak 0 di belakang bilangan N! dengan harga N yang sangat besar sekali (misalnya 1030) ? Pembahasan: Jika anda menjawabnya dengan memperkalikan semua bilangan N.(N‐1).(N‐2)....2.1 dst maka anda hanya berhasil menjawab untuk N yang kecil (sebatas ukuran harga terbesar dari bilangan bulat yang disediakan serta batas waktu komputasi yang diberikan).

Jadi anda perlu melakukan analisis sbb. Karena banyaknya angka nol di belakang suatu angka bergantung pada berapa banyak kemunculan faktor 2 dan faktor 5 (mengapa? karena 2 kali 5 adalah 10). Dan khususnya, untuk suatu bilangan N! dapat dibuktikan banyaknya kemunculan faktor 5 tidak akan lebih banyak dari banyaknya kemunculan faktor 2. Maka, pertanyaan di atas dapat dijawab dengan hanya menghitung total banyaknya kemunculan faktor 5 dari bilangan‐bilangan pembentuk N! Bilangan yang berisi faktor 5 adalah bilangan‐bilangan kelipatan 5 saja jadi cukup kita memperhatikan bilangan‐bilangan kelipatan 5 ini.

Misalnya dalam 10! hanya ada dua bilangan yang memiliki faktor 5 yaitu 5 dan 10 sendiri sehingga. Contoh lain, dalam 29! ada 5, 10, 15, 20, 25 yang berisi faktor 5, dan karena pada 25 faktor 5 muncul dua kali menyebabkan 29! berisi kemunculan faktor 5 sebanyak 6 kali (jadi ada 6 nol di belakang 29!). Dengan mengiterasi i dari 5 ke N dengan kelipatan 5, dan mendapatkan berapa banyak faktor 5 dari bilangan i, lalu menjumlahkannya, maka anda dapat menjawabnya dengan baik untuk level OSN!

i := 5; count := 0; while i <= N do begin // menghitung berapa banyak kemunculan faktor 5 dalam i j := i; while (j mod 5) = 0 do begin j := j div 5; count := count + 1; end; i := i + 5; end;


32/110

Untuk tingkat OSN ini dengan cara demikian anda dapat memperoleh nilai penuh. NAMUN, untuk tingkat lebih lanjut mungkin harga N bisa diberikan jauh lebih besar misalnya N = 1012, algoritma harus beriterasi luar (while) sebanyak 2.1011 kali ‐‐ dan untuk setiap harga i akan diperlukan sekian kali lagi beriterasi untuk menghitung banyaknya faktor 5 dalam i yang akhirnya akan memerlukan waktu komputasi yang besar!. Apalagi jika waktu eksekusi lebih dibatasi jelas solusi tsb tidak akan memberikan nilai penuh. Untuk itu anda harus menggali ide lebih lanjut lagi sbb.

Perhatikan bahwa:

• bilangan‐bilangan berfaktor 5 adalah semua bilangan kelipatan 5. Jika J1 adalah jumlah bilangan kelipatan 5 yang ≤ N tersebut maka J1 = N div 5.

• di antara bilangan‐bilangan itu terdapat bilangan‐bilangan kelipatan 25, yaitu yang menyumbang faktor 5 sebanyak dua kali. Jika J2 adalah banyaknya kemunculan bilangan kelipatan 25 yang ≤ N, maka J2 = N div 25.

• di antara bilangan‐bilangan itu terdapat bilangan‐bilangan kelipatan 125, yaitu yang menyumbang faktor 5 tiga kali. Jika J3 adalah banyaknya kemunculan bilangan kelipatan 125 yang ≤ N maka J3 = N div 125.

• ... dst.

Maka, jumlah faktor 5 pada N! = J1 + J2 + J3 + ... = (N div 5) + (N div 25) + (N div 125) + ... berdasarkan analisis ini anda cukup membuat iterasi untuk menghitung dan mentotalkan (N div i) dengan i deret 5, 25, 125, ... selama i ≤ N. Algoritma yang diperoleh hanya berisi 8 baris saja sebagai berikut. Untuk N = 1012, iterasi hanya dilakukan kurang dari 18 kali (log5(1012) < 18). Jadi program yang efisien untuk menjawab masalah di atas adalah program yang sangat pendek sebagai berikut.

readln(N); i := 5; count := 0; while i <= N do begin count := count + (N div i); i := i * 5; end; writeln(count);

Dengan contoh ini, hendak ditunjukkan bahwa masalah yang diberikan dalam materi pemrograman bukanlah semata masalah pemrograman itu saja melainkan masalah analitika yang mendalam kemudian pemrograman hanyalah sebagai realisasinya yang seringkali hanya dengan pembuatan program yang singkat/pendek semata. Pada tingkat kesulitan yang lebih tinggi hingga tingkat Olimpiade Internasional, berlaku cara berpikir demikian. (Lihat pembahasan sejumlah soal contoh di website http://www.toki.or.id).

http://www.toki.or.id/


33/110

F. Penutup Melalui dokumen ini penulis berharap peserta ataupun pembina peserta dapat menemukan intisari dan tujuan mengenai soal‐soal seleksi mulai dari tingkat Kabupaten/Kotamadya, tingkat Provinsi dan tingkat Nasional. Peserta yang lolos ke Tingkat Pelatihan Nasional (Pelatnas) diharapkan merupakan peserta yang memiliki kemampuan analitikal dan merancang algoritma yang tinggi. Referensi mengenai hal tersebut jauh lebih sulit ditemukan daripada referensi untuk pemrograman itu sendiri. Tulisan awal ini merupakan versi yang perlu diolah lebih lanjut agar bisa menjadi referensi yang membantu para peserta namun diharapkan bisa memenuhi kebutuhan, sekurangnya sebagai petunjuk, bagaimana soal‐soal seleksi olimpiade sains bidang informatika dan komputer ini dibuat. Masukan untuk menyempurnakan tulisan ini sangat diharapkan untuk meningkatkan manfaat terutama para calon peserta dan pembina peserta dalam mempersiapkan diri menghadapi proses seleksi.

Deskripsi Ringkas Situs TOKI Learning Center Penulis: Dr. Inggriani Liem v. 080703 Roberto Eliantono Brian Marshal

34/110

DESKRIPSI RINGKAS SITUS TOKI LEARNING CENTER

Tujuan Bahan Ini 1. Siswa mengenali layar‐layar dan fasilitas yang disediakan pada aplikasi

berbasis web yang dipakai pada saat OSN (TOKI Learning Center). 2. Siswa memahami “best practices” dalam bekerja secara online pada saat

kompetisi. 3. Siswa dapat mulai berlatih selama PJJ.

Batasan Aplikasi Interaksi yang dilakukan dengan aplikasi ini sederhana, seperti aplikasi web pada umumnya. Untuk menggunakan aplikasi ini, siswa harus sudah mampu mengakses sebuah URL, memahami fungsi “link”, “button”, “radio button”, dan mengetik teks.

Halaman Utama

Halaman utama TOKI Learning Center terdiri atas tiga bagian utama, yaitu: 1. Box informasi sesi, yang menunjukkan informasi pengguna sistem dan waktu

server. 2. Informasi penting, berisi pesan‐pesan penting yang dianggap perlu diketahui

pengguna. Ralat soal dan pengumuman‐pengumuman penting biasa dituliskan di sini.

Banner, pesan bergerak, untuk hal-hal penting


35/110

3. Menu utama sistem, yang berisi link‐link untuk mengakses fasilitas TOKI Learning Center

Fasilitas Yang Tersedia • Question and Answer: hanya dibuka saat OSN, merupakan menu yang

memungkinkan peserta mengajukan pertanyaan‐pertanyaan tentang soal. Jawaban atas semua pertanyaan peserta juga ditampilkan pada halaman ini.

• Menjawab Soal‐soal Pilihan Berganda: menu untuk membaca dan mengisi jawaban soal‐soal pilihan berganda

• Materi dan Tugas‐tugas: berisi materi (untuk PJJ) dan/atau deskripsi tugas‐tugas pemrograman.

• Submit Tugas: merupakan menu untuk mengirimkan jawaban tugas pemrograman

• Status Pengumpulan Tugas pemrograman Saya: untuk melihat status pengumpulan tugas pemrograman

• Meminta Untuk Dinilai (Tgs Pemrograman): untuk meminta agar tugas pemrograman dinilai, ditutup saat OSN.

• Lihat Tabel Nilai: untuk melihat tabel nilai, ditutup saat OSN. • Forum Diskusi: untuk melakukan diskusi antarpeserta serta supervisor,

ditutup saat OSN. • Who Is Who?: menampilkan identitas pengguna sistem. • Ubah Data dan Password: untuk mengubah identitas dan password, ditutup

saat OSN. • Logout: keluar dari sistem.


36/110

Tanya Jawab

• Hanya dibuka saat perlombaan (OSN), dan waktu yang diberikan terbatas

(misalnya, 1 jam pertama). • Diberikan kesempatan bertanya, pertanyaan dan jawaban dapat dilihat oleh

semua kontestan. • Pertanyaan:

o Harus jelas supaya bisa dijawab dengan Ya/Tidak. Pada pilihan ganda tidak mengacu ke nomor soal, melainkan ke kalimat pernyataan.

Pada soal pemrograman, mengacu ke judul soal. o Yang tidak bisa dijawab dengan Ya/Tidak akan dijawab: No Comment. o Mungkin dijawab : “Baca soal lebih teliti”.

• Rambu‐rambu: o Pertanyaan diajukan dalam bahasa Indonesia/Inggris yang baik dan

benar. o Dilarang mendiskusikan jawaban. o Tidak mengajukan pertanyaan yang sama.

Pertanyaan yang diajukan Jawaban


37/110

Memilih Soal Pilihan Berganda

Menjawab Soal Pilihan Ganda

Klik Button untuk menjawab per soal

Klik untuk submit

Klik Button untuk menghapus


38/110

Lembar Jawab Pilihan Ganda

Pilihan Ganda • Jika ada ralat, maka teks dituliskan dalam warna lain dan diumumkan. • Harap perhatikan pengumuman. • Anda dapat menjawab satu per satu, atau via Lembar jawaban. • Jika Anda memilih untuk mengisi via Lembar Jawab (sekaligus), jangan

tunggu saat terakhir untuk submit.

Klik radio button untuk menjawab

Klik untuk simpan


39/110

Menu Deskripsi Soal (Untuk mengakses soal)

Soal Problem Solving (dengan membuat program) • Baca dengan cermat deskripsi (persoalan, input, output), format

input/output, batasan memori dan waktu eksekusi. • Jika ada ralat maka teks dituliskan dalam warna lain dan diumumkan.

Daftar soal programming


40/110

Rekapitulasi Submisi

• Hanya hasil submisi yang terakhir yang dinilai.

o Anda diberi kesempatan untuk beberapa kali submisi. o Kesempatan yang masih tersisa dapat dilihat pada halaman rekap.

• Submisi ditutup saat waktu diumumkan. • Jangan menunggu sampai saat terakhir. Anda dapat mengumpulkan nilai

dengan men‐submit ketika ada jawaban yang sudah lolos test case.

Meminta Untuk Dinilai • Dengan Fasilitas ini, grader akan menilai program. Sistem akan

mengeksekusi dan menyampaikan hasilnya. • Selama lomba:

o Fasilitas ini dimatikan. [Fasilitas ini dihidupkan saat PJJ] o Untuk mengetahui apakah jawaban benar/salah, harus

mengkompilasi dan mengeksekusi sendiri secara lokal. Hanya source code yang disubmisi.

Forum Diskusi • Dimatikan pada saat lomba. • Pada saat PJJ, dapat dipakai sebagai sarana untuk mendiskusikan jawaban

dan bertukar pendapat dengan peserta lain atau pengasuh.

Rekapitulasi hasil submisi


41/110

Ubah Password • Fasilitas ini dimatikan saat lomba. Jagalah kerahasiaan password yang

diberikan kepada Anda. • Saat PJJ dipakai untuk mengubah password yang diberikan.

Logout • Jangan lupa melakukan logout, terutama pada saat PJJ. • Keluar/meninggalkan aplikasi tanpa logout mungkin akan mengakibatkan

hal‐hal yang tidak diinginkan.

Contoh Soal dan Pembahasan Penulis: Tim Pembina dan Alumni TOKI v. 080704

42/110

CONTOH SOAL DAN PEMBAHASAN

Soal Aritmatika, Analitika dan Logika 1. Seorang wanita menerima warisan sebesar 3

1 dari harta suaminya seorang pengusaha yang meninggal dunia karena kecelakaan pesawat. Dan tiga orang putranya juga menerima masing‐masing 3

1 dari sisanya. Jika wanita tersebut dan salah seorang anaknya menerima total sebesar Rp. 6 milyar, berapakah total harta yang ditinggalkan oleh pengusaha tersebut ?

(A) Rp. 9 milyar (B) Rp. 9,6 milyar (C) Rp. 10.8 milyar (D) Rp. 13.5 milyar (E) Rp. 18 milyar

Misal:

harta pengusaha = x

warisan yang diterima istri pengusaha = w

warisan yang diterima putra pengusaha = p

Deskripsi matematis persoalan:

13131 13 31 23 329

( )( )

6?

w xp x w

x xx

xw p

x

=

= × −

= × −

= ×

=

+ ==

Penyelesaian:


43/110

1 23 93 29 9

59

95545

6666

6

10.8

w px xx x

xx

+ =+ =

+ =

=

= ×

=

=

(OSP 2006) 2. Jika x = 0.888, y = 888.0 , dan z = (0.888)2, manakah pernyataan berikut yang

paling benar ? (A) x < y < z (B) x < z < y (C) y < x < z (D) y < z < x (E) z < x < y

Bilangan real di antara 0 dan 1 (eksklusif), jika dikuadratkan akan semakin kecil, jika diakarpangkatduakan akan semakin besar.

Sebagai referensi,

2

0.888 0.942(0.888) 0.789

≈

≈

(OSP 2006) 3. Jika n adalah nilai rata‐rata dari tiga buah angka yaitu 6, 9, dan k berapakah nilai k

sesungguhnya ? (A) 3n – 15 (B) n – 5 (C) n – 15

(D) 315−n

(E) 315+n


44/110

6 93

15 33 15

k n

k nk n

+ +=

+ == −

(OSP 2006)

4. Seorang Pedagang membeli buku dari penyalur di kawasan Pasar Cikapundung, Bandung seharga Rp. 36.000, dia harus menyisakan biaya ongkos sebesar 10%. Selain itu dia juga harus menyisakan keuntungan sebesar Rp. 9.000 per bukunya. Harga jual buku tersebut akan naik berapa persen jika dibandingkan harga belinya ?

(A) 27.5 % (B) 35 % (C) 45 % (D) 25 % (E) 15 %

Misal:

Harga jual buku = s

Harga beli buku = b

Selisih harga jual dan harga beli = d

Deskripsi matematis persoalan:

3600010% 9000

?

bs b bd s bdb

== + += −

=

Penyelesaian:


45/110

720

10% 90001.1 90001.1 36000 900039600 900048600

48600 36000126001260036000

100%35%

s b bb

d s b

db

= + += += × += +=

= −= −=

=

= ×

=

(OSP 2006)

5. Ibu Dina sedang mencoba untuk membuka usaha ‘bakery’ disebuah ruko di perumahan elit di kawasan Cibubur. Dari resep yang ia pelajari, untuk suatu campuran adonan brownies kukus diperlukan 1½ cangkir terigu dan 4½ cangkir air. Bila ternyata sisa tepung terigu yang tersisa di lemari tinggal ¾ cangkir, berapa cangkirkah air yang diperlukan ?

(A) 2 cangkir (B) 2 ¼ cangkir (C) 3 ½ cangkir (D) 3 ¼ cangkir (E) Sesuai dengan resep

Perbandingan terigu dan air dalam adonan = 3 91 12 2 2 21 : 4 : 1: 3= =

Karena perbandingan terigu dan air dalam suatu adonan haruslah tetap, jumlah air yang diperlukan apabila tepung terigu yang tersisa tinggal 3

4 cangkir adalah 3 9 1

4 4 43 2× = = cangkir.

(OSP 2006) 6. Hitunglah (80! × 38!) /(77! × 40!)

(A) 316 (B) 2023 (C) 871 (D) 412 (E) 391


46/110

80 79 7880! 38! 80!77! 40!

× ××

=×

38!×

77! 40 3940!

××2

80=279 78× ×

40 39×4 79316

= ×=

(OSP 2006) 7. Jumlah dua digit pertama dari bilangan hasil perkalian 530003 × 810004 adalah

(A) 16 (B) 6 (C) 14 (D) 10 (E) 8

10 00430003 10004 30003 3

30003 3 10004

30003 30012

30003 9

30003

5 8 5 (2 )5 25 210 2512 10

×

× = ×

= ×

= ×

= ×

= ×

Jumlah dua digit pertama hasil perkalian tersebut adalah 5 + 1 = 6

(OSP 2006) Untuk nomor soal 89 perhatikan penjelasan ini Ingat bahwa perkalian tiga matriks A.B.C dapat dilakukan dengan cara (A.B).C, yaitu A.B terlebih dahulu kemudian hasilnya dengan C atau A.(B.C), yaitu B.C diperkalikan terlebih dahulu kemudian A dikalikan dengan hasilnya. Jika suatu fungsi perkalian matriks “dihargai” sbb. Dua matriks A berukuran baris x kolom = m x n dikalikan matriks B berukuran = n x p maka harga perkalian matriks tersebut adalah m x n x p. 8. Diberikan matriks‐matriks A, B, C, dan D masing‐masing berukuran 20x200, 200x20,

20x100, 100x10. Berapakah harga untuk urutan perkalian (A.B).(C.D) ? (A) 820.000 (B) 680.000 (C) 420.000


47/110

(D) 104.000 (E) 800.000

Perkalian A dengan B menghasilkan matriks baru (misalkan bernama E) berukuran 20 × 20.

Perkalian C dengan D menghasilkan matriks baru (F) berukuran 20 × 10.

Harga (A.B) = 20 × 200 × 20 = 80 000

Harga (C.D) = 20 × 100 × 10 = 20 000

Harga (E.F) = 20 × 20 × 10 = 4 000

Total harga = harga (A.B) + harga (C.D) + harga (E. F) = 80 000 + 20 000 + 4 000

= 104 000

(OSP 2006) 9. Diberikan perkalian dari empat matriks A.B.C.D yang masing‐masing berukuran

20x200, 200x20, 20x100, 100x10. Manakah urutan perkalian matriks yang membutuhkan biaya paling murah?

(A) ((A.B).C).D (B) (A.B).(C.D) (C) (A.(B.C)).D (D) A.((B.C).D) (E) A.(B.(C.D))

Harga pilihan jawaban A:

A.B = 20 × 200 × 20

= 80 000

(A.B).C = 20 × 20 × 100

= 40 000

((A.B).C).D = 20 × 100 × 10

= 20 000

Total = 140 000


48/110

Harga pilihan jawaban B:

A.B = 20 × 200 × 20

= 80 000

C.D = 20 × 100 × 10

= 20 000

(A.B).(C.D) = 20 × 20 × 10

= 2 000

Total = 102 000

Harga pilihan jawaban C:

B.C = 200 × 20 × 100

= 400 000

A.(B.C) = 20 × 200 × 100

= 400 000

(A.(B.C)).D = 20 × 100 × 10

= 20 000

Total = 820 000

Harga pilihan jawaban D:

B.C = 200 × 20 × 100

= 400 000

(B.C).D = 200 × 100 × 10

= 200 000

A.((B.C).D) = 20 × 200 × 10

= 40 000

Total = 640 000

Harga pilihan jawaban E:


49/110

C.D = 20 × 100 × 10

= 20 000

B.(C.D) = 200 × 20 × 10

= 40 000

A.(B.(C.D)) = 20 × 200 × 10

= 40 000

Total = 100 000

Dari perhitungan di atas, didapatkan bahwa urutan perkalian matriks yang membutuhkan biaya paling murah (100 000) adalah A.(B.(C.D)).

(OSP 2006)

10. Pepen berdiri sejauh 18 meter di sebelah utara Tugu Pemuda, Fanny berdiri 24 meter di sebelah barat Tugu yang sama. Berapakah jarak terdekat antara Fanny dan Pepen yang dapat ditempuh ?

(A) 30 meter (B) 900 meter (C) 6 meter (D) 42 meter (E) 90 meter

Posisi Pepen, Fanny dan Tugu Bermuda membentuk segitiga siku‐siku pada Tugu Bermuda di mana jarak antara Pepen dan Fanny adalah sisi miring segitiga.

18 = 3 x 6, dan 24 = 4 x 6.

Dengan Triple Pythagoras {3, 4, 5}, maka sisi miring segitiga tersebut adalah:

30 = 5 x 6

(OSP 2008) 11. Apabila dua buah bilangan 2n dan 5n (di mana n adalah bilangan bulat positif)

dimulai dengan digit yang sama, maka digit tersebut adalah... (Catatan: bilangan dituliskan dengan notasi desimal, tanpa diawali nol.)

(A) 9


50/110

(B) 5 (C) 6 (D) 7 (E) 3

Pada n = 5, 25 = 32 dan 35 = 3125

(OSP 2008)

12. Jika a, b, c, d dan e adalah bilangan‐bilangan bulat yang tidak nol dan tidak negatif serta tidak ada yang sama, dan diketahui pula a+b+c+d=10, berapakah harga terbesar yang mungkin dari ab+cd ?

(A) 10 (B) 32 (C) 25 (D) 14 (E) > 50

Set empat bilangan positif unik yang memenuhi persamaan a + b + c + d = 10 hanya ada satu: {1, 2, 3, 4}. Dari set bilangan tersebut, hanya ada tiga kombinasi yang unik:

a . b + c . d

1 . 2 + 3 . 4 = 14

1 . 3 + 2 . 4 = 11

1 . 4 + 2 . 3 = 10

(OSP 2008) 13. Di dalam suatu kotak terdapat 2N buah bola dan di antaranya terdapat N bola

berwarna putih dan N bola beraneka warna secara unik (satu bola satu warna, tidak ada yang sama) dan tidak putih. Berapa banyak kombinasi untuk memilih N bola dari 2N bola itu? (Catatan: Dalam perhitungan kombinasi, AAB dan ABA dianggap sama.)

(A) 2N (B) (2N / 2)


51/110

(C) 2N (D) N! (E) (2N)! / N!

Banyak kombinasi memilih N bola dari 2N bola tersebut bisa dipecah menjadi beberapa bagian:

- Banyak kombinasi memilih N bola di mana tidak ada bola berwarna terambil NC0, hanya ada 1 cara.

- Banyak kombinasi memilih N bola di mana tepat satu bola berwarna terambil NC1.

Misalkan N = 4, bola putih = A, bola berwarna = B, C, D dan E.

Bola tersedia: AAAABCDE

Banyak cara memilih satu bola berwarna dari empat yang tersedia adalah 4C1 (= 4).

AAAB, AAAC, AAAD, AAAE.

- Banyak kombinasi memilih N bola di mana tepat dua bola berwarna terambil NC2

Misalkan N = 4, bola putih = A, bola berwarna = B, C, D dan E.

Bola tersedia: AAAABCDE

Banyak cara memilih dua bola berwarna dari empat yang tersedia adalah 4C2 (= 6).

AABC, AABD, AABE, AACD, AACE, AADE.

- … - Banyak kombinasi memilih N bola di mana tepat N bola berwarna terambil

NCN

Catatan: NCk adalah banyak kombinasi memilih k benda dari N pilihan.

Dengan demikian jumlah seluruh kombinasinya adalah atau sama dengan 2N

(OSP 2008) 14. Pak Dengklek memiliki buku yang bernomor halaman mulai 1 s.d. N. Jika

semua nomor halaman buku tersebut ditulis secara berderet dibutuhkan 552 digit. Berapakah N?


52/110

(A) 205 (B) 210 (C) 211 (D) 212 (E) 220

Jumlah digit pada deret angka 1 s/d 999 adalah:

1 – 9 : 9 x 1 digit = 9 digit

10 – 99 : 90 x 2 digit = 180 digit

100 – 999 : 900 x 3 digit = 2700 digit

Jumlah digit yang ditulis pada buku Pak Dengklek adalah 552, sehingga buku tersebut berakhir pada halaman dengan tiga digit (100 – 999). Banyak halaman yang terdiri dari tiga digit adalah: (552 – 9 – 180) / 3 = 121 halaman. Dengan demikian jumlah halaman total di buku tersebut adalah 9 + 90 + 121 = 220 halaman.

(OSP 2008) 15. Berapa banyak segi empat yang terbentuk dari tabel berukuran 3x3?

(A) 36 (B) 27 (C) 30 (D) 40 (E) 35


53/110

Ada sembilan jenis segi empat yang bisa dibentuk:

1 x 1 (9 buah)

1 x 2 (6 buah)

…

1 x 3 (3 buah) …

2 x 1 (6 buah)

2 x 2 (4 buah)

….

2 x 3 (2 buah) ….

3 x 1 (3 buah)

….

3 x 2 (2 buah)

3 x 3 (1 buah)

Total: 36 buah

Jika soal ini digeneralisasi dari tabel 3 x 3 menjadi tabel n x n, maka kita akan menemukan suatu pola bilangan:

n Jumlah segi empat 1 1 = 12 2 9 = (1 + 2)2 3 36 = (1 + 2 + 3)2 4 100 = (1 + 2 + 3 + 4)2 … … n Sn2 = (1 + 2 + … + n)2

Di mana Sn adalah jumlah bilangan bulat positif dari 1 sampai n.

(OSP 2008) 16. Pak Ganesh menulis angka 1 s.d. 10000. Berapa banyak angka 1 yang muncul pada

hasil tulisan Pak Ganesh?

(A) 5000 (B) 1000 (C) 4001 (D) 2092 (E) 3505


54/110

Cari ada berapa banyak kemunculan angka 1 pada penulisan angka 0000 s/d 9999 (bilangan 4 digit). Permasalahan ini bisa dipecah menjadi beberapa bagian:

Kemunculan angka 1 pada digit pertama : 1***

Kemunculan angka 1 pada digit kedua : *1**

Kemunculan angka 1 pada digit ketiga : **1*

Kemunculan angka 1 pada digit keempat : ***1

Catatan: simbol * merepresentasikan angka sembarang dari 0 s/d 9.

Pada masing‐masing kemunculan di atas, simbol *** bisa digantikan oleh sembarang angka dari 000 s/d 999, sehingga total masing‐masing terdapat 1000 kombinasi. Dengan demikian, total kemunculan angka 1 pada bilangan 4 digit (0 s/d 9999) ada 4000 buah. Sehingga, kemunculan angka 1 pada 1 s/d 10000 adalah 4001.

(OSP 2008) 17. Di suatu provinsi, diadakan lomba voli tiap 3 tahun sekali, lomba bulutangkis

tiap 4 tahun sekali, lomba sepak bola tiap 7 tahun sekali, dan lomba tenis tiap 6 tahun sekali. Pada tahun 2000 semua lomba tersebut diadakan. Berapa kali terdapat lebih dari satu lomba dalam setahun dalam periode antara tahun 2005 dan tahun 2017?

(A) Kurang dari 8 kali (B) 8 kali (C) 9 kali (D) 10 kali (E) Lebih dari 10 kali


55/110

Tabel penyelenggaraan lomba per tahun:

2000 A B C D

2001 A B C D

2002 A B C D

2003 A B C D

2004 A B C D

2005 A B C D

2006 A B C D

2007 A B C D

2008 A B C D

2009 A B C D

2010 A B C D

2011 A B C D

2012 A B C D

2013 A B C D

2014 A B C D

2015 A B C D

2016 A B C D

2017 A B C D

A : Voli (setiap 3 tahun)

B : Bulutangkis (setiap 4 tahun)

C : Sepak Bola (setiap 7 tahun)

D : Tenis (setiap 6 tahun)

(OSP 2008) 18. Tahun "semi‐kabisat" adalah tahun yang bukan merupakan tahun kabisat, tetapi

jika tiap bilangan penyusun angka tahunnya dijumlahkan, hasilnya habis dibagi dengan 4. Ada berapa tahun "semi‐kabisat" semenjak tahun 1901 hingga 1960?

(A) 10 (B) 12 (C) 15 (D) 16 (E) 18

Hanya dua digit terakhir pada angka tahun yang berubah dari 1901 hingga 1960. Karena sisa pembagian dengan 4 dari jumlah dua digit pertama adalah 2 (dari (1 + 9) mod 4), maka jumlah dua digit terakhir juga harus memiliki 2 sebagai sisa pembagian dengan 4 (agar keseluruhan bilangan habis dibagi 4).

Banyaknya bilangan dari 1 s/d 60 yang jumlah digitnya memiliki 2 sebagai sisa pembagian dengan 4 adalah:

190* : 1902, 1906


56/110

191* : 1911, 1915, 1919

192* : 1920, 1924, 1928

193* : 1933, 1937

194* : 1942, 1946

195* : 1951, 1955, 1959

1960 : 1960

Dari 16 tahun di atas, yang merupakan tahun kabisat ada sebanyak 4 buah, yaitu: 1920, 1924, 1928, 1960. Dengan demikian jumlah tahun semi‐kabisat dari 1901 hingga 1960 adalah 16 – 4 = 12 buah.

(OSP 2008)

19. Jika n adalah sebuah bilangan bulat ganjil, maka: (i) n3 – n2 pasti ganjil (ii) n2 – n pasti genap (iii) n3 – n pasti ganjil (iv) n4 – n2 pasti genap Pernyataan yang benar adalah:

(A) (i), (iii) (B) (i), (ii), (iii) (C) (ii), (iv) (D) (ii), (iii), (iv) (E) (iv)

Sebuah bilangan ganjil jika dipangkatkan dengan bilangan bulat positif apapun akan menghasilkan bilangan ganjil juga.

Pernyataan (i) : n3 – n2 pasti ganjil

ganjil – ganjil = genap, pernyataan (i) salah!

Pernyataan (ii) : n2 – n pasti genap

ganjil – ganjil = genap, pernyatan (ii) benar!

Pernyataan (iii) : n3 – n pasti ganjil

ganjil – ganjil = genap, pernyataan (iii) salah!


57/110

Pernyataan (iv) : n4 – n2 pasti genap

ganjil – ganjil = genap, pernyataan (iv) benar!

(OSP 2008)

20. Si Upik pandai menjumlahkan, namun ia hanya dapat menulis angka 1 dan 2. Oleh

karena itu, saat Upik ingin menuliskan sebuah angka yang lebih dari 2, ia menuliskan beberapa angka 1 dan beberapa angka 2 sedemikian sehingga jika dijumlahkan jumlahnya adalah bilangan tersebut. Contohnya, untuk menuliskan angka 3, Upik memiliki tepat 3 cara yaitu 12, 21, atau 111 (1+2=3 ; 2+1=3 ; 1+1+1=3). Untuk menuliskan angka 2, sebenarnya Upik memiliki 2 cara yaitu 2 dan 11 (2=2; 1+1=2), tapi hanya ada 1 cara untuk menuliskan angka 1. Berapa banyak cara Upik untuk menuliskan angka 8?

(A) 21 (B) 25 (C) 30 (D) 34 (E) 55

Untuk menuliskan angka 8, ada dua operasi yang bisa dilakukan:

- Menuliskan angka 1 di paling depan, sehingga angka yang tersisa adalah 7. - Menuliskan angka 2 di paling depan, sehingga angka yang tersisa adalah 6.

Banyaknya cara menuliskan angka 8 adalah jumlah dari banyaknya cara melakukan dua operasi di atas (banyak cara menuliskan angka 7 dan banyak cara menuliskan angka 6).

Misalkan banyaknya cara menuliskan angka n adalah f(n), maka relasi rekurens pada permasalahan ini adalah:

- f(1) = 1 - f(2) = 2 - f(n) = f(n – 1) + f(n – 2)

n 1 2 3 4 5 6 7 8 f(n) 1 2 3 5 8 13 21 34

(OSP 2008)


58/110

21. Pak Dengklek ingin membagikan buku tulis kepada 100 anak panti asuhan. Masing‐masing anak mendapat setidaknya satu buku tulis, dan tidak ada anak yang mendapat lebih dari lima buku tulis. Tidak ada seorang anak pun yang mendapat buku tulis lebih banyak dari jumlah buku tulis yang dimiliki dua orang anak lainnya. Jika Aseng, Adi, dan Ujang adalah anak panti asuhan dan Aseng mendapat tiga buku tulis, maka pernyataan manakah yang benar di bawah ini:

(i) Ujang mungkin hanya mendapat satu buku tulis. (ii) Jika diketahui Ujang mendapat empat buku tulis, maka Adi tidak mungkin mendapat satu buku tulis. (iii) Tidak mungkin ada anak yang mendapat tepat lima buku tulis.

(A) (i) dan (ii) benar (B) (i) dan (iii) benar (C) (ii) dan (iii) benar (D) (i), (ii), dan (iii) benar (E) Pilihan a sampai d salah semua

Fakta/Aturan:

a. Masing‐masing anak mendapatkan antara satu sampai dengan lima buku tulis.b. Tidak ada seorang anak pun yang mendapat buku tulis lebih banyak dari

jumlah buku tulis yang dimiliki dua orang anak lainnya. c. Aseng mendapat tiga buku tulis.

Pernyataan (i) : Ujang mungkin hanya mendapat satu buku tulis.

Ada satu cara pembagian buku yang membenarkan pernyataan ini: Aseng 3 buku tulis, Ujang 1 buku tulis dan Adi 2 buku tulis. Pernyataan (i) benar!

Pernyataan (ii) : Jika diketahui Ujang mendapat empat buku tulis, maka Adi tidak mungkin mendapat satu buku tulis.

Ada satu cara pembagian buku yang menggagalkan pernyataan ini: Aseng 3 buku tulis, Ujang 4 buku tulis dan Adi 1 buku tulis. Pembagian dengan cara ini tidak melanggar aturan/fakta yang ada. Pernyataan (ii) salah!

Pernyataan (iii) : Tidak mungkin ada anak yang mendapat tepat lima buku tulis.

Ada beberapa cara pembagian buku yang menggagalkan pernyataan ini, salah satunya adalah: Aseng 5 buku tulis, Ujang 5 buku tulis dan Adi 5 buku tulis. Pembagian dengan cara ini tidak melanggar aturan/fakta yang ada. Pernyataan (iii) salah!


59/110

(OSP 2008) 22. Suatu hari Pak Dengklek mengajak Pak Ganesh bermain. Mula‐mula Pak Dengklek

memberikan sebuah kertas yang sudah bergambar segi empat berukuran 8 cm x 9 cm lalu meminta Pak Ganesh menggambar N buah titik di atas kertas itu sedemikian sehingga tidak ada dua buah titik yang berjarak kurang dari 5 cm (semua titik yang digambar tidak boleh berada di luar segi empat yang sudah tergambar sebelumnya, tetapi boleh di dalam atau tepat pada garis segi empat tersebut). Pak Dengklek menang jika Pak Ganesh tidak mampu menggambar N buah titik dengan syarat tersebut. Berapa N minimal agar Pak Dengklek pasti menang?

(A) 5 (B) 6 (C) 7 (D) 8 (E) 9

Jumlah titik maksimum yang dapat diletakan pada kertas tersebut adalah 6 buah.

Dengan demikian agar Pak Dengklek menang, nilai N yang diberikan harus di atas 6.

(OSP 2008)


60/110

Soal Algoritmika 23. Perhatikan potongan algoritma berikut:

Procedure kocok(d: integer; kata: string); var i: integer; c : char; begin i:=1; repeat c := kata[i]; kata[i] := kata[i+d]; kata[i+d] := c; i:= i+1; until (i=length(kata)-1); writeln(kata); end;

Apa yang dicetaknya pada pemanggilan kocok(1, 'GO GET GOLD') ? (A) GO GET GOLD (B) O GET GOLGD (C) DGO GET GOL (D) GET GOLDOG (E) go get gold

Keadaan awal : d=1 dan kata=’GO GET GOLD’

Keterangan : length(kata) = 11, i merupakan indeks perulangan dalam prosedur tersebut

Penukaran karakter dilakukan pada karakter ke‐i dengan ke‐i+1, yang pada tabel di bawah ini ditandai dengan warna kuning

Karakter ke‐ i 1 2 3 4 5 6 7 8 9 10 11 G O G E T G O L D 1 O G G E T G O L D 2 O G G E T G O L D 3 O G G E T G O L D 4 O G E G T G O L D 5 O G E T G G O L D 6 O G E T G G O L D 7 O G E T G G O L D 8 O G E T G O G L D 9 O G E T G O L G D 10 Selesai

Jadi, yang dicetak setelah pemanggilan kocok(1,’GO GET GOLD’) adalah O GET GOLGD

(OSP 2007)


61/110

24. Perhatikan potongan algoritma berikut:

c := 0; d := 0; while (a>b) do begin a:= a-b; c:= c+1; d:= d+b; end; writeln(c, ‘, ‘,d);

Jika nilai a=23, b=4, maka keluaran dari algoritma di atas adalah: (A) 3, 33 (B) 1, 4 (C) 0, 0 (D) 6, 23 (E) 5, 20

Pemrosesan algoritma tersebut dapat ditunjukkan pada tabel di bawah ini.

a b C d Keterangan 23 4 0 0 Kondisi awal, a>b 19 4 1 4 a>b 15 4 2 8 a>b 11 4 3 12 a>b 7 4 4 16 a>b 3 4 5 20 Loop berhenti karena a<=b

Jadi, keluaran dari algoritma tersebut adalah 5, 20

(OSP 2007) 25. Perhatikan potongan algoritma berikut:

procedure panjang (p: integer); var z : array[0..9] of integer; a, b, c, d : integer; x : integer; begin for a:= 0 to 9 do case (a mod 5) of 0 : z[a] := 3; 1 : z[a] := 1; 2 : z[a] := 4; 3 : z[a] := 2; 4 : z[a] := 0; end;


62/110

for b:= 9 downto 0 do begin x:= 3*z[b]; z[b]:= a - b; end; for c:= 0 to 9 do if (c mod 2 = 0) then z[c]:= z[c] + 5; for d:= 9 downto 0 do if (z[d] < 0) then z[d] := z[d] * -1; writeln(z[p]); end;

Apakah keluaran yang dihasilkan algoritma di atas dalam pemanggilan panjang(9)? (A) 8 (B) 6 (C) 4 (D) 2 (E) 0

Pada perulangan baris ke‐7, nilai elemen array z diisi oleh nilai‐nilai dalam case of berdasarkan nilai a mod 5. Nilai a pada akhir perulangan adalah 9.

a 0 1 2 3 4 5 6 7 8 9 z[a] 3 1 4 2 0 3 1 4 2 0

Pada perulangan baris ke‐15, nilai x diisi oleh hasil 3*nilai elemen array z pada masing‐masing indeks b. Nilai elemen array z masing‐masing tersebut juga berubah dan diisi nilai a – b, yaitu 9 – indeks b.

a 0 1 2 3 4 5 6 7 8 9 z[a] 9 8 7 6 5 4 3 2 1 0

Pada perulangan baris ke‐19, nilai elemen array z berubah menjadi 5 lebihnya dari nilai elemen array z sebelumnya jika indeks c dapat habis dibagi 2.

a 0 1 2 3 4 5 6 7 8 9 z[a] 14 8 12 6 10 4 8 2 6 0

Pada perulangan baris ke‐22, nilai elemen array z tidak berubah karena masing‐masing nilainya >=0.

Berdasarkan penjelasan di atas, keluaran pemanggilan panjang(9) adalah 0

(OSP 2007)


63/110

26. Perhatikan prosedur coba(n) berikut.

procedure coba(var n: integer); begin if n > 0 then begin n := n div 3; write(n mod 3); coba(n); end; end;

Apa yang akan dicetak saat pemanggilan coba(z) dengan z sebelumnya sudah memiliki harga 49? (A) 0001 (B) 1211 (C) 0121 (D) 1120 (E) 1210

Pemrosesan potongan algoritma tersebut dengan n=49 dapat direalisasikan dalam tabel berikut ini.

Pemanggilan n=n div 3 write(n mod 3) coba(n) coba(49) 16 1 coba(16) coba(16) 5 2 coba(5) coba(5) 1 1 coba(1) coba(1) 0 0 coba(0) coba(0) Selesai

Jadi, yang akan tercetak adalah 1210

(OSP 2007)


procedure jalan(n: integer); begin if n > 0 then begin jalan(n div 5); write(n mod 5 + 1); end; end;


64/110

Pada pemanggilan jalan(49) pada procedure di atas ini apa yang akan dicetaknya kemudian?

(A) 222 (B) 52 (C) 49 (D) 255 (E) 5

jalan(49) :

- jalan(9)

‐ jalan(1)

‐ jalan(0)

‐ write(2)

‐ write(5)

- write(5)

Jadi, yang akan tercetak adalah 255

(OSP 2007)


procedure call(x:integer); begin if x<>0 then begin write(‘*’); x := x – 1; call(x); x := x + 1; end; end;

Apakah output dari pemanggilan call(3) ? (A) *** (B) * (C) ** (D) ******** ... (banyak tak terhingga) (E) ******


65/110

call(3):

- write(‘*’) - x = 2 - call(2)

‐ write(‘*’)

‐ x = 1

‐ call(1)

‐ write(‘*’)

‐ x = 0

‐ call(0)

‐ x = 1

‐ x = 2

- x = 3

Jadi, output yang dihasilkan adalah ***

(OSP 2007)

29. Perhatikan algoritma berikut:

Procedure geser(i: integer); begin i := (((i shl 4) shr 6) shl 2); writeln(i); end;

Apakah output dari pemanggilan geser(9) di atas? (A) 1 (B) 0 (C) 2 (D) 4 (E) 8


66/110

i = 910 = 10012

i shl 4 = 100100002

(i shl 4)shr 6 = 102

((i shl 4)shr 6)shl 2 = 10002 = 810

(OSP 2007)

30. Perhatikan algoritma berikut:

function ABC (a, b : integer) : integer; var hasil : integer; begin if (a mod b = 0) then ABC := b else ABC := ABC(a, b-1); end;

Berapakah hasil ABC(12, 4)? (A) ‐1 (B) 0 (C) 1 (D) 2 (E) 4

Fungsi ABC mengembalikan nilai b jika a merupakan kelipatan b (a mod b = 0). Jika b bukan faktor dari a, maka fungsi ini akan memanggil dirinya kembali dengan parameter ABC(a,b‐1). Tampak bahwa fungsi ABC akan mengembaikan nilai faktor terbesar dari a yang kurang dari atau sama dengan b. Maka hasil ABC(12,4) adalah 4.

(OSP 2008) Catatan: Jawaban dan pembahasan soal non‐pemrograman ini disusun oleh para kontributor TOKI1 dan bukan merupakan jawaban/pembahasan resmi.

1 Kontributor: Bernardino Dito; Brian Marshal; Prima Chairunnanda, B. Eng.; Riza Oktavian Nugraha Suminto; Roberto Eliantono Adiseputra; Suhendry Effendy, S. Kom.


67/110

Soal Pemrograman

Faktorial Kode Soal: OSN601

Batas Run-time: 1 detik / test-case Batas Memori: 32 MB

Masukan: Standard input Keluaran: Standard output

Diberikan sebuah bilangan N, N! disebut N faktorial dan nilainya dihitung dengan rumus :

N x (N ‐ 1) x (N ‐ 2) ... x 1.

Tugas Anda adalah menghitung berapa jumlah angka nol berturutan yang mengakhiri N!.

Sebagai contoh:

• N = 10: 10! = 3 628 800, maka jumlah angka nol adalah 2.

• N = 8: 8! = 40 320, jumlah angka nol adalah 1 (nol di tengah tidak dihitung).

FORMAT MASUKAN

Masukan hanya terdiri dari satu baris berisi bilangan bulat N (1 ≤ N ≤ 10 000).

FORMAT KELUARAN

Tuliskan satu bilangan bulat yang menyatakan jumlah angka nol yang mengakhiri N!.

CONTOH MASUKAN 1

10

CONTOH KELUARAN 1

2

CONTOH MASUKAN 2

8

CONTOH KELUARAN 2

1


68/110

CATATAN

Hati‐hati dengan integer overflow: tipe data longint atau long hanya dapat menampung bilangan hingga sekitar 2 milyar.

PETUNJUK

Jika anda dapat memanfaatkan sifat rumus faktorial, maka anda akan mendapatkan hasil yang lebih efisien

PEMBAHASAN2

Pertanyaan: Berapa banyak deretan angka nol di belakang bilangan faktorial N! ? Jika Anda menjawabnya dengan memperkalikan semua bilangan N.(N‐1).(N‐2)....2.1 dst maka anda hanya berhasil menjawab untuk N yang kecil (sebatas ukuran harga terbesar dari bilangan bulat yang disediakan serta batas waktu komputasi yang diberikan).

Jadi Anda perlu melakukan analisis sebagai berikut:

Karena banyaknya angka nol di belakang suatu angka bergantung pada berapa banyak kemunculan faktor 2 dan faktor 5 (mengapa? karena 2 kali 5 adalah 10). Dan khususnya, untuk suatu bilangan N! dapat dibuktikan banyaknya kemunculan faktor 5 tidak akan lebih banyak dari banyaknya kemunculan faktor 2. Maka, pertanyaan di atas dapat dijawab dengan hanya menghitung total banyaknya kemunculan faktor 5 dari bilangan‐bilangan pembentuk N! Bilangan yang berisi faktor 5 adalah bilangan‐bilangan kelipatan 5 saja jadi cukup kita memperhatikan bilangan‐bilangan kelipatan 5 ini. Misalnya dalam 10! hanya ada dua bilangan yang memiliki faktor 5 yaitu 5 dan 10 sendiri sehingga. Contoh lain, dalam 29! ada 5, 10, 15, 20, 25 yang berisi faktor 5, dan karena pada 25 faktor 5 muncul dua kali menyebabkan 29! berisi kemunculan faktor 5 sebanyak 6 kali (jadi ada 6 nol di belakang 29!). Dengan mengiterasi i dari 5 ke N dengan kelipatan 5, dan mendapatkan berapa banyak faktor 5 dari bilangan i, lalu menjumlahkannya, maka anda dapat menjawabnya dengan baik... untuk level OSN 2006 ini!

i := 5; count := 0; while i <= N do begin // menghitung berapa banyak kemunculan faktor 5 dalam i j := i; while (j mod 5) = 0 do begin j := j div 5; count := count + 1; end; i := i + 5; end; 2 Dikutip dari http://www.toki.or.id/archive/faktorialsolusi.html


69/110

Untuk tingkat OSN ini dengan cara demikian Anda dapat memperoleh nilai penuh. NAMUN, untuk tingkat lebih lanjut mungkin harga N bisa diberikan jauh lebih besar misalnya N = 1012, algoritma harus beriterasi luar (while) sebanyak 2.1011 kali ‐‐ dan untuk setiap harga i akan diperlukan sekian kali lagi beriterasi untuk menghitung banyaknya faktor 5 dalam i yang akhirnya akan memerlukan waktu komputasi yang besar!. Apalagi jika waktu eksekusi lebih dibatasi jelas solusi tersebut tidak akan memberikan nilai penuh. Untuk itu Anda harus menggali ide lebih lanjut lagi…

Perhatikan bahwa:

• bilangan‐bilangan berfaktor 5 adalah semua bilangan kelipatan 5. Jika J1 adalah jumlah bilangan kelipatan 5 yang ≤ N tersebut maka J1 = N div 5.

• di antara bilangan‐bilangan itu terdapat bilangan‐bilangan kelipatan 25, yaitu yang menyumbang faktor 5 sebanyak dua kali. Jika J2 adalah banyaknya kemunculan bilangan kelipatan 25 yang ≤ N, maka J2 = N div 25.

• di antara bilangan‐bilangan itu terdapat bilangan‐bilangan kelipatan 125, yaitu yang menyumbang faktor 5 tiga kali. Jika J3 adalah banyaknya kemunculan bilangan kelipatan 125 yang ≤ N maka J3 = N div 125.

• ... dst.

Maka, jumlah faktor 5 pada N! = J1 + J2 + J3 + ... = (N div 5) + (N div 25) + (N div 125) + ... berdasarkan analisis ini anda cukup membuat iterasi untuk menghitung dan mentotalkan (N div i) dengan i deret 5, 25, 125, ... selama i ≤ N. Algoritma yang diperoleh hanya berisi 8 baris saja sebagai berikut. Untuk N = 1012, iterasi hanya dilakukan kurang dari 18 kali (log5(1012) < 18). readln(N); i := 5; count := 0; while i <= N do begin count := count + (N div i); i := i * 5; end; writeln(count);

(OSN 2006)


70/110

Ulang Tahun Kode Soal: OSN603

Batas Run-time: 1 detik / test-case Batas Memori: 32 MB

Masukan: Standard input Keluaran: Standard output

Beberapa hari lagi, Pak Dengklek akan merayakan ulang tahunnya yang ke‐61. Beliau bermaksud akan mengundang teman‐temannya untuk menghadiri pesta ulang tahunnya tersebut. Sayangnya, beliau baru saja kehilangan satu‐satunya buku telepon yang dipunyainya. Karena itu, ia harus mengunjungi wartel terdekat dan membuka buku kuning (yellow pages) untuk mengetahui nomor telepon teman‐temannya. Tidak lupa ia mengajak Anda untuk membantunya mencarikan nomor telepon teman‐temannya tersebut.

Diberikan buku kuning yang berisi pasangan nama dan nomor telepon seluruh penduduk desa tempat Pak Dengklek tinggal, serta nama‐nama teman Pak Dengklek yang tinggal di desa tsb., tolonglah Pak Dengklek untuk mencari nomor telepon teman‐teman Pak Dengklek tersebut.

FORMAT MASUKAN

Baris pertama berisi dua buah bilangan bulat:

• N (1 ≤ N ≤ 10.000), menunjukkan jumlah penduduk desa yang terdaftar di buku kuning.

• Q (1 ≤ Q ≤ 10.000), menunjukkan jumlah teman Pak Dengklek.

N baris selanjutnya berisi nama dan nomor telepon setiap orang di desa tersebut, dipisahkan dengan spasi.

Q baris selanjutnya berisi nama‐nama teman Pak Dengklek. Nama setiap orang hanya akan tersusun dari huruf kapital, dengan panjang maksimal 15 huruf. Daftar nama pada buku kuning akan terurut sesuai abjad, tetapi daftar teman Pak Dengklek yang akan dicari nomor telponnya belum tentu terurut dan satu teman Pak Dengklek bisa saja ditanyakan lebih dari sekali. Setiap nomor telepon terdiri atas tepat 7 angka, satu nomor telepon dapat dimiliki oleh lebih dari satu orang. Semua teman pak Dengklek yang akan dicari nomor telponnya pasti tercantum dalam buku kuning.

FORMAT KELUARAN

Keluarkan Q baris, di mana setiap barisnya berisi nomor telepon dari teman yang ditanyakan oleh Pak Dengklek.


71/110

CONTOH MASUKAN

10 5 ACONG 8468431 BALAJI 1573547 GREGOR 1765743 JAPRA 3746843 JOKO 1357891 MALARANGENG 1375638 MANMOHAN 1357562 SITORUS 1378651 TERRY 8756345 YUDHOYONO 1781945 GREGOR YUDHOYONO ACONG MANMOHAN JAPRA

CONTOH KELUARAN

1765743 1781945 8468431 1357562 3746843

PEMBAHASAN3 Pertanyaan: Jika diberikan N data terurut tersimpan dalam tabel, lalu Anda diminta mendapatkan suatu data di antara N data tersebut, maka apa yang akan Anda lakukan?

Paling naif tentu Anda mencari dari baris pertama dalam N data tersebut hingga ditemukan data yang dicari itu. Pemeriksaannya adalah dengan operasi membandingkan string‐string yang bersangkutan (data yang dicari dan data tersimpan). Jika data sangat banyak sekali maka Anda akan menghadapi batas waktu komputasi.

Satu trik yang TERNYATA bisa lolos untuk mendapatkan nilai penuh di OSN ini (karena banyaknya datanya masih terlalu kecil!) adalah tetap dengan pemeriksaan dari baris pertama tetapi dengan memeriksa karakter pertama string‐string itu: Jika sama maka periksa karakter berikutnya sementara jika berbeda, maka skip data tersebut untuk memeriksa data pada baris berikutnya.

Untuk tingkat lebih lanjut tentu solusi tersebut dibuat untuk tidak akan mendapatkan nilai penuh! Untuk mendapatkan nilai penuh maka ada dua teknik yang perlu dikuasai yaitu algoritma binary search dan yang lebih lanjut lagi adalah dengan hash table.

3 Dikutip dari http://www.toki.or.id/archive/ultahsolusi.html


72/110

Algoritma binary search hanya dapat bekerja jika data sudah terurut. Idenya adalah sebagai berikut:

Misalkan data yang dicari adalah X. Data yang diperiksa pertama kali adalah data yang terdapat ditengah tabel. Jika tabel berindeks dari 1 s.d. N maka indeks tersebut adalah (N+1) div 2. Karena sudah terurut, jika data di tengah tadi bukanlah data yang dicari, maka X pasti berada di ruas kiri atau kanan tabel (sebelah kiri/kanan dari data tengah tadi). Sehingga, jika di ruas kiri, pemeriksaan dengan cara yang sama dapat diulangi pada ruas kiri tersebut yang kini sebagai keseluruhan. Untuk jelasnya Anda dapat melihat algoritma berikut.

// data nama dan no telepon ada di dalam array tabel[1..n] dengan // field nama dan field telepon bataskiri := 1; bataskanan := n; selesai := false; while not selesai and (bataskiri <= bataskanan) do begin tengah := (bataskiri + bataskanan) div 2; if (tabel[tengah].nama = X) then selesai := true else if (tabel[tengah].nama > X) then bataskanan := tengah - 1 else bataskiri := tengah + 1; end; if (selesai) then writeln(tabel[tengah].telepon); Algoritma ini dapat bekerja pada data yang sangat banyak dengan iterasi untuk kasus terburuknya dilakukan sebanyak log2(n). jadi untuk data 10000 paling banyak akan dilakukan sebanyak 13 iterasi.

Karena pemeriksaan kesamaan di atas merupakan operasi string yang dapat memerlukan waktu lebih lama daripada pemeriksaan bilangan, maka pemeriksaan dapat dilakukan karakter demi karakter saja (seperti pada trik yang dibahas di atas). Selain itu, kedua pemeriksaan itupun dapat dilakukan hanya satu kali saja. Bagaimana? Bagi C programmer maka bagian tersebut sudah ada dalam library C sebagai fungsi strcmp().....

(OSN 2006)

Materi PJJ Pra OSN 2008 Penulis: Tim Pembina dan Alumni TOKI v.08 final

73/110

MATERI PJJ PRA OSN 2008 Bagian Pertama1

Readln dan Writeln Nama Program: pjj0101.PAS / C / CPP Batas Runtime: 1 detik / test‐case Batas Memori: 16 MB Nama Berkas Masukan: Standard input (keyboard) Nama Berkas Keluaran: Standard output (layar)

Sebagai perkenalan pertama dengan program Pascal, ketikanlah perintah‐perintah program berikut ini lalu simpan sebagai 'pjj0101.pas'.

Program Pjj0101; var brs: string; begin readln(brs); writeln(brs); end.

Program ini akan membaca satu baris teks masukan (dari standard input) dan mencetak keluaran (ke standard output) yang persis sama dengan masukan. Pada bagian awal program terdapat pernyataan (deklarasi) yang menyebutkan digunakannya suatu variabel dengan nama brs. Deklarasi ditunjukkan dengan adanya notasi var. Baris‐baris berikutnya setelah notasi var adalah tempat menuliskan deklarasi variabel‐variabel.

Variabel adalah tempat menyimpan suatu harga dalam program, dan selama berjalannya program, harga itu dapat berubah‐ubah. Setiap variabel dideklarasikan dengan menyebutkan jenis dari harga yang dapat disimpannya. brs dideklarasikan sebagai variabel berjenis string, berarti brs dapat menyimpan string yang panjangnya maksimum 255 karakter.

Badan program dinyatakan dengan perintah begin dan diakhiri dengan perintah end. (yaitu end dengan tanda titik). readln(brs) berguna untuk membaca satu baris string masukan dan hasil pembacaannya disimpan dalam variabel brs. Perintah writeln(brs) berguna untuk menuliskan isi variabel brs ke output. Dalam program setiap perintah dipisahkan dengan tanda “;” (titik koma). Sebagai kebiasaan baik, akhiri setiap baris perintah dengan tanda titik koma seperti pada contoh di atas.

1 Materi ini dikembangkan oleh Brian Marshal dan Derianto Kusuma berdasarkan Materi PJJ OSN 2007 yang disusun oleh Suryana Setiawan, M.Sc.


74/110

Untuk menguji program Anda, bukalah editor ('edit.exe' atau 'notepad.exe') lalu ketikan suatu teks sesuka anda dalam satu baris dengan panjang kurang dari 255 karakter. Simpanlah teks tersebut dalam file teks, misalnya dengan nama 'uji1.txt'. Kompilasi program tersebut dengan compiler yang anda gunakan, menjadi 'pjj0101.exe', lalu jalankan perintah pada command prompt.

pjj0101 < uji.txt

Jika program mengeluarkan keluaran yang sama dengan isi teks pada input, maka program Anda sudah berjalan dengan benar.

Sebagai latihan menggunakan penguji otomatis, tentunya jika anda memiliki akses internet, akses alamat server penguji, login sesuai dengan UserId dan Password yang telah Anda miliki, lalu submit program 'pjj0101.pas' tersebut. Jika Anda tidak memiliki akses internet dan hendak mengirimkannya melalui pos, maka simpanlah ke dalam disket atau cd (beserta latihan‐latihan lainnya, demi menghemat biaya pos Anda!) lalu kirimkan kepada pembina TOKI.

Contoh Masukan abc

Contoh Keluaran abc Jawaban Anda atas soal‐soal yang terdapat dalam materi PJJ ini dapat di‐submit langsung melalui TOKI Learning Center (http://www.toki.or.id/) dengan User ID dan password yang akan diberikan kepada Anda via E‐mail, telepon, atau media lainnya, atau melalui pos ke: Tim Pembina TOKI Jln. Kyai Gede Utama no. 12 Bandung 40132 Jangan lupa menyertakan identitas lengkap Anda (minimal: nama, alamat surat, dan asal sekolah).

http://www.toki.or.id/


75/110

While Loop Nama Program: pjj0102.PAS / C / CPP Batas Runtime: 1 detik / test‐case Batas Memori: 16 MB Nama Berkas Masukan: Standard input (keyboard) Nama Berkas Keluaran: Standard output (layar)

Melanjutkan latihan pertama gantilah kedua baris readln(brs) dan writeln(brs) dengan deretan perintah berikut ini, yang berfungsi untuk membaca beberapa baris masukan dan menulis baris yang baru dibaca, satu demi satu baris. Jangan mengganti bagian lain dari program, kecuali nama program 'pjj0102'. Simpan sebagai 'pjj0102.PAS'.

while not eof(input) do begin readln(brs); writeln(brs); end;

Dalam deretan perintah di atas terdapat struktur loop while

while <kondisi> do begin <perintah-perintah> end;

Untuk menguji program anda, buatlah file teks input 'uji2.txt' (seperti 'uji1.txt' namun dituliskan dalam beberapa baris). Setelah dikompilasi, jalankan dengan perintah

pjj0102 < uji2.txt

Jika keluaran sama dengan yang dituliskan dalam file 'uji2.txt' maka program Anda sudah berjalan dengan benar. Ujilah dengan penguji otomatis seperti dijelaskan pada 'pjj0101.PAS'.

Contoh Masukan abc 123

Contoh Keluaran abc 123


76/110

While Loop + Counter Nama Program: pjj0103.PAS / C / CPP Batas Runtime: 1 detik / test‐case Batas Memori: 16 MB Nama Berkas Masukan: Standard input (keyboard) Nama Berkas Keluaran: Standard output (layar)

Jika pada latihan sebelumnya program membaca string demi string masukan, kini program Anda harus membaca bilangan‐bilangan (satu bilangan dalam satu baris), menjumlahkan bilangan‐bilangan tersebut, dan menuliskan jumlah total bilangan‐bilangan tersebut setelah bilangan terakhir dibaca. Pembacaan dilakukan dengan cara yang sama, tetapi variabel yang digunakan haruslah variabel bertipe integer (bilangan bulat). Gantilah nama variabel brs dengan nama baru, misalnya bil. Tentu saja setiap perintah readln(brs) juga diganti dengan perintah readln(bil). Untuk menyimpan total jumlah bilangan yang dibaca, diperlukan sebuah variabel berjenis integer seperti halnya variabel bil. Mari beri nama variabel ini jml. Jadi deklarasi dituliskan

var bil: integer; jml: integer;

Karena selama pembacaan jml digunakan untuk mencatat jumlah hingga bilangan terakhir dibaca, maka di awal program variabel jml harus diberi harga awal (diinisialisasi) 0. Di dalam loop nilai jml harus ditambahkan dengan harga yang dibaca ke dalam variabel bil. Setelah loop selesai, di bagian bawah program isi jml dituliskan ke output. Untuk itu badan program dapat dituliskan sebagai

jml := 0; while not eof(input) do begin readln(bil); jml := jml + bil; end; writeln(jml);

Notasi ‘:=’ menyatakan bahwa hasil ekspresi di sebelah kanan tanda ':=' akan disimpan pada variabel yang tertulis di sebelah kiri ‘:=’. Beri nama program ini 'pjj0103' dan simpanlah dengan nama 'pjj0103.PAS'. Untuk menguji program Anda buatlah file teks input 'uji3.txt' yang setiap barisnya berisikan satu bilangan bulat (boleh negatif) yang panjangnya tidak lebih dari 4 digit.

pjj0103 < uji3.txt

Ujilah dengan penguji otomatis seperti dijelaskan pada latihan‐latihan sebelumnya.


77/110

Contoh Masukan 1 2 3

Contoh Keluaran 6


78/110

Menjumlah per Kolom Nama Program: pjj0104.PAS / C / CPP Batas Runtime: 1 detik / test‐case Batas Memori: 16 MB Nama Berkas Masukan: Standard input (keyboard) Nama Berkas Keluaran: Standard output (layar)

Jika pada latihan ketiga masukan terdiri dari baris‐baris yang setiap barisnya hanya satu bilangan bulat, pada latihan ini Anda mencoba untuk membaca baris‐baris yang per barisnya berisi 3 bilangan bulat dan masing‐masing dipisahkan satu spasi. Lalu Anda diminta menjumlahkan bilangan‐bilangan pada setiap kolom dengan variabel‐variabel penjumlah yang berbeda. Kolom pertama dengan penjumlah pertama, kolom kedua dengan penjumlah kedua, dan kolom ketiga dengan penjumlah ketiga. Ketiga hasil penjumlahan tersebut dicetak dalam satu baris yang sama yang dipisahkan dengan satu spasi.

Untuk itu Anda perlu menggunakan 3 variabel pembaca dan 3 variabel penjumlah. Kita namai ketiga variabel pembaca itu bil1, bil2, dan bil3 sementara ketiga variabel penjumlah diberi nama jml1, jml2 dan jml3. Dalam Pascal, deklarasi beberapa variabel sejenis dapat dituliskan dalam satu baris seperti

var bil1, bil2, bil3, jml1, jml2, jml3: integer;

Namun, demi memudahkan pembacaan program kembali, sebaiknya variabel‐variabel yang memiliki fungsi yang berbeda dideklarasi secara terpisah:

var bil1, bil2, bil3: integer; jml1, jml2, jml3: integer;

Ketiga bilangan dalam satu baris dapat sekaligus dibaca sesuai dengan urutannya serta spasinya. Perintah

readln(bil1, bil2, bil3);

akan membaca ketiga bilangan sekaligus dari satu baris masukan. Penanda batas antar bilangan saat pembacaan dalam Pascal adalah tanda spasi.

Penjumlahaan masing‐masing bilangan tersebut tentu saja harus dilakukan terhadap pejumlah masing‐masing

jml1 := jml1 + bil1; jml2 := jml2 + bil2; jml3 := jml3 + bil3;


79/110

Pencetakan jml1, jml2, dan jml3 dalam satu baris yang sama (dengan pemisah spasi yang harus dituliskan juga karena kalau tidak maka bilangan‐bilangan dituliskan bersambungan!) dapat dilakukan dengan perintah

writeln(jml1,' ', jml2,' ', jml3);

Lakukan juga pengujian seperti pada latihan‐latihan sebelumnya.

Contoh Masukan 1 2 3 2 3 4

Contoh Keluaran 3 5 7


80/110

Menjumlah dalam Satu Baris Nama Program: pjj0105.PAS / C / CPP Batas Runtime: 1 detik / test‐case Batas Memori: 16 MB Nama Berkas Masukan: Standard input (keyboard) Nama Berkas Keluaran: Standard output (layar)

Jika pada latihan ketiga bilangan‐bilangan dituliskan pada masing‐masing baris, maka kali ini bilangan‐bilangan dituliskan pada satu baris yang sama. Untuk membantu program Anda, bilangan pada baris pertama menunjukkan berapa banyak bilangan yang akan Anda jumlahkan. Jadi, program Anda harus membaca bilangan ini di awal, kemudian membaca bilangan‐bilangan sebanyak nilai bilangan tadi.

Untuk perulangan (loop) dengan jumlah yang pasti/tertentu dalam Pascal, Anda dapat menggunakan struktur loop for berikut

for <iterator> := <harga-awal> to <harga-akhir> do begin <perintah-perintah> end;

<iterator> adalah variabel yang akan berubah harganya setiap loop dilakukan, dimulai dari harga <harga‐awal>. Setiap perulangan, harga variabel tersebut bertambah satu. Perulangan demi perulangan dilakukan hingga variabel berharga <harga‐akhir>. Tentu saja <harga‐awal> harus lebih kecil atau sama dengan <harga‐akhir>, karena kalau tidak maka program akan terus‐menerus melakukan loop. Kita perlu dua variabel baru, untuk mencatat jumlah bilangan yang akan dibaca, misalnya jbil dan untuk <iterator> misalnya i.

Jadi pada bagian deklarasi ditambah dengan pernyataan

jbil, i: integer;

Dan bagian badan program diganti dengan

jml := 0; read(jbil); for i := 1 to jbil do begin read(bil); jml := jml + bil; end; writeln(jml);


81/110

Catatan: perintah readln diganti dengan perintah read agar pembacaan berikutnya tetap membaca pada baris yang sama.

Lakukan juga pengujian seperti pada latihan‐latihan sebelumnya. Namai program tersebut dengan nama pjj0105 dan simpanlah dengan nama 'pjj0105.PAS'.

Contoh Masukan 5 1 2 3 4 5

Contoh Keluaran 15


82/110

If Then Nama Program: pjj0106.PAS / C / CPP Batas Runtime: 1 detik / test‐case Batas Memori: 16 MB Nama Berkas Masukan: Standard input (keyboard) Nama Berkas Keluaran: Standard output (layar)

Program Anda harus dapat membaca setiap bilangan bulat pada masukan dan memeriksa apakah bilangan tersebut positif. Jika positif maka bilangan itu dituliskan ke output, sementara jika bilangan negatif atau nol tidak melakukan apa‐apa. Program mirip dengan pada latihan ketiga, tetapi keluaran dicetak di dalam loop sementara pencetakan di akhir ditiadakan. Karena bilangan positif saja yang dicetak maka diperlukan suatu struktur if‐then berikut

if <kondisi> then begin <perintah-perintah> end;

<kondisi> yang diperiksa setelah notasi 'if' adalah 'apakah bil berharga positif'. <perintah‐perintah> adalah yang akan dilakukan jika kondisi bernilai benar. Jadi Anda menambahkan

if bil > 0 then begin writeln(bil); end;

di dalam struktur loop while di atas (tentunya sebelum pembacaan berikutnya).

Namai program tsb dengan nama pjj0106 dan simpanlah dengan nama pjj0106.PAS.

Contoh Masukan 1 4

Contoh Keluaran 1 4

Contoh Masukan 2 0

Contoh Keluaran 2


83/110

Contoh Masukan 3 -1

Contoh Keluaran 3


84/110

If Then, Multi Condition Nama Program: pjj0107.PAS / C / CPP Batas Runtime: 1 detik / test‐case Batas Memori: 16 MB Nama Berkas Masukan: Standard input (keyboard) Nama Berkas Keluaran: Standard output (layar)

Program Anda harus membaca setiap bilangan bulat masukan dan memeriksa apakah bilangan tersebut positif dan genap. Jika positif dan genap maka bilangan itu dituliskan ke output, dan jika tidak maka tidak melakukan apa‐apa. Jadi Anda dapat langsung mengubah program untuk latihan ke enam dengan menambahkan kondisi kedua (apakah bilangan tersebut genap) yang perlu diperiksa. Jika <kondisi> berisi dua kondisi yang keduanya harus benar maka Anda menuliskan kedua kondisi tersebut berurutan diperantarai oleh notasi 'and' sebagai berikut

if (<kondisi pertama>) and (<kondisi kedua>) then begin <perintah-perintah> end;

Tentu, <kondisi pertama> adalah 'apakah bil positif' dan <kondisi kedua> adalah 'apakah bil bilangan genap', yang dapat diperiksa dengan memeriksa harga modulus (sisa pembagian) dari bil jika bil dibagi dengan 2. Dalam Pascal, dituliskan bil mod 2. Jika modulus itu berharga 0, bil habis dibagi (tanpa sisa), sementara jika bukan 0, maka bil tidak habis terbagi (ada sisa). Bilangan genap selalu habis dibagi 2 sehingga modulusnya harus 0. Jadi <kondisi kedua> memeriksa apakah 'bil mod 2 = 0' dan pemeriksaan kedua kondisi tersebut dalam struktur if‐then menjadi

if (bil > 0) and (bil mod 2 = 0) then begin writeln(bil); end;

Apakah posisi kedua kondisi bisa ditukar? Tentu bisa karena 'and' sebagai operator logika tidak mementingkan urutan (kecuali pada kasus‐kasus tertentu, yang akan dijelaskan kemudian).

Beri nama program pjj0107 dan simpanlah dengan nama pjj0107.PAS.

Contoh Masukan 1 12


85/110

Contoh Keluaran 1 12

Contoh Masukan 2 11

Contoh Keluaran 2


86/110

If Then Else Nama Program: pjj0108.PAS / C / CPP Batas Runtime: 1 detik / test‐case Batas Memori: 16 MB Nama Berkas Masukan: Standard input (keyboard) Nama Berkas Keluaran: Standard output (layar)

Program Anda harus dapat membaca setiap bilangan bulat masukan dan memeriksa apakah bilangan tersebut bilangan positif, negatif atau nol. Jika merupakan bilangan positif maka program akan menuliskan string 'positif', jika bilangan negatif maka program akan menuliskan 'negatif' dan jika bilangan nol maka proram akan menuliskan 'nol'. Untuk itu Anda perlu mempelajari struktur if‐then‐else yang sedikit berbeda dari struktur if‐then sebelumnya. Perhatikan struktur if‐then berikut

if <kondisi> then begin <perintah-perintah> end; <perintah-perintah selanjutnya>

Jika pada struktur if‐then saat kondisi yang diperiksa tidak benar maka komputer hanya melompati <perintah‐perintah> untuk langsung menjalankan <perintah‐perintah selanjutnya>. Sementara pada struktur if‐then‐else sebagai berikut.

if <kondisi> then begin <perintah-perintah 1> end else begin <perintah-perintah 2> end; <perintah-perintah selanjutnya>

Jika <kondisi> benar maka komputer akan menjalankan <perintah‐perintah 1> lalu lompat ke <perintah‐perintah selanjutnya> dan jika <kondisi> tidak benar maka komputer akan menjalankan <perintah‐perintah 2> lalu ke <perintah‐perintah selanjutnya>.

Jadi dalam latihan ini jika kondisi yang diperiksa adalah bil > 0 maka <perintah‐perintah 1> adalah mencetak string 'positif'. Sementara itu karena kondisi tidak benar masih harus dibedakan antara negatif atau nol untuk mencetak 'negatif' atau 'nol', maka di dalam else‐begin‐end dibuat kembali pemeriksaan if‐then‐else yang mana kondisi yang diperiksa adalah apakah bil = 0 sebagai berikut.


87/110

if bil > 0 then begin writeln('positif'); end else begin if bil = 0 then begin writeln('nol'); end else begin writeln('negatif'); end; end;

Adanya satu struktur di dalam struktur yang sama dikenal dengan istilah 'nested structure' (struktur bersarang), dalam hal ini adalah nested if‐then‐else. Dalam Pascal seberapa dalam struktur nested tidak dibatasi, namun akan menyulitkan kita sendiri dalam membaca program itu. Untuk mempermudah pembacaan maka biasanya struktur yang berada lebih dalam dituliskan dengan indentasi seperti di atas. Namun compiler Pascal akan mengabaikan identasi tersebut, jadi indentasi sepenuhnya untuk kerapihan penulisan program demi kemudahan membacanya kembali.

Beri nama program tersebut pjj0108 dan simpanlah dengan nama 'pjj0108.PAS'.

Contoh Masukan 1 2

Contoh Keluaran 1 positif

Contoh Masukan 2 0

Contoh Keluaran 2 nol

Contoh Masukan 3 -2

Contoh Keluaran 3 negatif


88/110

Case Nama Program: pjj0109.PAS / C / CPP Batas Runtime: 1 detik / test‐case Batas Memori: 16 MB Nama Berkas Masukan: Standard input (keyboard) Nama Berkas Keluaran: Standard output (layar)

Program untuk latihan ini harus membaca setiap bilangan bulat masukan yang dipastikan berharga dari antara 1 sampai dengan 30000. Program akan mengenali apakah bilangan itu merupakan satuan (1 s.d. 9) atau puluhan (10 s.d. 99) atau ratusan (100 s.d. 999) atau ribuan (1000 s.d. 9999) atau puluh ribuan (10000 s.d. 30000). Jika satuan maka program akan memberikan keluaran string 'satuan', jika puluhan maka akan memberikan keluaran 'puluhan', dan seterusnya.

Anda dapat menggunakan struktur nested if‐then‐else seperti sebelumnya sbb.

if bil < 10 then begin writeln('satuan'); end else begin if bil < 100 then begin writeln('puluhan'); end else begin if bil < 1000 then begin writeln('ratusan'); end else begin if bil < 10000 then begin writeln('ribuan'); end else begin writeln('puluhribuan'); end; end; end; end;

Namun, karena penulisan nested structure dalam program yang terlalu banyak nest‐nya tampak kurang rapi maka kita dapat menggunakan struktur alternatif yang disebut struktur case sbb.


89/110

case <variabel> of <harga atau harga-harga 1> : begin <perintah-perintah 1> end; <harga atau harga-harga 2> : begin <perintah-perintah 2> end; dan seterusnya... end;

Dengan struktur ini maka <harga atau harga‐harga> dapat berupa satu harga tunggal atau suatu jangkauan harga atau beberapa harga. Jangkauan harga, misalnya 'dari 10 s.d. 99' dituliskan '10..99' (kedua batas bilangan dengan dua titik di antaranya). Beberapa harga dituliskan dengan tanda koma misalnya '10, 100, 1000'. Jika ada beberapa <harga atau harga‐harga> yang jangkauan bilangannya saling tumpang tindih, program akan menjalankan <perintah‐perintah> yang berada pada urutan <harga atau harga‐harga> yang lebih awal.

Jika jika menggunakan struktur case ini pemeriksaan menjadi lebih kompak dan sederhana sbb.

case bil of 1..9: begin writeln('satuan'); end; 10..99: begin writeln('puluhan'); end; 100..999: begin writeln('ratusan'); end; 1000..9999: begin writeln('ribuan'); end; 10000..30000: begin writeln('puluhribuan'); end; end;

Namai program tersebut dengan nama pjj0109 dan simpanlah dengan nama 'pjj0109.PAS'.

Contoh Masukan 1 4

Contoh Keluaran 1 satuan

Contoh Masukan 2 12345

Contoh Keluaran 2 puluhribuan


90/110

Procedure Nama Program: pjj0110.PAS / C / CPP Batas Runtime: 1 detik / test‐case Batas Memori: 16 MB Nama Berkas Masukan: Standard input (keyboard) Nama Berkas Keluaran: Standard output (layar)

Program ini harus membaca beberapa bilangan bulat, satu bilangan per baris, dan menuliskan keluaran 'satuan' atau 'puluhan' atau 'ratusan' atau 'ribuan' atau 'puluhribuan' untuk setiap bilangan yang dibaca.

Berbeda dengan latihan sebelumnya, pada latihan ini Anda membaca banyak bilangan bulat, tidak hanya satu.

Pada latihan ini akan diperkenalkan konsep procedure. Sebuah procedure (prosedur) adalah deretan perintah‐perintah yang dapat dieksekusi dengan cara memanggil namanya. Bentuk umum deklarasi prosedur adalah:

procedure <nama>(<daftar parameter>); <daftar deklarasi> begin <perintah-perintah> end; Contohnya, kita dapat membuat sebuah procedure bernama 'TulisJawaban': procedure TulisJawaban(x: integer); begin case x of 1..9: begin writeln('satuan'); end; 10..99: begin writeln('puluhan'); end; 100..999: begin writeln('ratusan'); end; 1000..9999: begin writeln('ribuan'); end; 10000..30000: begin writeln('puluhribuan'); end; end; end;

Setelah itu procedure TulisJawaban ini dapat kita gunakan untuk memecahkan masalah awal:

while not eof(input) do begin readln(bil); TulisJawaban(bil); end;

Untuk setiap bil yang dibaca, nilai variabel bil akan "dimasukkan" ke dalam variabel x di dalam procedure TulisJawaban. Lalu prosedur tersebut akan mengeluarkan 'satuan', 'puluhan', 'ratusan', 'ribuan', atau 'puluhribuan'


91/110

tergantung pada nilai x. Secara keseluruhan, program ini akan mengeluarkan jenis bilangan untuk setiap bilangan yang dibaca.

Perhatikan kesamaan penulisan readln(bil); dan TulisJawaban(bil);. Sesungguhnya, readln dan writeln juga adalah prosedur, tetapi prosedur‐prosedur tersebut sudah dibuatkan untuk kita, sehingga kita tinggal menggunakannya saja.

Namai program tersebut dengan nama pjj0110 dan simpanlah dengan nama pjj0110.PAS'.


Contoh Keluaran satuan puluhan ratusan


92/110

Function Nama Program: pjj0111.PAS / C / CPP Batas Runtime: 1 detik / test‐case Batas Memori: 16 MB Nama Berkas Masukan: Standard input (keyboard) Nama Berkas Keluaran: Standard output (layar)

Program untuk latihan ini harus membaca sebuah bilangan N dan mengeluarkan nilai N! (N faktorial). Jika N berada dalam jangkauan 0 hingga 10, keluarkan nilai N!. Jika N negatif atau lebih besar dari 10, keluarkan 'ditolak'. Catatan: 0! = 1.

Kali ini akan diperkenalkan konsep function atau fungsi. Struktur fungsi mirip dengan prosedur, tetapi fungsi dapat mengembalikan suatu nilai untuk si pemanggil fungsi tersebut. Struktur fungsi secara umum adalah seperti berikut ini:

function <nama>(<daftar parameter>): <return type>; <daftar deklarasi> begin <perintah-perintah> end;

Contohnya, untuk menyelesaikan latihan ini, kita dapat membuat fungsi seperti berikut ini:

function Faktorial(n: integer): longint; var i: integer; bil: longint; begin bil := 1; for i := 1 to n do bil := bil * i; Faktorial := bil; end;

Dan kode program yang memanggilnya sebagai berikut:

var bil: integer; begin readln(bil); if (n >= 0) and (n <= 10) then writeln(Faktorial(bil)) else writeln('ditolak'); end.


93/110

Program ini akan membaca sebuah integer dari input dan menyimpannya di dalam variabel bil. Setelah itu, jika bil ada di dalam jangkauan 1 hingga 10, Faktorial dari bil akan dituliskan ke layar. Sudah dikatakan bahwa sebuah fungsi akan mengembalikan suatu nilai. Karena <return type> adalah integer, maka nilai yang dikembalikan oleh fungsi Faktorial bertipe integer.

Ketika fungsi Faktorial dipanggil oleh kode di atas, nilai variabel bil "dimasukkan" ke dalam variabel n di dalam fungsi Faktorial. Setelah itu, fungsi Faktorial akan menghitung nilai faktorial dari n dengan menggunakan sebuah variabel pembantu bernama bil lagi.

Namun, sekarang ada dua variabel bil, satu di dalam fungsi Faktorial dan satu di dalam program utama. Tetapi kita tidak perlu kuatir, karena meskipun memiliki nama yang sama, kedua variabel ini dianggap sebagai dua variabel yang berbeda. Variabel yang dideklarasikan di program utama disebut "global variable", dan yang dideklarasikan di dalam fungsi / prosedur disebut "local variable". Lebih dari itu, beberapa fungsi dan prosedur yang berbeda bisa memiliki local variable‐nya sendiri‐sendiri dan bisa memiliki nama yang sama, tetapi dua variabel akan dianggap berbeda jika dideklarasikan pada scope (tempat) yang berbeda.

Perhatikan juga perintah Faktorial := bil; yang berada di akhir fungsi Faktorial. Perintah ini menyatakan bahwa nilai variabel bil menjadi nilai yang akan dikembalikan oleh fungsi Faktorial setelah fungsi tersebut selesai.

Jadi, misalnya perintah writeln(Faktorial(4)); akan mengeluarkan hasil yang sama dengan perintah writeln(24);. Secara umum, fungsi biasanya digunakan untuk membuat program lebih terstruktur, atau untuk menghindari menuliskan kode berulang kali.

Kita juga dapat membuat sebuah fungsi lain yang bernama Valid sebagai berikut:

function Valid(n: integer): boolean; begin Valid := (n >= 0) and (n <= 10); end;

dan digunakan di program utama sebagai berikut:

var bil: integer; begin readln(bil); if (Valid(bil)) then writeln(Faktorial(bil)) else writeln('ditolak'); end.


94/110

Jadi fungsi Valid akan mengembalikan nilai true atau false, tergantung nilai n (yang diperoleh dari nilai bil). Program ini akan mengeluarkan keluaran yang sama dengan program sebelumnya.

Ada satu konsep lagi yang akan dikenalkan, yaitu konsep fungsi rekursif (ada juga prosedur rekursif). Sebuah fungsi rekursif adalah fungsi yang memanggil dirinya sendiri, dan struktur ini sering dipakai dan memiliki banyak kegunaan. Contoh fungsi rekursif adalah sebagai berikut:

function Faktorial(n: integer): longint; begin if (n = 0) Faktorial := 1 else Faktorial := n * Faktorial (n - 1); end;

Tentu Faktorial(0) akan mengembalikan hasil 1, seperti yang diharapkan. Bagaimana jika Faktorial(1) dipanggil? Fungsi Faktorial akan melakukan perintah Faktorial := 1 * Faktorial(0);, sehingga pada akhirnya fungsi ini akan mengembalikan hasil 1. Jika Faktorial(n) dipanggil, fungsi ini akan melakukan perintah Faktorial := n * Faktorial(n ‐ 1) dan setelah itu, fungsi ini akan dipanggil lagi dengan parameter n yang lebih kecil daripada sebelumnya. Fungsi Faktorial dipanggil terus‐menerus oleh dirinya sendiri sampai nilai n menjadi 0 dan fungsi ini berhenti memanggil dirinya sendiri. Pada akhirnya, nilai yang dikeluarkan oleh Faktorial(n) adalah n * (n ‐ 1) * (n ‐ 2) * ... * 1, yang merupakan hasil yang benar.


Contoh Masukan 1 4

Contoh Keluaran 1 24

Contoh Masukan 2 11

Contoh Keluaran 2 ditolak


95/110

Var Parameter Nama Program: pjj0112.PAS / C / CPP Batas Runtime: 1 detik / test‐case Batas Memori: 16 MB Nama Berkas Masukan: Standard input (keyboard) Nama Berkas Keluaran: Standard output (layar)

Program untuk latihan ini harus membaca dua buah bilangan bulat dalam satu baris, A dan B, lalu mengeluarkan kedua bilangan itu tetapi dengan posisi ditukar, menjadi B dan A, dalam satu baris.

Soal ini sebetulnya dapat dipecahkan dengan program yang sangat pendek seperti ini:

var a, b: integer; begin readln(a, b); writeln(b, ' ', a); end.

Namun, kali ini cobalah membuat sebuah prosedur Swap yang memiliki dua buah parameter integer, yang akan menukarkan nilai a dan b, seperti berikut ini:

var a, b: integer; // menukar nilai a dengan b procedure Swap(a, b: integer); var temp: integer; begin temp := a; a := b; b := temp; end; // program utama begin readln(a, b); Swap(a, b); writeln(a, ' ', b); end.

Coba ujilah program itu dengan sebuah file input yang berisi dua buah bilangan bulat. Apakah program ini mengeluarkan hasil yang benar? Ternyata program ini tidak berjalan dengan benar. Mengapa demikian? Dalam prosedur Swap di atas, parameter a dan b sebetulnya adalah "local variable" yang dideklarasikan di dalam prosedur Swap, sehingga a dan b ini sama sekali bukan variabel a dan b


96/110

yang dideklarasikan di awal program. Dengan demikian, menukarkan nilai a dan b yang berada di dalam prosedur Swap tidak akan berpengaruh apa‐apa.

Oleh karena itu, kita harus mengubah sedikit prosedur Swap kita menjadi:

procedure Swap(var a: integer; var b: integer); var temp: integer; begin temp := a; a := b; b := temp; end;

atau

procedure Swap(var a, b: integer); var temp: integer; begin temp := a; a := b; b := temp; end;

"Modifier" var menunjukkan bahwa parameter a dan b bukanlah "local variable" di dalam prosedur tersebut, tetapi adalah referensi ke sebuah variabel yang nyata di luar prosedur tersebut. Karena Swap dipanggil dari program utama dengan parameter a dan b pada program utama, maka variabel‐variabel global inilah yang direferensi oleh parameter prosedur Swap. Sehingga, jika nilai a dan b ditukarkan di dalam prosedur, sebetulnya nilai yang ditukarkan adalah nilai variabel global a dan variabel global b.

Untuk lebih jelasnya, meskipun kode prosedur Swap kita ganti menjadi:

procedure Swap(var c, d: integer); var temp: integer; begin temp := c; c := d; c := temp; end;

program tetap berjalan dengan benar karena sekarang c mengacu pada variabel a global, dan d mengacu pada variabel b global. Sebuah prosedur atau fungsi dapat memiliki beberapa variabel "dengan modifier var" dan beberapa variabel "tanpa modifier var" sekaligus.



97/110

Contoh Masukan 4 5

Contoh Keluaran 5 4


98/110

Break, Continue, Exit Nama Program: pjj0113.PAS / C / CPP Batas Runtime: 1 detik / test‐case Batas Memori: 16 MB Nama Berkas Masukan: Standard input (keyboard) Nama Berkas Keluaran: Standard output (layar)

Pada latihan ini, program Anda harus membaca sebuah bilangan bulat N (1 ≤ N ≤ 100), dan harus mengeluarkan bilangan‐bilangan dari 1 sampai dengan N secara berurutan, satu per baris, dengan aturan sebagai berikut:

• Lompati bilangan kelipatan 10 • Jika program akan mengeluarkan bilangan 93, jangan keluarkan 93, tetapi

keluarkan 'ERROR' dan jangan keluarkan apa‐apa lagi.

Aturan tersebut kesannya dibuat‐buat, karena masalah ini hanya sebagai contoh untuk mengilustrasikan kegunaan break, continue, dan exit.

Untuk menyelesaikan masalah di atas, Anda dapat membuat program seperti ini:

var n: integer; i: integer; error: boolean; begin readln(n); error := false; for i := 1 to n do begin if (i = 93) then error := true; if (not error) and (i mod 10 <> 0) then writeln(i); end; if (error) then writeln('ERROR'); end.

Pada program di atas, variabel boolean error hanya berfungsi sebagai variabel pembantu. Pada mulanya, error diinisialisasi dengan false. Setelah itu, di dalam loop for, jika i bukan kelipatan 10, i dituliskan ke layar. Namun jika i bernilai 93, maka variabel error diberi nilai true, sehingga sejak saat itu tidak ada lagi yang ditulis ke layar kecuali 'ERROR' di akhir program.

Ada cara lain menuliskan program tersebut, yaitu seperti berikut:


99/110

var n: integer; i: integer; begin readln(n); for i := 1 to n do begin if (i = 93) then begin writeln('ERROR'); break; end; if (i mod 10 = 0) then continue; writeln(i); end; end.

Pada program ini, break berfungsi untuk keluar secara paksa dari loop for. Jika i = 93, 'ERROR' dituliskan ke layar dan loop for dihentikan secara paksa, dan program berlanjut ke perintah berikutnya setelah loop for. Karena tidak ada perintah lagi, program selesai. Perintah break sebetulnya juga dapat dipakai untuk menghentikan loop while secara paksa.

Perintah continue berfungsi untuk menghentikan aliran program dan kembali ke baris for i := 1 to n do dengan nilai i selanjutnya. Jadi jika i adalah kelipatan 10, perintah writeln(i) tidak dijalankan dan loop for dilanjutkan dengan nilai i berikutnya.

Perintah break di atas juga dapat diganti dengan perintah exit. Perintah ini akan menghentikan sebuah prosedur, fungsi, atau program secara paksa. Karena pada kasus di atas aliran program berada di program utama, perintah exit akan menghentikan program seketika.


Contoh Masukan 1 12

Contoh Keluaran 1 1 2 3 4 5 6 7 8 9 11 12


100/110

Contoh Masukan 2 94

Contoh Keluaran 2 1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 21 22 23

24 25 26 27 28 29 31 32 33 34 35 36 37 38 39 41 42 43 44 45 46

47 48 49 51 52 53 54 55 56 57 58 59 61 62 63 64 65 66 67 68 69

71 72 73 74 75 76 77 78 79 81 82 83 84 85 86 87 88 89 91 92 ERROR


101/110

Operasi String Nama Program: pjj0114.PAS / C / CPP Batas Runtime: 1 detik / test‐case Batas Memori: 16 MB Nama Berkas Masukan: Standard input (keyboard) Nama Berkas Keluaran: Standard output (layar)

Pada latihan ini, program Anda harus membaca sebuah empat buah string yang kita beri nama S1, S2, S3, dan S4. Misalnya program Anda mendapat input seperti ini:

abcdehalofghi bcd halo semua

Dijamin bahwa string S1 mengandung sebuah string S2 di dalamnya. Buang string S2 yang ditemukan di string S1 (dijamin ada, dan hanya satu). Kemudian sisipkan string S4 pada posisi setelah string S3 yang ditemukan di string S1 (dijamin ada, dan hanya satu). Jadi pada contoh di atas, abcdehalofghi diubah menjadi aehalofghi, lalu menjadi aehalosemuafghi. Keluarkan string hasil akhir, yang pada contoh ini adalah aehalosemuafghi.

Untuk menyelesaikan masalah tersebut, kita perlu mengenal berbagai fungsi‐fungsi dan prosedur‐prosedur penanganan string yang disediakan oleh library Pascal yang bisa kita gunakan.

(Dapat dilihat di http://community.freepascal.org:10000/docs‐html/rtl/system/stringfunctions.html)

Fungsi‐fungsi dan prosedur‐prosedur yang akan kita gunakan adalah:

function length(s: string): integer; function pos(substr: string; s: string): integer; procedure delete(var s: string; index: integer; count: integer); procedure insert(var source: string; s: string; index: integer);

Fungsi length akan mengembalikan panjang dari s.

Jika string s mengandung string substr, fungsi pos akan mengembalikan index pertama dari kemunculan pertama substr di dalam s (karakter pertama diberi index 1). Jika tidak ada, fungsi ini akan mengembalikan 0.

http://community.freepascal.org:10000/docs-html/rtl/system/stringfunctions.html

http://community.freepascal.org:10000/docs-html/rtl/system/stringfunctions.html


102/110

Prosedur delete akan membuang sebanyak count karakter pada string s, dimulai dengan index ke‐index. Misalnya, jika s pada mulanya adalah 'Halo', delete(s, 1, 2) akan mengubah isi s menjadi 'lo'.

Prosedur insert akan memasukkan string s ke dalam string source, dimulai pada posisi index ke‐index.

Untuk menyelesaikan masalah awal, kita dapat membuat program sebagai berikut:

var S1, S2, S3, S4: string; begin readln(S1); readln(S2); readln(S3); readln(S4); delete(S1, pos(S2, S1), length(S2)); insert(S4, S1, pos(S3, S1) + length(S3)); writeln(S1); end.

Pada program di atas, S2 di dalam S1 akan dibuang dari S1, dan selanjutnya S4 akan dimasukkan ke dalam S1 tepat pada posisi pos(S3, S1) + length(S3), yaitu posisi karakter pertama yang tidak termasuk S3, setelah kemunculan seluruh karakter S3 di dalam S1.


Contoh Masukan abcdehalofghi bcd halo semua

Contoh Keluaran aehalosemuafghi

Masih banyak fungsi‐fungsi dan prosedur‐prosedur lain yang mungkin berguna, yang bisa dipelajari di

http://community.freepascal.org:10000/docs‐html/rtl/system/index.html

Berikut ini adalah ringkasan dari beberapa fungsi yang mungkin berguna:

http://community.freepascal.org:10000/docs-html/rtl/system/index.html


103/110

procedure str(x: integer; var s: string);

Prosedur ini akan mengubah nilai integer x menjadi string, lalu dimasukkan ke dalam variabel s. Misalnya, jika x bernilai 10, s akan menjadi bernilai '10'.

function lowerCase(s: string): string;

Fungsi ini akan menghasilkan sebuah string seperti s tetapi semua karakternya diubah ke huruf kecil.

function upCase(s: string): string;

Fungsi ini akan menghasilkan sebuah string seperti s tetapi semua karakternya diubah ke huruf besar.

function chr(b: byte): char;

Fungsi ini akan mengembalikan sebuah karakter yang memiliki kode ASCII b. Misalnya chr(65) akan mengembalikan "A".

function ord(c: char): longint;

Fungsi ini akan mengembalikan nilai bilangan bulat dari sebuah tipe ordinal. Biasanya fungsi ini digunakan untuk menentukan kode ASCII dari karakter c. Misalnya, ord("A") akan mengembalikan 65.

Kombinasi chr dan ord dapat digunakan untuk mengubah sebuah karakter dari huruf kecil menjadi huruf besar, atau sebaliknya. Misalnya, chr(ord("x") + (ord("A") ‐ ord("a"))) akan menghasilkan "X".

function abs(l: longint): longint;

Fungsi ini akan mengembalikan nilai absolut dari l. Misalnya, abs(‐3) akan mengembalikan 3, dan abs(3) juga mengembalikan 3.

procedure dec(var x: integer); procedure dec(var x: integer; decrement: integer);

Prosedur ini akan mengurangi nilai x dengan 1, atau dengan nilai decrement jika diberikan.

procedure inc(var x: integer); procedure inc(var x: integer; increment: integer);


104/110

Prosedur ini akan menambah nilai x dengan 1, atau dengan nilai increment jika diberikan.

function sqr(x: longint): longint; function sqr(x: real): real;

Fungsi ini akan mengembalikan kuadrat dari x.

function sqrt(x: real): real;

Fungsi ini akan mengembalikan akar kuadrat dari x.

function trunc(x: real): integer;

Fungsi ini akan mengembalikan bagian bilangan bulat dari sebuah bilangan real x. Misalnya, trunc(3.456) akan menghasilkan 3.

function round(x: real): integer;

Fungsi ini akan menghasilkan pembulatan dari sebuah bilangan real x. Pada Pascal, aturan pembulatan untuk 0.5 adalah ke arah bilangan genap. Jadi, round(1.5) akan menghasilkan 2, tetapi round(2.5) juga akan menghasilkan 2.

function pi: real;

Fungsi ini mengembalikan nilai pi (3.14159...).


105/110

Manhattan Distance Nama Program: pjj0115.PAS / C / CPP Batas Runtime: 1 detik / test‐case Batas Memori: 16 MB Nama Berkas Masukan: Standard input (keyboard) Nama Berkas Keluaran: Standard output (layar)

Manhattan distance adalah jarak dari suatu titik menuju titik lainnya di bidang kartesian dengan menyusuri bagian vertikal dan horizontal, tanpa pernah kembali. Secara sederhana sama dengan jumlah dari selisih absis dan selisih ordinat (distance = |x1‐x2| + |y1‐y2|). Pada soal ini, Anda akan membaca masukan yang berisi empat buah bilangan bulat yang merupakan koordinat dari dua buah titik, x1 y1 x2 y2 (semuanya berada dalam jangkauan ‐1000000000..1000000000) secara berturutan dalam 1 baris. Hitung berapa manhattan distance untuk kedua buah titik tersebut.

Format Masukan

Sebuah baris berisi empat buah bilangan bulat x1 y1 x2 y2.

Format Keluaran

Sebuah bilangan bulat yang merupakan manhattan distance untuk kedua buah titik yang diberikan.

Contoh Masukan -1 -1 1 1

Contoh Keluaran 4


106/110

Floor and Ceiling Nama Program: pjj0116.PAS / C / CPP Batas Runtime: 1 detik / test‐case Batas Memori: 16 MB Nama Berkas Masukan: Standard input (keyboard) Nama Berkas Keluaran: Standard output (layar)

Nilai floor dari sebuah bilangan adalah bilangan bulat terbesar yang masih lebih kecil atau sama dengan bilangan tersebut, sebaliknya nilai ceiling dari sebuah bilangan adalah bilangan bulat terkecil yang masih lebih besar atau sama dengan bilangan tersebut.

Format Masukan

Sebuah bilangan real (dalam jangkauan ‐1000000 .. 1000000).

Format Keluaran

Dua buah bilangan bulat berturutan dalam satu baris dipisahkan oleh spasi, yakni nilai floornya dan nilai ceilingnya.

Contoh Masukan -256.652

Contoh Keluaran -257 -256


107/110

Dua Pangkat Nama Program: pjj0117.PAS / C / CPP Batas Runtime: 1 detik / test‐case Batas Memori: 16 MB Nama Berkas Masukan: Standard input (keyboard) Nama Berkas Keluaran: Standard output (layar)

Bilangan "dua pangkat" dalam soal ini adalah bilangan bulat yang dapat dituliskan dalam bentuk 2^K dimana K adalah sebuah bilangan bulat.

Format Masukan

Sebuah bilangan bulat dalam jangkauan 1 sampai 2^20.

Format Keluaran

"TRUE" jika bilangan yang diberikan adalah bilangan "dua pangkat", dan "FALSE" jika sebaliknya.

Contoh Masukan 1 8

Contoh Keluaran 1 TRUE

Contoh Masukan 2 6

Contoh Keluaran 2 FALSE


108/110

POLA 1 Nama Program: pjj0118.PAS / C / CPP Batas Runtime: 1 detik / test‐case Batas Memori: 16 MB Nama Berkas Masukan: Standard input (keyboard) Nama Berkas Keluaran: Standard output (layar)

Perhatikan contoh masukan dan keluaran yang diberikan, temukan polanya, lalu buatlah programnya.

Format Masukan

Sebuah bilangan bulat N (0<N<10)

Format Keluaran

Pola berukuran N, seperti pada contoh keluaran.

Contoh Masukan 5

Contoh Keluaran * ** *** **** *****


109/110



Format Masukan

Sebuah bilangan bulat N (0<N<10)

Format Keluaran


Contoh Masukan 1 5

Contoh Keluaran 1 0 12 345 6789 01234

Contoh Masukan 2 7

Contoh Keluaran 2 0 12 345 6789 01234 567890 1234567


110/110



Format Masukan

Dua buah bilangan bulat N dan K (0 < N < 100 , 1 < K < 10).

Format Keluaran



Contoh Keluaran 1 1 2 * 4 5 * 7 8 * 10 11


Contoh Keluaran 2 1 * 3 * 5 * 7 * 9 * 11


Contoh Keluaran 3 1 2 3 4 * 6 7 8 9 * 11

materi pembinaan pra olimpiade sains · pdf filemampu membentuk model aritmatika/matematika...

Documents