TEKS : Pengenalan Sistem Online Judge

10/3/13

TEKS : Pengenalan Sistem Online Judge

TEKS : Pengenalan Sistem Online Judge Pada masa lalu, kompetisi informatika biasanya menggunakan tenaga manusia untuk memeriksa jawaban para peserta. Program setiap peserta dijalankan untuk setiap test case, lalu keluarannya dicek kebenarannya. Hal ini sangat memakan waktu dan tidak efisien, sehingga digunakan sistem "online judge" untuk mengautomatisasi proses tersebut. Sebelum berbicara tentang bagaimana online judge bekerja, marilah melihat "header" soal yang sudah sering kita lihat, seperti di bawah ini: Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:

nama.PAS / C / CPP 1 detik / test-case 16 MB Standard input (layar) Standard output (layar)

Selain untuk memberi instruksi pada peserta, header tersebut juga berfungsi untuk memberi instruksi pada online judge yang akan memeriksa program. Misalnya, sesuai contoh di atas, program harus diberi nama nama.PAS agar dapat dikenali oleh online judge. Lalu, program hanya boleh memakai memori tidak lebih dari batas memori, yang pada kasus di atas adalah 16 MB (16000000 bytes) (Tentang pemakaian memori akan dibahas di artikel selanjutnya berjudul "Data dan Tipe Data"). Jika program memakai memori lebih dari 16 MB, program akan langsung diberi nilai 0. Setelah itu, program akan diberi "test case" atau masukan-masukan yang sudah disiapkan oleh juri. Masukan-masukan ini akan berbeda dari contoh masukan pada deskripsi soal, dan ada cukup banyak masukan (biasanya 10 atau lebih). Untuk setiap test case, program dijalankan dan waktunya diukur. Jika program berjalan lebih lama daripada batas run-time yang ditentukan, program akan dihentikan secara paksa dan tidak mendapat skor untuk test case tersebut. Jika program berhenti sebelum batas waktu runtime dan mengeluarkan keluaran yang sesuai dengan keluaran juri, program mendapat skor, dan jika tidak sesuai dengan keluaran juri, program tidak mendapat skor. Skor total untuk sebuah program adalah jumlah dari semua skor-skor yang file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_intro2.html

1/4

10/3/13


diperoleh untuk semua test case. Karena yang melakukan pengecekan keluaran adalah komputer, maka kesalahan format sedikit pun tidak akan ditoleransi. Komputer akan menganggap berbeda keempat keluaran ini: 3 3 3

3 Catatan: Keluaran kedua kelebihan sebuah spasi di awal. Keluaran ketiga kelebihan sebuah baris kosong. Keluaran keempat kelebihan sebuah spasi di akhir baris. Oleh karena itu, format keluaran harus persis sesuai yang diminta pada soal, tanpa ada kelebihan spasi di awal baris, di akhir baris, dan tanpa ada baris kosong yang berlebih. Jika Anda melihat kode seperti ini, waspadalah: ... for i := 1 to N do write(A[i], ' '); writeln; Kemungkinan besar, kode di atas akan menghasilkan format keluaran yang salah, karena sebuah spasi akan ditulis setelah A[N] dituliskan. Soal-soal yang ada biasanya meminta agar tidak ada spasi yang berlebih di akhir baris, sehingga kode tersebut kemungkinan besar harus diganti dengan: ... for i := 1 to N do begin write(A[i]); if (i < N) then write(' '); end; file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_intro2.html

2/4

10/3/13


writeln; Selain itu, perhatikan perintah writeln; yang berada di bagian akhir. Perintah ini menjamin agar akhir suatu baris selalu ditutup dengan "tanda baris baru" (end-of-line). Jika perintah writeln; ini tidak ada, keluaran akan dianggap salah oleh online judge, karena online judge mengharuskan akhir baris keluaran untuk diakhiri dengan end-of-line. Selain itu, pada header soal, perhatikan juga nama berkas masukan dan nama berkas keluaran. Sebagian soal membaca masukan dari "standard input" (layar) dan menuliskan keluaran ke "standard output" (layar juga). Pada soal-soal yang spesial, mungkin masukan dan keluaran tidak dari layar dan ke layar, tetapi dari dan ke file. Cara membaca dan menulis file akan dijelaskan suatu waktu. Untuk saat ini, program yang diminta cukup membaca dan menulis ke layar. Selain berfungsi untuk memeriksa program peserta secara otomatis, online judge juga menyediakan "web interface" yang memiliki berbagai fasilitas yang disediakan untuk para peserta, misalnya: Submit program, boleh berkali-kali. Program yang akan diperiksa adalah program yang disubmit terakhir. Pada saat disubmit, program akan dites dengan contoh masukan dan contoh keluaran dan nilainya akan dikeluarkan untuk contoh tersebut. Namun, test case yang ada bukanlah test case juri. Pada akhir pertandingan, program barulah akan diuji dengan test case juri yang sebenarnya, dan skor akan ditentukan kembali. Mengetes program sendiri dengan test case sendiri, dan memeriksa keluarannya sendiri. Melihat program-program apa saja submitnya, dan berapa ukurannya.

yang

sudah disubmit,

kapan

Melihat kode program yang sudah disubmit, dan sebagainya. Sistem online judge TOKI yang sekarang sudah sangat baik, tetapi beberapa alumni dan pembina TOKI sekarang sedang merancang sistem online judge baru yang lebih baik lagi, yang diperkirakan akan selesai pada awal kuartal keempat tahun 2008. file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_intro2.html

3/4

10/3/13


Jika Anda men-submit program Anda dan online judge mengeluarkan nilai 0 untuk contoh test case, Anda dapat menggunakan check list berikut ini: Apakah keluaran program Anda untuk semua contoh masukan sudah benar? Apakah format keluaran Anda sudah benar? Apakah tidak ada spasi di akhir baris, dan baris terakhir input ditutup dengan end-of-line? Apakah program Anda memakai memori lebih dari batas memori yang ditentukan? Apakah nama program Anda benar? Untuk mengakhiri artikel ini, kami ucapkan selamat berjuang dalam Pelatihan Jarak Jauh ini, dan selamat mengeluarkan kemampuan Anda yang sebaik-baiknya.

file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_intro2.html

4/4

10/3/13

TEKS : Data dan Tipe Data

TEKS : Data dan Tipe Data Data adalah sesuatu yang memakai memori, karena data diletakkan di memori. Program sebetulnya adalah data. Kode program itu sendiri, dan kode mesin yang terjadi setelah program itu di-compile adalah data yang akan diletakkan di suatu tempat di memori. Oleh karena itu, bahkan program seperti ini: begin end. tetap memakan memori yang besarnya lebih daripada 0 bytes. Oleh karena itu, jika dituliskan pada "header" soal bahwa batas memori adalah 1 MB, mungkin Anda hanya mendapatkan memori sebesar 700 KB - 800 KB untuk variabel-variabel Anda. Setiap variabel yang Anda deklarasikan di program utama (global variable) akan dianggap sebagai data yang memakan sejumlah memori, dari permulaan program sampai program selesai. Setiap variabel memiliki tipe data, dan setiap tipe data memiliki besar memori yang berbeda-beda dan jangkauan yang berbeda-beda. Misalnya, sebuah integer memakan memori 2 bytes, dan oleh karena itu hanya dapat menyimpan sebuah bilangan bulat bernilai -32768 sampai dengan 32767. Tipe data yang umum digunakan dalam Pascal adalah sebagai berikut: Jenis

Tipe data Range

Memori (byte)

Bilangan shortint -128..127 bulat

1

Bilangan byte bulat

1

0..255

Bilangan smallint -32768..32767 bulat

2

Bilangan integer bulat

-32768..32767

2

Bilangan word bulat

0..65535

2

Bilangan file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_sd1.html

1/4

10/3/13


bulat

longint

-2147483648..2147483647

Bilangan longword 0..4294967295 bulat

4 4

Bilangan int64 bulat

-9223372036854775808..9223372036854775807 8

Bilangan qword bulat

0..18446744073709551615

8

Bilangan real real

tergantung platform

4-8

Bilangan single real

1.5e-45..3.4e38

4

Bilangan double real

5.0e-324..1.7e308

8

Boolean boolean

false, true

1

Karakter char

#0..#255

1

String

string

String dengan panjang maksimal 255

256

String

string[x] String dengan panjang maksimal x

(x+ 1)

(Diambil dari http://www.freepascal.org/docs-html/ref/ref.html) Tipe data yang sering digunakan untuk bilangan bulat adalah longint. Biasakan menggunakan longint sebagai pengganti integer, karena longint diproses sangat cepat oleh prosesor 32-bit, bahkan lebih cepat daripada memroses sebuah integer. Catatan untuk bilangan real: Semua tipe bilangan real dapat menyimpan bilangan positif dan negatif. Dan BASEe-EXP artinya adalah BASE x 10EXP. Jadi, misalnya tipe data single dapat menyimpan nilai 0, 1.5 x 10-45..3.4 x 1038 (positif), dan -3.4 x 1038..-1.5 x 10-45 (negatif). Bilangan real juga memiliki tingkat keakuratan yang berbeda. Misalnya singleakurat sampai 7-8 digit dan doubleakurat sampai 15-16 digit. Jadi, hasil dari 1.0 / 3.0 * 3.0 mungkin bukan 1.0, tetapi 0.9999999 atau 1.0000001. Oleh karena itu, pada saat menggunakan tipe data real, jangan melakukan pembandingan dengan tanda "sama dengan" ( = ). Misalkan Anda memiliki variabel bilangan real bernama r. Pernyataan if (r = 1.0) then file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_sd1.html

2/4

10/3/13


adalah hal yang salah, karena tipe bilangan real mungkin tidak menyimpan nilai yang persis sama dengan 1.0. Hal yang seharusnya dilakukan adalah if (abs(r - 1.0) > toleransi) then dengan toleransi didefinisikan sebagai sebuah nilai yang sangat kecil, misalnya 0.0001. Ingat bahwa nilai toleransi juga tidak boleh terlalu kecil, karena

nilai

toleransi

yang

terlalu kecil

tidak

akan berguna

untuk

pembandingan bilangan real. Pada artikel-artikel berikutnya, akan dibahas array dan record, sebagai tipe data yang sering kali lebih bermanfaat, tetapi akan memakan memori yang lebih besar dari sebuah variabel tunggal. Sebagai catatan, ada perbedaan antara pemakaian memori oleh global variable dan local variable. Semua global variable akan memakai memori pada saat program mulai dijalankan sampai program selesai. Sedangkan, local variable hanya memakan memori pada saat prosedur atau fungsi yang mengandungnya dipakai. Misalnya Anda memiliki sebuah prosedur seperti ini (notasi array akan dibahas selanjutnya): procedure Tulis; var a: array[1..1000000] of longint; begin writeln; end; Prosedur ini akan memakai memori 1000000 * 4 bytes = 4 MB hanya jika prosedur ini dipanggil. Setelah prosedur ini selesai, memori 4 MB tersebut akan dibebaskan kembali. Jika prosedur Tulis tidak pernah dipanggil, array a tidak akan pernah diciptakan. Biasanya total memori yang boleh dipakai global variable dan yang boleh dipakai local variable memiliki batasan yang berbeda. Batas memori global variable adalah sesuai yang tertera di header soal, tetapi batas memori local variable biasanya ditandai dengan "stack size", dan biasanya tidak lebih dari 8 MB. Oleh karena itu, disarankan tidak membuat struktur data local variable yang terlalu besar. Prosedur atau fungsi rekursif juga akan memakan memori yang cukup besar jika fungsi atau prosedur tersebut dipanggil terus-menerus sehingga mencapai kedalaman yang sangat besar. Contohnya: file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_sd1.html

3/4

10/3/13


function Genap(n: integer): boolean; begin if (n = 0) then return true else return not Genap(n - 1); end; Fungsi di atas adalah fungsi rekursif yang berfungsi untuk menentukan apakah suatu bilangan genap atau ganjil, tetapi melakukannya dengan cara yang sangat tidak efisien. Jika Genap(10000000) dipanggil, fungsi tersebut akan

melakukan

rekursi

ke

Genap(9999999),

Genap(9999998),

Genap(9999997), dan seterusnya, berusaha mencapai Genap(0). Namun, pada

kedalaman

tertentu,

fungsi

tersebut

akan

mengalami

"stack

overflow", yaitu sebuah kondisi di mana batas stack (batas memori local variable) telah dilampaui. Perhatikan bahwa fungsi genap paling sedikit memakan 12 bytes memori: 4 bytes untuk tipe data parameter n: integer 4 bytes untuk boolean (meskipun boolean hanya memakai 1 byte, tetapi compiler akan membulatkan ke atas menjadi 4 bytes) 4 bytes untuk menyimpan alamat "return address" pada saat run-time Jadi, setelah sekitar hampir 670000 kali memanggil dirinya sendiri, stack yang dipakai akan melebihi 8 MB, sehingga terjadi "stack overflow". Untuk saat ini, Anda perlu memperhatikan batas memori untuk global variable saja. Pada latihan-latihan berikutnya akan diperkenalkan rekursi, dan Anda akan diminta untuk memperhatikan juga batas memori stack.

file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_sd1.html

4/4

10/3/13

TEKS : Struktur Data Pascal

TEKS : Struktur Data Pascal Pascal memiliki berbagai struktur data sederhana yang dapat Anda pakai, misalnya array, record, dan set. Array adalah suatu struktur data yang dapat berisi banyak elemen dengan tipe data yang sama. Lihat kode berikut ini: var

a: array[1..1000] of longint; b: array[1..2000] of double; c: array[1..3000] of string[50]; begin a[234] := 1; b[345] := 1.0; c[3000] := 'Halo'; end. a dideklarasikan sebagai suatu struktur data yang dapat menampung 1000 buah integer yang berbeda. Integer-integer tersebut dapat diakses dengan a[1], a[2], a[3], ..., a[1000]. Begitu juga dengan b dan c. c dapat menampung 3000 buah string yang panjangnya masing-masing maksimal 50 karakter. Mari kita hitung besar memori yang digunakan ketiga variabel tersebut. a memakai memori 1000 x 4 = 4000 bytes. b memakai memori 2000 x 8 = 16000 bytes. c memakai memori 3000 x (50 + 1) = 153000 bytes. Index yang dideklarasikan di dalam suatu array tidak harus mulai dari 1. Dalam bahasa C / C++, index suatu array mau tidak mau harus dimulai dari 0. Pada Pascal, Anda dapat mengatur index array sesuai kemauan Anda, dan dengan tipe data bilangan bulat, boolean, atau character, misalnya: var

d: array[-999..999] of longint; e: array["a".."z"] of double; f: array[false..true] of string[50];

Sebagai contoh, f memiliki dua buah elemen yang dapat diakses dengan f[false] dan f[true]. Anda juga dapat membuat array multidimensi, seperti berikut ini: var

peta: array[-999..999, -999..999, false..true] of integer; matriks: array[1..3, 1..5, 1..4] of longint;


1/4

10/3/13


Elemen-elemen pada peta adalah peta[-999, -999, false], peta[-999, -999, true], peta[-999, -998, false], dan seterusnya. Elemen-elemen pada matriks juga dapat diakses dengan cara yang sama. Memori yang dipakai oleh peta adalah 1999 * 1999 * 2 * 2 bytes = 15984004 bytes ~ 16 MB. Memori yang dipakai oleh matriksadalah 3 * 5 * 4 * 4 = 240 bytes. Struktur data Pascal yang juga sering dipakai adalah record, seperti pada contoh berikut ini: type TPoint = record x, y: longint; end; TOrang = record nama: string[40]; umur: byte; end; var

bangun: array[1..100] of TPoint; saya, kamu: TOrang;

begin saya.nama := 'Budi'; saya.umur := 30; kamu := saya; bangun[1].x := 3; bangun[1].y := 4; bangun[10] := bangun[1]; end. Sebuah record memiliki elemen-elemen yang dapat berupa tipe data sederhana, array, record lainnya, dan lain-lain. Elemen sebuah record dapat diakses dengan cara di atas. Misalnya, saya.nama adalah elemen nama dari variabel saya. Dan bangun[1].xadalah elemen xdari variabel bangun[1]. Pernyataan kamu := saya akan meng-copy semua nilai elemen-elemen di dalam variabel saya ke dalam variabel kamu, sehingga setelah pernyataan ini kamu.nama akan bernilai 'Budi'dan kamu.umurakan bernilai 30. Mari menghitung memori yang diperlukan struktur data tersebut. Array bangun memerlukan 100 * sizeof(TPoint) = 100 * (4 + 4) = 800 bytes. Variabel saya dan kamumasing-masing memerlukan sizeof(TOrang) = (40 + 1) + 1 = 42 bytes. Namun, biasanya compiler akan membulatkan ukuran sebuah record ke atas, ke bilangan pertama yang merupakan kelipatan 4. Jadi, ukuran record TOrang akan menjadi 44 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_sd2.html

2/4

10/3/13


bytes. Namun, Anda tidak perlu memikirkan detail seperti ini. Struktur data recordbanyak kegunaannya, tetapi biasanya akses data record sedikit lebih lambat dibandingkan akses data tanpa menggunakan record. Misalnya, global variabel yang kita miliki di atas dapat diganti menjadi: var

bangun_x: array[1..100] of longint; bangun_y: array[1..100] of longint; nama_saya, nama_kamu: string[40]; umur_saya, umur_kamu: byte;

Meskipun kode di atas menjadi kurang rapi, tetapi waktu aksesnya agak lebih cepat sedikit dibandingkan dengan menggunakan record. Satu struktur data lain yang cukup berguna adalah set atau himpunan, seperti pada contoh berikut ini: var

a, b: set of char; begin a := ["a".."z"]; b := ["A".."Z"] + ["0".."9"] - ["4", "5", "6"]; b := b + a; if ("a" in a) then writeln; end. Struktur data set hanya dapat digunakan dengan char dan tipe data lain yang ukurannya maksimal 1 byte. set memiliki ukuran 32 bytes, sehingga pada contoh di atas adan bmasing-masing memakai memori 32 bytes. Struktur data setmemiliki konsep seperti himpunan. Pernyataan a := ["a".."z"]; mengisi a dengan karakter-karakter "a", "b", "c", ..., "z". Sintaks A..B mewakili seluruh elemen-elemen yang dimulai dari A dan diakhiri dengan B. Beberapa elemen dapat dipisahkan dengan tanda koma, seperti pada ["4", "5", "6"]. Struktur data set juga memiliki berbagai operasi seperti + (union), (mengecualikan elemen), dan * (intersection). Operator in juga dapat dipakai untuk menguji apakah suatu elemen ada di dalam sebuah set. Struktur-struktur data yang sudah diperkenalkan ini dapat di-nest-kan (disarangkan) menjadi struktur data yang sangat rumit, misalnya: type TBingung = array[1..1000, "a".."z"] of set of char; TBanyak = record c: array[1..200] of string[125]; file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_sd2.html

3/4

10/3/13


d: array[1..10] of TBingung; end; TRumit = record x: array[-50..50, -50..50] of TBanyak; y: TBingung; end; var

a: array[1..10, 1..10] of TRumit;

begin a[4, 5].x[-30, -25].d[3][700, "c"] = ["a".."z", "A".."Z"] - ["c"]; end. Hmm, siapa tahu pada suatu saat Anda membutuhkan struktur data seperti di atas.


4/4

10/3/13

TEKS : Binary Search

TEKS : Binary Search Diberikan sebuah array of integer A, yang elemen-elemennya diberi index 1 sampai dengan N. Misalkan Anda harus mencari elemen bernilai x. Berapa lama waktu yang dibutuhkan? Tentu saja jika elemen di dalam array A tidak beraturan, kita harus mengecek A dari depan sampai belakang, berharap menemukan x. Namun, kali ini kita diberikan array A yang elemen-elemennya sudah terurut dari kecil ke besar. Apakah kita masih harus mengecek elemen-elemen A dari depan sampai belakang? Tidak perlu. Binary search adalah sebuah algoritma standar untuk menemukan suatu elemen dalam sorted array (array terurut) dalam waktu O(log N). Ide binary search adalah seperti ini: Misalkan A memiliki 100 elemen dan kita ingin mencari x = 10. Jika A[50] = 15, maka kita tahu bahwa x tidak mungkin berada di index 51..100, jadi kita hanya perlu mencari di index 1..49 saja. Algoritma binary search menggunakan fungsi rekursif: // fungsi ini akan mengembalikan index dari nilai x yang ditemukan, // dan akan mengembalikan 0 jika x tidak ditemukan // a: index terkiri // b: index terkanan // x: yang dicari function BinarySearch(a, b, x: integer); var m: integer; begin if (a = b) and (A[a] = x) then BinarySearch := a; else if (a <= b) then BinarySearch := 0; else begin m := (a + b) div 2; if (x = A[m]) then BinarySearch := m; else if (x < A[m]) then BinarySearch := BinarySearch(a, m - 1, x); else BinarySearch := BinarySearch(m + 1, b, x); end; end; Pada algoritma di atas ada beberapa basis. Jika b <= a maka hanya ada file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_bsearch.html

1/2

10/3/13

TEKS : Binary Search

maksimum 1 elemen yang menjadi tempat pencarian. Pada kasus ini, kembalikan nilai 0 jika elemen itu tidak bernilai x, dan kembalikan index jika elemen di index tersebut bernilai x. Jika ada 2 atau lebih elemen yang menjadi tempat pencarian, ambil elemen yang berada di tengah (di posisi m). Setelah itu, panggil BinarySearch secara rekursif, tergantung dari bagian mana dari array yang akan dicari, kiri atau kanan. Di bawah ini adalah ilustrasi binary search. Elemen pada index m ditandai dengan kotak biru. Pada setiap pemanggilan BinarySearch, daerah pencarian dikurangi menjadi hanya setengah dari daerah pencarian awal. Dengan demikian, banyak bilangan yang kita bandingkan dengan x berbanding lurus dengan log2 N (atau dengan notasi bahasa Indonesia 2log N).

file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_bsearch.html

2/2

10/3/13

TEKS : Sorting Standard

TEKS : Sorting Standard "To sort" artinya mengurutkan. Misalnya, ada bilangan-bilangan 25413 maka setelah diurutkan akan menjadi 12345 Tapi mengurutkan tidak selalu dari kecil ke besar, tetapi bisa saja dari besar ke kecil, sehingga menjadi 54321 Hal yang diurutkan pun tidak harus angka, tetapi bisa saja string, misalnya komputer toki kompetisi peserta lomba yang setelah diurutkan secara leksikografi (seperti dalam kamus) menjadi kompetisi komputer lomba peserta toki Seperti sudah dikatakan sebelumnya, ada juga cara pengurutan lainnya, misalnya dari kata yang paling pendek ke yang paling panjang: toki lomba peserta komputer kompetisi Jadi kita telah melihat bahwa dalam pengurutan, harus ada tipe data yang akan diurutkan dan juga aturan pengurutan yang jelas. Pengurutan sering dipakai di dalam soal-soal, dan biasanya menjadi suatu bagian dari algoritma yang lebih besar. Ada banyak sekali algoritma pengurutan (sort). Ada yang kodenya mudah dan ada yang kodenya susah. Ada yang cepat dan ada yang lambat. Berikut ini akan dibahas beberapa algoritma pengurutan yang sering dipakai. Untuk semua pembahasan, diberikan sebuah array of integer A yang berisi N buah integer: A[1], A[2], ..., A[N], dan kita diminta untuk mengurutkannya dari kecil ke besar. Selection Sort Algoritma ini cukup straightforward (mudah) dan bisa dilakukan di tempat (tanpa bantuan array lain). Idenya adalah pada setiap langkah, cari elemen terkecil yang tersisa lalu letakkan di depan: file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_sort.html

1/5

10/3/13


for i := 1 to N - 1 begin dari antara A[i..N] cari elemen terkecil. misalnya A[j] jika i ≠ j, tukarkan A[i] dengan A[j] end; Jadi, ketika loop ke-i selesai, A[1..i] sudah berisi i elemen terkecil pertama, tetapi A[i+1..N] mungkin masih acak. Insertion Sort Pada insertion sort, untuk setiap elemen ke-i, kita berusaha meletakkan elemen itu di suatu tempat, sehingga ielemen pertama menjadi terurut: for i := 2 to N begin carilah j sedemikian sehingga jika A[j..i-1] digeser ke kanan dan A[i] diletakkan di posisi j maka A[1..i] menjadi terurut. lakukan penggeseran dan letakkan A[i] di posisi j end; Bubble Sort Pada bubble sort dilakukan N - 1 loop, di mana pada setiap loop elemen yang kecil perlahan-lahan bergeser ke depan dan yang besar perlahan-lahan bergeser ke belakang: for i := 1 to N - 1 for j := i + 1 to N if (A[i] > A[j]) then tukar A[i] dengan A[j] Merge Sort Selection Sort, Insertion Sort, dan Bubble Sort adalah contoh-contoh sort yang memakan waktu O(N2), yang artinya kira-kira adalah running time berbanding lurus dengan kuadrat dari banyak input. Jadi, algoritma-algoritma sort di atas tidak baik dipakai untuk N yang terlalu besar. Algoritma merge sort dan quick sort (berikutnya) adalah algoritma yang berjalan dengan waktu O(N log N), yang jauh lebih efisien daripada O(N2), dan akan berjalan jauh lebih cepat untuk N yang besar. Algoritma merge sort sesungguhnya sangat sederhana: Bagi array menjadi dua sama besar, sort bagian pertama, sort bagian kedua, lalu gabungkan. Tentu sort ini menggunakan prosedur rekursif dengan parameter index paling kiri (a) dan index paling kanan (b), seperti ini: procedure Sort(a, b: integer); begin if (b > a) then begin Sort(a, (a + b) div 2); // sort bagian pertama Sort((a + b) div 2 + 1, b); // sort bagian kedua Merge(a, (a + b) div 2, (a + b) div 2 + 1, b); // gabungkan end; end; dengan pemanggilan pertama Sort(1, N); file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_sort.html

2/5

10/3/13


Di manakah basisnya? Basisnya adalah pada kasus b = a, yaitu ketika hanya ada 1 elemen yang akan disort. Pada kasus ini, Sort tidak melakukan apa-apa. Inti dari algoritma ini sebenarnya ada pada bagian Merge, yang berfungsi menggabungkan A[a1..b1] yang terurut dan A[a2..b2] yang terurut menjadi A[a1..b2] yang terurut. Catatan: kita menggunakan sebuah array B untuk menyimpan hasil sementara. Pada setiap loop, kita menentukan apakah elemen dari A[a1..b1] atau dari A[a2..b2]yang harus ditambahkan ke B. Jika sudah selesai, B akan dipindahkan ke A. procedure Merge(a1, b1, a2, b2: integer); var i: integer; begin i := a1; while (a1 <= b1) and (a2 <= b2) do begin if (A[a1] <= A[a2]) then masukkan nilai A[a1] ke B[i] lalu a1 := a1 + 1; else masukkan nilai A[a2] ke B[i] lalu a2 := a2 + 1; i := i + 1; end; // sisanya yang belum dimasukkan ke B while (a1 <= b1) masukkan nilai A[a1] ke B[i] lalu a1 := a1 + 1; i := i + 1; while (a2 <= b2) masukkan nilai A[a2] ke B[i] lalu a2 := a2 + 1; i := i + 1; copy B[a1..b2] ke A[a1..b2] end; Ilustrasi Merge Sort (bagian berwarna biru menunjukan proses Merge):

Quick Sort Quick Sort adalah algoritma sort yang tercepat dari antara sort-sort O(N log N) lainnya. Tetapi, Quick Sort juga algoritma yang running timenya tidak stabil. Artinya, dijamin 99,9999% bahwa Quick Sort akan berjalan dengan sangat cepat, tetapi pada kasus-kasus tertentu Quick Sort akan berjalan agak lambat, dan kalau sedang sial, untuk input tertentu (worst case) Quick Sort akan berjalan dengan waktu O(N2). Tapi pada umumnya (average case), Quick Sort berjalan dengan waktu O(N log N). Algoritma ini sangat unik. Inti dari algoritma ini: procedure Quicksort(a, b: integer); var pivot: integer; begin if (b > a) then begin pivot := A[(a + b) div 2]; pindahkan semua elemen yang lebih kecil dari pivot ke sebelah kiri pivot pindahkan semua elemen yang lebih besar dari pivot ke sebelah kanan pivot misalkan pivot akhirnya berada di posisi j, maka Quicksort(a, j - 1); Quicksort(j + 1, b); end; end; dengan pemanggilan pertama file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_sort.html

3/5

10/3/13


Quicksort(1, N); Basis dari prosedur rekursif ini adalah pada kasus b <= a, yaitu ketika hanya ada maksimum 1 elemen yang akan disort. Pivot dapat dipilih secara acak, dan bisa elemen apapun dari antara A[a..b]. Untuk kasus di atas, kita pilih elemen ke-(a + b) div 2. Di bawah ini adalah ilustrasi Quick Sort, di mana elemen yang diberi kotak biru adalah pivot. Perhatikan bahwa elemen-elemen yang lebih kecil dari pivot diletakkan di sebelah kiri pivot, dan yang lebih besar di sebelah kanan pivot.

Salah satu implementasi Quick Sort dapat dilihat pada contoh berikut: procedure Quicksort(a, b: integer); var pivot: integer; left, right: integer; begin if (b > a) then begin pivot := A[(a + b) div 2]; left := a; right := b; while (left <= right) begin while (A[left] < pivot) left := left + 1; while (A[right] > pivot) right := right - 1; if (left <= right) then begin swap A[left] dengan A[right] left := left + 1; right := right - 1; end; end; // sampai di sini, tentu left > right Quicksort(a, right); Quicksort(left, b); end; end; Algoritma sort yang stabil Kadang kala input yang kita miliki dapat memiliki elemen-elemen bernilai sama seperti 12313122 sehingga jika diurutkan dari kecil ke besar menjadi 11122233 Pada kasus ini tidak ada masalah, karena angka-angka yang sama tidak bisa dibedakan. Namun bagaimana jika Anda diberikan input makan lomba main tidur file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_sort.html

4/5

10/3/13


toki lalu Anda harus mengurutkan kata-kata tersebut dari yang pendek ke panjang? Bagaimana memecahkan kondisi seri (tie) antara "toki" dan "main", dan juga antara "makan", "lomba", dan "tidur"? Algoritma sort yang stabil (stable) adalah algoritma yang dapat mengurutkan input, dan jika menemukan kondisi seri, akan mengeluarkan elemen-elemen yang seri sesuai dengan urutan input awal. Pada contoh di atas, algoritma yang stabil akan mengeluarkan: main toki makan lomba tidur karena "main" muncul terlebih dahulu daripada "toki", dan "makan" muncul dahulu daripada "lomba", lalu daripada "tidur". Dari algoritma-algoritma yang sudah kita pelajari di atas, semua algoritma stabil kecuali Quick Sort. Ketika menggunakan Quick Sort, kita tidak bisa menentukan urutan relatif dari elemen-elemen yang seri. Berikut ini adalah tabel perbandingan algoritma-algoritma sort yang sudah kita pelajari: Algoritma Stabil

Running time

Catatan

Selection Sort

Ya

O(N2)

Running time tidak tergantung input

Insertion Sort

Ya

O(N2)

Jika input hampir terurut, running time menjadi sangat cepat

Bubble Sort

Ya

O(N2)

Lambat dibandingkan algoritma O(N2) lainnya

Merge Sort

Ya

O(N log N)

Running time tidak tergantung input

Quick Sort Tidak O(N log N)

Paling cepat dibandingkan algoritma O(N log N) lainnya, tetapi pada kasus terburuk (sangat jarang terjadi) menjadi O(N2). Algoritma ini adalah algoritma yang paling populer digunakan di kompetisi informatika.

file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_sort.html

5/5

10/3/13

TEKS : Search Problem

TEKS : Search Problem Search problem atau masalah pencarian adalah salah satu jenis masalah yang paling sering dipecahkan menggunakan komputer, karena cara kerja komputer yang bodoh namun cepat sangat cocok untuk memecahkan masalah-masalah jenis ini. Ada banyak sekali masalah-masalah yang dapat dimodelkan sebagai masalah pencarian. Masalah pencarian memiliki komponen-komponen berikut ini: Deskripsi state Initial state Goal state State transition Biasanya pencarian dimulai dari state mula-mula atau initial state, dan tujuannya adalah menemukan goal state. Kita hanya dapat melangkah dari sebuah state ke state lainnya menurut aturan transisi atau state transition. Sering kali kita tidak mengetahui seperti apa goal state yang akan dicari, tetapi kita hanya diberi tahu ciri-ciri dari goal state tersebut. Contoh 1: Banyak jalan menuju Roma Misalkan Anda sedang berada di sebuah kota X di dekat Roma, dan Anda ingin pergi ke roma. Program Anda diberikan sebuah peta berisi kota-kota yang dihubungkan dengan jalan-jalan, dan program Anda harus menemukan sebuah rute yang mana saja dari kota X ke Roma, atau jika tidak ada, memberi tahu bahwa tidak ada jalan ke Roma. Bagaimanakan cara komputer melihat masalah ini?

file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_search1.html

1/4

10/3/13


Kita dapat mengasosiasikan sebuah kota dengan sebuah state. Artinya, jika Anda sedang berada di sebuah kota A, Anda berada pada state A. Initial state adalah state X. Goal state adalah state Roma. Sebuah state transition yang sah adalah transisi dari sebuah kota ke kota lainnya yang dihubungkan oleh sebuah ruas jalan di peta. Bagaimanakah cara menemukan sebuah rute dari X menuju Roma? Tentu program Anda perlu memanfaatkan state transition yang diberikan (ruasruas jalan yang diberikan) untuk melangkah dari kota X ke kota lainnya, lalu ke kota lain lagi, dan seterusnya, hingga mencapai Roma. Bagaimana persisnya akan dibahas pada artikel-artikel berikutnya. Contoh 2: 8 Queen Problem Pada permainan catur, queen / ratu adalah sebuah anggota pasukan yang paling kuat. Ratu dalam berjalan ke depan, kiri, kanan, belakang, dan keempat diagonal, sebanyak satu atau lebih langkah. Dengan demikian, anggota pasukan yang berada di baris atau kolom atau diagonal yang sama dengan sang ratu berada dalam posisi "diserang" oleh ratu tersebut. file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_search1.html

2/4

10/3/13


Pada masalah ini, Anda diminta untuk meletakkan 8 buah ratu di papan catur berukuran 8 x 8, sedemikian sehingga tidak ada sepasang ratupun yang saling menyerang satu sama lain (seperti pada gambar). Hal ini bukan hal yang mudah dilakukan bahkan oleh manusia. Bagaimanakah cara menginstruksikan komputer untuk melakukan hal ini?

Mari kita mendeskripsikan masalah ini sebagai search problem. Sebuah state akan kita deskripsikan sebagai peletakan nol (0) atau lebih ratu pada papan catur sehingga tidak ada ratu yang menyerang ratu lainnya. Tentu initial state-nya adalah state di mana hanya ada 0 ratu pada papan catur (belum ada sama sekali yang diletakkan). Goal state-nya adalah semua state di mana ada 8 ratu pada papan catur dan tidak ada yang menyerang satu sama lain. Perhatikan bahwa goal state bisa saja ada lebih dari satu. Dalam kasus ini, ada 92 cara berbeda meletakkan 8 ratu tanpa saling menyerang, sehingga ada 92 goal state. Tentu saja, tanpa melakukan pencarian, kita tidak akan tahu state mana file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_search1.html

3/4

10/3/13


sajakah yang merupakan goal state. Sebuah state transition adalah transisi dari state X ke state X', yang didefinisikan sebagai state X yang ditambah sebuah ratu baru yang diletakkan pada papan catur sehingga tidak ada ratu yang saling menyerang. Catatan: Tidak semua state dalam masalah ini memiliki state transition. Misalnya, mungkin saja kita berada pada suatu state di mana jumlah ratu yang diletakkan kurang dari 8, tetapi kita tidak bisa meletakkan ratu lagi di papan. Hal ini dapat dimengerti sebagai menemukan "jalan buntu" / dead end. Cara memecahkan masalah ini dengan komputer cukup sederhana. Tentu program harus mulai dari initial state, yaitu state tanpa ratu. Lalu, program melakukan state transition, dengan cara meletakkan ratu berikutnya di papan catur. Jika program menemukan state di mana tidak ada state transition, program menemukan jalan buntu sehingga program harus menarik kembali ratu yang baru saja diletakkan. Begitu seterusnya hingga program meletakkan ratu yang ke-8 di papan catur dengan sukses. Detailnya akan dibahas pada artikel-artikel berikutnya.


4/4

10/3/13

TEKS : Depth First Search (DFS)

TEKS : Depth First Search (DFS) DFS adalah sebuah teknik pencarian di mana penelusuran dimulai dari initial state, menuju state berikutnya, lalu menuju state berikutnya, dan seterusnya, sampai pencarian menemukan jalan buntu. Jika menemukan jalan buntu, mundur ke state sebelumnya dan coba lagi state lainnya, dan seterusnya, hingga goal state tercapai. Contoh 1: Banyak jalan menuju Roma

Beginilah contoh langkah-langkah yang dilakukan dengan algoritma DFS: Mulai dari X Jalan ke 14, lalu 10, lalu 15, lalu 16, lalu 7, lalu 8, lalu 9 Di kota 9 menemukan jalan buntu, jadi balik ke kota 8. Di kota 8 masih menemukan jalan buntu, jadi balik ke kota 7. Dari kota 7 ke kota 6, lalu 5, lalu 4, lalu 18, lalu 2, lalu 3. Di kota 3 menemukan jalan buntu, jadi balik ke kota 2. Dari kota 2 ke kota 1, lalu ke Roma.

file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_dfs.html

1/4

10/3/13


Perhatikan bahwa banyak kota yang dilewati sebelum sampai ke Roma tidak tentu, tergantung kota mana dulu yang ditelusuri. Kadang-kadang DFS dapat menemukan goal state dengan sangat cepat jika sedang beruntung, tetapi sering kali DFS memakan waktu yang sangat lama sebelum menemukan goal state jika ada banyak sekali state dalam search problem tersebut. Implementasi DFS tentu paling natural menggunakan rekursi sederhana, contohnya sebagai berikut: (* Global *) var sudahDikunjungi : array[1..N_KOTA] of boolean; X : longint; Roma : longint; function Kunjungi(kota : longint) : boolean begin sudahDikunjungi[kota] := true; for tetangga := 1 to N_KOTA do begin if (AdaJalan(pivot, tetangga) and not sudahDikunjungi[tetangga]) then begin if (tetangga = Roma) then begin Kunjungi := true; exit; end; if (Kunjungi(tetangga) = true) then begin Kunjungi := true; exit; end; file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_dfs.html

2/4

10/3/13


end; end; Kunjungi := false; end; function RomaDitemukan() : boolean var kota : longint; begin for kota := 1 to N_KOTA do sudahDikunjungi[kota] := false; RomaDitemukan := Kunjungi(X); end; Jika for loop telah selesai, namun nilai Kunjungi untuk nilai kota = X masih belum true juga, artinya memang tidak ada jalan menuju Roma dari kota X. Contoh 2: 8 Queen Problem

Masalah ini juga cukup mudah diselesaikan dengan cara DFS. Kita mulai dari initial state, yaitu state di mana tidak ada queen yang diletakkan di papan catur. Lalu kita meletakkan queen pertama, lalu queen kedua, lalu queen ketiga, dan seterusnya, sampai kita menemukan jalan buntu. Jika kita menemukan jalan buntu, tarik kembali queen terakhir, dan coba letakkan di posisi yang berbeda, dan seterusnya, sampai goal state tercapai. Contoh implementasi DFS untuk soal ini secara garis besar adalah sebagai berikut: function Coba(sekarang : KonfigurasiPapanCatur) : KonfigurasiPapanCatur var row, column : longint; berikut, hasil : KonfigurasiPapanCatur; begin for row := 1 to 8 do for column := 1 to 8 do begin berikut := CobaLetakkanQueenDi(sekarang, row, column); if (berikut <> nil) then begin hasil := Coba(berikut); if (hasil <> nil) then begin Coba := hasil; exit; file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_dfs.html

3/4

10/3/13


end; end; end; return nil; end; function CariKonfigurasi8Queen() : KonfigurasiPapanCatur begin CariKonfigurasi8Queen := Coba(KonfigurasiPapanCaturKosong()); end; Perhatikan bahwa fungsi Coba mungkin saja mengembalikan nilai nil untuk nilai parameter "sekarang" tertentu. Hal ini terjadi jika diberikan parameter "sekarang" tertentu, tidak ada cara meletakkan queen-queen berikutnya sedemikian sehingga 8 queen dapat diletakkan di papan catur tanpa saling menyerang. Perhatikan juga bahwa sekarang kita tidak memerlukan queue karena memang DFS tidak memerlukan queue. Dan pada masalah ini, kita juga tidak perlu mengecek apakah sebuah konfigurasi sudah pernah dikunjungi atau belum. Hal ini dapat berakibat beberapa konfigurasi dikunjungi lebih dari satu kali, tetapi hal ini dapat diterima, karena goal state yang mungkin juga ada banyak, sehingga kemungkinan besar sebuah goal state ditemukan sebelum terlalu banyak state dikunjungi. Perhatikan juga bahwa dengan DFS untuk memecahkan masalah ini, tidak ada lagi masalah memori. Memori yang dibutuhkan hanyalah beberapa puluh bytes saja untuk setiap kedalaman rekursi, dan kedalaman rekursi pada kasus ini maksimal hanyalah 8.

file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_dfs.html

4/4

10/3/13

TEKS : Breadth First Search (BFS)

TEKS : Breadth First Search (BFS) BFS adalah sebuah teknik pencarian di mana state-state yang ditelusuri pertama kali adalah state yang terdekat, setelah itu yang lebih jauh, setelah itu yang lebih jauh lagi, dan seterusnya, hingga goal state ditemukan. Contoh 1: Banyak jalan menuju Roma

Kita kembali pada contoh masalah berikut ini. Anda berada di kota X dan Anda ingin menemukan jalan menuju kota Roma. Ide BFS adalah sebagai berikut. Anda mulai dari kota X. Setelah itu Anda menemukan kota-kota yang terdekat dari kota X, yaitu kota 14, 18, 17, dan 9. Setelah itu, Anda menemukan kota-kota yang berjarak 2 langkah dari kota X, yaitu Roma, 2, 3, 4, 5, 6, 15, 16, 8, dan 10. Ternyata kota Roma termasuk salah satu dari daftar kota ini. Sampailah Anda di Roma.

file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_bfs.html

1/4

10/3/13


Mari kita melihat bagaimana komputer melakukan hal ini. Kita perlu memiliki sebuah data struktur queue (antrian), di mana kita dapat menambahkan elemen baru di belakang dan mengambil elemen dari depan. Langkah-langkah BFS untuk kasus ini adalah sebagai berikut: Masukkan X ke queue Ambil X dari queue, lalu masukkan semua tetangganya yang belum ada di queue (9, 17, 18, 14) ke queue Ambil 9 dari queue, lalu masukkan semua tetangganya yang belum ada di queue (10, 16, 8) ke queue Ambil 17 dari queue, lalu masukkan semua tetangganya yang belum ada di queue (4, 5, 6, 15) ke queue Ambil 18 dari queue, lalu masukkan semua tetangganya yang belum ada di queue (3, 2, Roma) ke queue Sampai di sini, ternyata kita sudah menemukan kota Roma. Beginilah contoh implementasi BFS dengan Pascal: function RomaDitemukan(X : longint; Roma : longint) : boolean var queue : array [1..N_KOTA] of longint; queueDepan : longint; queueBelakang : longint; i : longint; tetangga : longint; pivot : longint; sudahDikunjungi : array[1..N_KOTA] of boolean; begin (* Inisialisasi struktur data *) queueDepan := 1; queueBelakang := 2; queue[1] = X; for i := 1 to N_KOTA do sudahDikunjungi[i] := false; sudahDikunjungi[X] := true;


2/4

10/3/13


(* BFS *) while (queueDepan < queueBelakang) do begin (* Ambil kota di posisi paling depan queue *) pivot := queue[queueDepan]; queueDepan := queueDepan + 1; (* Masukkan tetangga-tetangganya ke dalam queue *) for tetangga := 1 to N_KOTA do begin if (AdaJalan(pivot, tetangga) and not sudahDikunjungi[tetangga]) then begin queue[queueBelakang] := tetangga; queueBelakang := queueBelakang + 1; if (tetangga = Roma) then begin RomaDitemukan := true; exit; end; end; end;

(* Ketemu. Keluar dari fungsi *)

end; RomaDitemukan := false; end; Dapat saja terjadi bahwa ternyata tidak ada jalan dari X menuju Roma. Jika hal ini terjadi, kondisi queueDepan < queueBelakang pada akhirnya akan menjadi false, dan algoritma BFS selesai tanpa menemukan kota Roma. Contoh 2: 8 Queen Problem

Algoritma BFS juga bisa diterapkan untuk masalah 8 queen problem. Idenya, kita mulai dari initial state, yaitu dari state di mana tidak ada sama sekali queen yang dipasang pada papan catur. Setelah itu, kita mengunjungi semua state di mana ada tepat satu queen yang dipasang pada papan catur. Setelah selesai, kita mengunjungi semua state di mana ada tepat dua queen yang dipasang di papan catur, dan seterusnya. Pada akhirnya, tentu kita akan menemukan state di mana ada 8 queen di papan catur yang tidak saling menyerang. Contoh implementasi BFS dalam kasus ini adalah sebagai berikut (secara garis besar): function CariKonfigurasi8Queen() : KonfigurasiPapanCatur var queue : array [1..N_KONFIGURASI] of KonfigurasiPapanCatur; file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_bfs.html

3/4

10/3/13


queueDepan : longint; queueBelakang : longint; i : longint; pivot : KonfigurasiPapanCatur; tetangga : array [1..N_KONFIGURASI] of KonfigurasiPapanCatur; begin queueDepan := 1; queueBelakang := 2; queue[1] = KonfigurasiPapanCaturKosong(); (* BFS *) while (queueDepan < queueBelakang) do begin (* Ambil konfigurasi papan dari paling depan queue *) pivot := queue[queueDepan]; queueDepan := queueDepan + 1; (* Masukkan tetangga-tetangganya ke dalam queue *) tetangga := DapatkanSemuaTetangga(pivot); for i := 1 to length(tetangga) do begin if (not SudahDikunjungi(tetangga[i])) then begin TandaiSudahDikunjungi(tetangga[i]); queue[queueBelakang] := tetangga; queueBelakang := queueBelakang + 1; if (BanyakQueen(tetangga[i]) = 8) then begin CariKonfigurasi8Queen := tetangga[i]; exit; end; end; end; end; end; Masalah ini sedikit berbeda dengan masalah sebelumnya. Dalam masalah ini, BFS agak sulit diterapkan karena memori yang dibutuhkan sangat besar, karena jumlah state yang mungkin berada di dalam queue secara bersamaan mungkin saja sangat besar.


4/4

10/3/13

TEKS : Perbandingan Algoritma Search

TEKS : Perbandingan Algoritma Search BFS dan BFS adalah teknik pencarian yang paling sering digunakan. Keduanya memiliki pendekatan yang cukup berbeda. Breadth First Search mengutamakan breadth atau pelebaran. Depth First Search mengutamakan depth atau kedalaman. Untuk menentukan apakah sebuah search problem akan lebih baik diselesaikan dengan BFS atau DFS, kita perlu melihat ciriciri masalah yang akan dipecahkan. Jika kita tahu bahwa goal state letaknya sangat dekat dengan initial state, dan ada banyak state yang tidak relevan, mungkin BFS adalah pilihan yang lebih baik. Sebaliknya, jika kita tahu persis jarak dari initial state ke goal state (seperti pada 8 queen problem), BFS tidak akan membantu, dan kita lebih baik menggunakan DFS karena lebih hemat memori. Berapakah running time yang dibutuhkan BFS dan DFS? Secara umum, running time BFS paling lama proporsional dengan banyaknya state yang berada dalam jarak sejauh initial state ke goal state. Sebaliknya, tidak ada batasan maksimum running time DFS jika kita tidak mengecek state mana saja yang sudah dikunjungi. Jika kita mengecek state yang sudah pernah dikunjungi, paling lama DFS perlu mengunjungi semua state sebelum menemukan goal state. Memori yang diperlukan BFS proporsional dengan banyak state yang dapat berada di queue dalam waktu yang bersamaan. Sering kali hampir semua state dapat berada di queue dalam waktu yang bersamaan, jadi memori yang diperlukan proposional dengan banyak semua state. Sedangkan, memori yang diperlukan kedalaman rekursi.

DFS

umumnya

hanya

proporsional

dengan

Jika kita ingin meminimalkan banyaknya langkah yang harus dilakukan dari initial state ke goal state terdekat, kita akan mendapatkan banyak langkah optimal dengan BFS. DFS tidak dapat melakukan hal ini. Teknik pencarian lainnya Ada berbagai variasi dari BFS dan DFS yang kadang-kadang digunakan karena memiliki kelebihan tertentu.


1/2

10/3/13

TEKS : Perbandingan Algoritma Search

Bidirectional search / search dua arah adalah search yang dilakukan dari initial state dan dari goal state secara bersamaan. Jika kita mengetahui bahwa jarak dari initial state ke goal state tidak begitu jauh, teknik ini dapat mempercepat search. Misalnya, pada masalah jalan menuju Roma, kita dapat melakukan search dari kota X dan dari kota Roma, dan berusaha untuk bertemu di tengah jalan. DFS-ID (DFS with Iterative Deepening) adalah DFS yang dilakukan secara bertahap, dari kedalaman 1, 2, 3, dan seterusnya. Hal ini berfungsi untuk mencegah DFS melakukan penelusuran yang tidak relevan demi mencapai goal state. Misalnya, pada masalah jalan menuju Roma, pertama kita melakukan DFS dengan kedalaman maksimum 1. Kita akan menemukan seluruh tetangga kota X. Setelah itu, kita melakukan DFS dengan kedalaman maksimum 2. Kita akan menemukan seluruh kota yang berjarak 2 dari kota X, termasuk kota Roma. Apa keuntungan memakai DFS-ID dibandingkan DFS atau BFS? DFS-ID jelas memiliki keuntungan running time dibandingkan dengan DFS, jika kita tahu bahwa goal state tidak terlalu jauh dari initial state. Running time DFS-ID tetap lebih lambat dibandingkan running time BFS. Namun, DFS-ID tidak memerlukan queue seperti BFS, sehingga memori yang dibutuhkan DFS-ID sangatlah sedikit, hanya proporsional terhadap kedalaman search.


2/2

10/3/13

Rekursi (1)

Rekursi (1) Rekursi adalah metode mengekspresikan sesuatu menggunakan dirinya sendiri. Misalnya, gambar di samping ini adalah gambar sebuah kemasan produk bergambar orang yang sedang memegang kemasan produk, yang bergambar orang yang sedang memegang kemasan produk, yang bergambar orang yang sedang... dan seterusnya. Gambar itu disebut gambar yang rekursif.

Pada bidang pemrograman, rekursi banyak dipakai untuk memecahkan berbagai masalah, dan diwujudkan dalam prosedur rekursif atau fungsi rekursif. Prosedur rekursif adalah prosedur yang memanggil dirinya sendiri, dan fungsi rekursif adalah fungsi yang memanggil dirinya sendiri. Contoh: Deret Fibonacci Misalnya, deret Fibonacci didefinisikan seperti ini: F(1) = 1 F(2) = 1 F(n) = F(n - 1) + F(n - 2), untuk n≥3 Kita dapat membuat sebuah fungsi rekursif yang menghasilkan nilai F(n) dengan mudah: function Fibonacci(n: longint): longint; begin if (n = 1) or (n = 2) then Fibonacci := 1 else Fibonacci := Fibonacci(n - 1) + Fibonacci(n - 2); end;

file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_rekursi1.html

1/4

10/3/13

Rekursi (1)

Fungsi di atas akan menghasilkan hasil yang benar. Misalnya, pemanggilan Fibonacci(3) akan menghasilkan 2, Fibonacci(4) akan menghasilkan 3, dan Fibonacci(5) akan menghasilkan 5. Mengapa fungsi di atas dapat menghasilkan hasil yang benar? Ketika fungsi Fibonacci dipanggil dengan parameter 1 atau 2, fungsi tersebut akan mengembalikan nilai 1. Ketika fungsi itu dipanggil dengan parameter 3 ke atas, fungsi itu akan memanggil dirinya sendiri untuk mendapatkan hasil dari Fibonacci(1) dan Fibonacci(2), untuk mengeluarkan hasil yang benar untuk pemanggilan Fibonacci(3). Demikian seterusnya. Ada dua komponen yang penting dalam penulisan suatu prosedur atau fungsi rekursif, yaitu "basis" dan "rekurens". Rekurens adalah bagian yang memanggil dirinya sendiri, yang pada contoh di atas adalah Fibonacci := Fibonacci(n - 1) + Fibonacci(n - 2);. Basis adalah bagian yang memberi batas pada rekursi, yang pada contoh di atas adalah if (n = 1) or (n = 2) then Fibonacci := 1. Meskipun rekurens adalah bagian utama dalam rekursi tersebut, basis menjadi bagian yang tidak kalah pentingnya. Bayangkan jika tanpa sengaja Anda menuliskan fungsi seperti ini: function Fibonacci(n: longint): longint; begin Fibonacci := Fibonacci(n - 1) + Fibonacci(n - 2); end; Maka fungsi ini tidak akan pernah berhenti memanggil dirinya sendiri, dan setelah beberapa lama akan mengalami "stack overflow" karena kehabisan memori. Namun, fungsi di bawah ini juga tetap salah: function Fibonacci(n: longint): longint; begin if (n = 1) then Fibonacci := 1 else Fibonacci := Fibonacci(n - 1) + Fibonacci(n - 2); end; karena basisnya tidak lengkap. Pemanggilan Fibonacci(2) untuk fungsi di atas

ini

tidak

akan

menghasilkan

hasil

yang

benar

karena

tidak

didefinisikan. Bahkan, fungsi itu akan memanggil Fibonacci(1) dan Fibonacci(0) (yang tidak didefinisikan) dan akan berjalan terus-menerus file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_rekursi1.html

2/4

10/3/13

Rekursi (1)

sampai stack overflow. Jadi, menentukan basis yang benar pada rekursi adalah hal yang sangat penting. Contoh: Menguji Palindrom Sebagai contoh, buatlah sebuah fungsi rekursif bernama Palindrom yang memiliki parameter sebuah string dan mengembalikan sebuah boolean. Fungsi tersebut mengembalikan true jika string itu adalah palindrom (dibaca sama dari kiri dan dari kanan) dan false jika bukan. Misalnya, Palindrom('abcba') akan menghasilkan true, tetapi Palindrom('abcb') akan menghasilkan false. Mari membuat fungsi tersebut secara bertahap: function Palindrom(s: string): boolean; begin ... Palindrom := (s[1] = s[length(s)]) and Palindrom(substr(s, 2, length(s) - 2)); end; Pada contoh di atas, hanya bagian rekurens saja yang sudah ditulis. Jadi kita mendefinisikan Palindrom secara rekursif sebagai berikut: sadalah palindrom jika dan hanya jika karakter pertama ssama dengan karakter terakhir s, dan karakter-karakter di antaranya membentuk palindrom. Misalnya 'abcba' adalah palindrom karena karakter pertamanya sama dengan karakter terakhirnya, dan 'bcb'juga adalah palindrom. Catatan:

substr adalah

mengembalikan

substring

sebuah dari

fungsi

string

Pascal

yang

yang

akan

diberikan.

Jadi,

substr(s, first, count) akan mengembalikan sebuah string yang dimulai dari karakter s yang ke-first sampai dengan karakter ke-(first + count - 1). Pada

contoh di atas,

substr(s, 2, length(s) - 2) mengembalikan karakter kedua hingga karakter kedua sebelum terakhir dari s. Setelah kita yakin bahwa rekurens kita sudah benar, kita dapat menentukan basis yang lengkap untuk fungsi rekursif ini. Kasus sederhana yang dapat kita temukan mungkin adalah string dengan panjang 1. Mari kita ubah kode file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_rekursi1.html

3/4

10/3/13

Rekursi (1)

menjadi seperti ini: function Palindrom(s: string): boolean; begin if (length(s) = 1) then Palindrom := true else Palindrom := (s[1] = s[length(s)]) and Palindrom(substr(s, 2, length(s) - 2)); end; Namun basis di atas tidak lengkap, karena fungsi di atas tidak dapat mendeteksi palindrom dengan panjang genap, misalnya 'aa'. Untuk itu, kita perlu menambahkan sebuah basis lagi, yaitu kasus string dengan panjang 0. Tentu string kosong juga adalah palindrom karena dibaca sama dari kiri dan dari kanan. function Palindrom(s: string): boolean; begin if (length(s) <= 1) then Palindrom := true; else Palindrom := (s[1] = s[length(s)]) and Palindrom(substr(s, 2, length(s) - 2)); end; Demikianlah fungsi Palindrom yang benar. Catatan: Sebetulnya kita tidak memerlukan rekursi untuk menguji apakah sebuah string adalah palindrom, dan bahkan fungsi rekursi ini akan berjalan lambat karena fungsi substrmemakan waktu yang agak lama dan dipanggil berulang-ulang. Contoh ini hanya untuk menjelaskan rekursi saja.


4/4

10/3/13

Rekursi (2)

Rekursi (2) Pada artikel ini, kita akan melihat masalah-masalah yang membutuhkan rekursi yang lebih rumit daripada sebelumnya. Jika pada artikel rekursi yang pertama kita menghitung jawaban untuk parameter N menggunakan nilai N yang lebih kecil, sekarang kita tidak bisa hanya mengandalkan parameter N, karena kita harus mempertimbangkan "konteks" dari masalah yang lebih kecil tersebut. Contoh: Kombinasi 1, 2, 3 Mari kita memecahkan soal berikut ini bersama-sama. Diberikan sebuah bilangan bulat N yang cukup kecil, tuliskan semua bilangan yang terdiri atas N digit-digit 1, 2, atau 3, satu bilangan setiap baris, diurutkan dari bilangan terkecil. Misalnya, untuk N = 3, program harus menuliskan 111 112 113 121 122 123 131 132 133 211 ... 333 Mari kita buat suatu prosedur rekursif yang akan menyelesaikan masalah berikut ini. Perhatikan bahwa kita dapat mendelegasikan masalah N = 3 ke masalah yang lebih kecil, yaitu N = 2. Mari kita susun prosedur rekursifnya: procedure Tulis(n: integer); var i: integer; begin ... for i := 1 to 3 do Tulis(n - 1); end; Tapi sepertinya ada yang kurang. Apa artinya Tulis(2) yang pada kode di file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_rekursi2.html

1/6

10/3/13

Rekursi (2)

atas dipanggil tiga kali? Kita menyadari bahwa ada sesuatu yang kurang: Kita harus menyimpan prefiks dari bilangan-bilangan yang akan ditulis oleh Tulis(2): procedure Tulis(n: integer; prefiks: longint); var i: integer; begin ... for i := 1 to 3 do Tulis(n - 1, prefiks * 10 + i); end; Dengan cara ini, Tulis(3, 0)akan memanggil: Tulis(2, 1) Tulis(2, 2) Tulis(2, 3) dan Tulis(2, 1)akan memanggil: Tulis(1, 11) Tulis(1, 12) Tulis(1, 13) dan seterusnya. Lalu kita perlu menuliskan basis untuk prosedur tersebut, yaitu kasus di mana n = 0. Karena tidak ada bilangan yang memiliki 0 digit, apakah kita tidak perlu menuliskan apa-apa? Kita tetap perlu menuliskan prefiks yang sudah diteruskan dari satu pemanggilan ke pemanggilan berikutnya, tetapi kita tidak perlu menuliskan digit lagi di belakang prefiks tersebut. procedure Tulis(n: integer; prefiks: longint); var i: integer; begin if (n = 0) then writeln(prefiks) else for i := 1 to 3 do Tulis(n - 1, prefiks * 10 + i); end; Demikianlah prosedur yang benar. Prosedur ini dapat kita pakai di program utama sebagai berikut: file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_rekursi2.html

2/6

10/3/13

Rekursi (2)

var

n: integer; begin readln(n); Tulis(n, 0); end. Perhatikan bahwa prosedur Tulis memiliki local variable i. Bagaimana jika fungsi ini memanggil dirinya sendiri? Apakah akan terjadi konflik? Tidak. Local variable i adalah milik sebuah pemanggilan Tulis. Jadi, jika prosedur Tulis dipanggil sebanyak 10x, ada 10 buah i yang berbeda, yang masingmasing dapat memiliki nilai yang berbeda-beda, dan tentu saja memori yang dipakai juga 10 kali lipat. Contoh: Permutasi Mari kita mengerjakan contoh masalah berikutnya: Diberikan sebuah bilangan bulat N yang cukup kecil, tuliskan bilangan-bilangan yang merupakan permutasi dari 1, 2, 3, ..., N, satu bilangan setiap baris, diurutkan dari kecil ke besar. Misalnya, untuk N = 3, program harus menuliskan 123 132 213 231 312 321 Bagaimanakah cara memecahkan masalah ini? Kita dapat mencoba membuat suatu prosedur rekursif seperti di atas: procedure Permutasi(n: integer; prefiks: longint); var i: integer; begin if (n = 0) then writeln(prefiks) else for i := 1 to max_n do Permutasi(n - 1, prefiks * 10 + i); end; tapi bagaimana cara memastikan bahwa digit yang sudah ditulis tidak ditulis lagi? Ada beberapa cara untuk memecahkan masalah ini:


3/6

10/3/13

Rekursi (2)

A. Pada saat iterasi i, jangan memakai digit-digit yang sudah ada pada prefiks. B. Tambahkan sebuah parameter baru pada prosedur Permutasi yang berisi digit-digit yang belum dipakai. C. Gunakan sebuah array global yang menyimpan digit-digit yang belum dipakai. Masing-masing cara di atas memiliki kelebihan dan kekurangannya sendirisendiri. Untuk kali ini, kita akan membahas cara C, yaitu dengan menggunakan sebuah array global. Perhatikan program berikut ini: const MAX = 9; var dipakai: array[1..MAX] of boolean; max_n: integer; procedure Permutasi(n: integer; prefiks: longint); var i: integer; begin if (n = 0) then writeln(prefiks) else for i := 1 to max_n do if (not dipakai[i]) begin dipakai[i] = true; Permutasi(n - 1, prefiks * 10 + i); dipakai[i] = false; end; end; begin // inisialisasi isi array dengan false fillchar(dipakai, sizeof(dipakai), 0); readln(max_n); Permutasi(max_n, 0); end. Array dipakai adalah array dari 9 elemen boolean, di mana dipakai[i] menyatakan apakah digit isudah dipakai atau belum di dalam prefiks pada rekursi. Seluruh elemen array ini akan diinisialisasi dengan false. Catatan file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_rekursi2.html

4/6

10/3/13

Rekursi (2)

bahwa

prosedur

fillchar(x,

count,

value) akan

menginisialisasi

sebanyak countbyte pertama pada variabel x, dengan isi value. Karena nilai byte dari falseadalah 0, maka fillchar(dipakai, sizeof(dipakai), 0); sama saja dengan for i := 1 to sizeof(dipakai) dipakai[i] := false; Perhatikan juga prosedur Permutasi yang baru. Ada dua baris yang diselipkan di sana, yaitu dipakai[i] := true; sebelum rekurens, untuk menandakan bahwa digit i tidak boleh dipakai pada pemanggilan yang lebih dalam, dan dipakai[i] := false; setelah pemanggilan fungsi selesai, untuk membebaskan digit ikembali. Kita juga menambahkan sebuah kondisi if (not dipakai[i]) agar digit selanjutnya yang akan ditulis adalah digit yang belum pernah dipakai di dalam prefiks. Local atau global? Sebetulnya ada banyak sekali cara untuk menyelesaikan masalah menulis permutasi di atas. Kita dapat membuat array dipakai tidak global, sehingga array dipakai menjadi salah satu parameter Permutasi. Namun, tidak mudah meletakkan sebuah array di daftar parameter karena ada beberapa urusan administratif yang perlu dilakukan. Selain itu, memori yang dipakai akan menjadi besar karena pada setiap pemanggilan prosedur rekursif, seluruh parameter dan local variable memerlukan memori baru. Jadi, tidak disarankan untuk meletakkan data yang terlalu besar sebagai parameter atau local variable. Sebaliknya, kita bisa saja membuat prosedur rekursif yang sama sekali tidak memiliki parameter, dan digantikan oleh variabel-variabel global, seperti ini: file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_rekursi2.html

5/6

10/3/13

Rekursi (2)

const MAX = 9; var dipakai: array[1..MAX] of boolean; max_n: integer; n: integer; prefiks: longint; procedure Permutasi; var i: integer; begin if (n = 0) then writeln(prefiks) else for i := 1 to max_n do if (not dipakai[i]) begin dipakai[i] := true; n := n - 1; prefiks := prefiks * 10 + i; Permutasi; prefiks := prefiks div 10; n := n + 1; dipakai[i] := false; end; end;

// <---- rekurens

Meskipun prosedur di atas tetap menghasilkan keluaran yang sama, dan meskipun hemat memori, tetapi penulisannya menjadi tidak rapi, bukan? Oleh karena itu, Anda perlu menentukan sendiri dengan kebijaksanaan Anda, kapan memakai global variable atau local variable (parameter).


6/6

10/3/13

TEKS : Komputasi Geometri Dasar

TEKS : Komputasi Geometri Dasar Ruang lingkup masalah geometri dalam olimpiade informatika Olimpiade informatika bukanlah olimpiade matematika. Dalam kaitannya dengan masalah geometri, yang diuji terutama adalah kemampuan memodelkan masalah geometri ke dalam bahasa pemrograman, dan pembuatan algoritma yang efisien untuk memecahkan masalah-masalah geometri. Dalam olimpiade tingkat nasional maupun internasional, masalah geometri yang dikeluarkan biasanya tidak membutuhkan pelajaran matematika yang lebih tinggi dari tingkat SMP (kelas 9). Masalah-masalah geometri dalam olimpiade mencakup geometri dalam dua dimensi. Masalah dikeluarkan secara resmi, tetapi sangat jarang akan mengasumsikan bahwa semua komponen dua dimensi.

informatika biasanya hanya geometri tiga dimensi pernah sekali. Pada artikel ini, kita geometri berada pada ruang

Artikel ini akan berisi beberapa ide-ide untuk melihat komponen masalah geometri secara komputasional. Titik

Sebuah titik dalam dapat didefinisikan oleh koordinat x dan koordinat y titik tersebut. Hal ini cukup dilakukan dengan var

x : double; y : double;

file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_geom.html

1/7

10/3/13


atau dengan cara yang lebih terstruktur: type Titik = record x : double; y : double; end; var t : Titik; Garis dan ruas garis

Garis adalah suatu entitas satu dimensi yang panjangnya tidak berhingga. Ada banyak cara mendefinisikan sebuah garis pada ruang dua dimensi, seperti dengan menggunakan dua titik, sebuah titik + sebuah gradien, dan lain-lain. Sebuah cara yang standar adalah memodelkan garis dengan parameter m dan c, di mana m adalah gradien dan c adalah koordinat y di mana sumbu y memotong garis. Contoh tipe garis yang dapat dipakai adalah: type Garis = record m : double; c : double; file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_geom.html

2/7

10/3/13


vertikal : boolean; end; Sebuah kasus khusus terjadi ketika garis tepat vertikal, yang berarti gradiennya adalah tidak terhingga. Untuk menangani kasus ini, kita menambahkan sebuah variabel boolean yang menandakan apakah garis tersebut vertikal. Jika garis tersebut vertikal, kita cukup mengabaikan nilai m, dan variabel c dapat berubah arti menjadi koordinat x di mana sumbu x berpotongan dengan garis vertikal tersebut.

Sebuah ruas garis paling sering didefinisikan dengan dua titik yang menjadi ujung-ujung ruas garis tersebut, misalnya: type RuasGaris = record x1, y1 : double; x2, y2 : double; end; Panjang sebuah ruas garis dapat didapatkan dengan rumus pitagoras biasa, yaitu: panjang := sqrt(sqr(ruas.x1 - ruas.x2) + sqr(ruas.y1 - ruas.y2)); Mencari perpotongan dua buah garis atau dua buah ruah garis bukanlah masalah yang sederhana. Anda pernah diberi tugas mencari perpotongan dua buah garis di sekolah bukan? Untuk menyuruh komputer melakukan hal yang sama, Anda perlu menuliskan cara berhitung yang Anda lakukan dalam bahasa pemrograman agar dapat dimengerti oleh komputer. Anda juga perlu memperhatikan kasus-kasus khusus, seperti kasus di mana dua garis sejajar file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_geom.html

3/7

10/3/13


(gradiennya sama) sehingga tidak ada perpotongan, kedua garis vertikal dan sejajar, kedua garis berimpit (nilai m dan c sama, atau keduanya vertikal dan nilai c sama), atau kedua garis berpotongan, di mana tidak ada yang vertikal atau salah satu bisa saja vertikal. Vektor

Vektor sangat berguna untuk memecahkan banyak masalah geometri yang lebih rumit. Secara umum, vektor dimodelkan dengan perpindahan pada koordinat x dan perpindahan pada koordinat y: type Vektor = record dx : double; dy : double; end; Jadi, vektor dapat dimengerti sebagai "perpindahan" dalam dua dimensi yang tidak tergantung pada di mana mulainya dan di mana berakhirnya. Arah vektor sudah ditentukan dengan pasti diberikan komponen perpindahanannya. Jika diketahui kedua ujung ruas garis yang membentuk vektor, cukup mudah menentukan vektor. Dalam kasus ini vektor dapat dimengerti sebagai selisih koordinat dari kedua ujung ruas garis: vektor.dx = ruas.x2 - ruas.x1; vektor.dy = ruas.xy - ruas.xy; Perhatikan bahwa ada dua buah vektor yang dapat dibuat dari sebuah ruas garis, dan kedua vektor tersebut memiliki arah yang berlawanan. Jika Anda tidak tahu arah mana yang harus dipilih untuk vektor yang Anda buat, mungkin file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_geom.html

4/7

10/3/13


Anda tidak memerlukan vektor dalam masalah tersebut dan mungkin hanya memerlukan ruas garis. Masalah-masalah yang melibatkan vektor biasanya cukup jelas menentukan arah vektor. Dengan definisi vektor seperti di atas, Anda dapat melakukan operasi-operasi pada vektor seperti penambahan, pengurangan, dot product, cross product, dan lain-lain. Panjang / norma / norm sebuah vektor adalah: panjang := sqrt(sqr(vektor.dx) + sqr(vektor.dy)); Poligon

Sebuah poligon adalah sebuah bangun tertutup, misalnya segitiga, segiempat, segilima, dll. Kita dapat mendefinisikan sebuah poligon menggunakan koordinat titik-titik penyusunnya: type Titik = record x : double; y : double; end; var

Poligon = array [1..N_TITIK] of Titik; p : Poligon;

Sebuah trik yang sering dipakai untuk menentukan luas poligon sembarang adalah rumus berikut ini. Diberikan sebuah poligon dengan titik-titik penyusun (x1, y1), (x2, y2), (x3, y3), ... (xN, yN), luas poligon tersebut adalah 0.5 * (x1y2 + x2y3 + x3y4 + ... + xN-1yN + xNy1- x2y1 - x3y2 - x4y3 - ... file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_geom.html

5/7

10/3/13


xNyN-1 - x1yN) Misalnya, luas poligon pada gambar adalah tepat 8 satuan luas. Menggunakan tipe data pecahan dalam pemrograman Masalah-masalah geometri pada umumnya memerlukan tipe data pecahan seperti double, meskipun kadang-kadang ada masalah geometri yang hanya membutuhkan tipe data bilangan bulat seperti longint. Ada beberapa pengetahuan

tentang

tipe

data

pecahan

yang

perlu

diketahui

untuk

menghindari kesalahan-kesalahan hasil program yang tidak diharapkan. Perlu diketahui bahwa tipe data pecahan adalah tipe data yang tidak akurat. Misalnya, hasil dari 1.0 / 3 * 3 mungkin saja 0.99999999998 atau 1.00000000001. Tipe data pecahan seperti double hanya akurat sampai sekitar 15 significant digit saja. Jadi, hasil dari 1e18 + 1 adalah 1e18, karena tipe data double tidak dapat merepresentasikan 1000000000000000001 karena bilangan tersebut memiliki banyak significant digit melebihi 15. Hal yang cukup problematik berkaitan dengan ketidakakuratan tipe data ini adalah pembandingan kesamaan dua buah variabel. Kebiasaan yang baik jika membandingkan kesamaan dua variable bertipe pecahan adalah dengan menggunakan epsilon, atau nilai toleransi. Misalnya: (* Global *) const Epsilon : double = 1e-4; (* artinya 0.0001 *) var

x : double; y : double;

begin x = 1.0 / 3 * 3; y = 1.0 / 7 * 7; if (abs(x - y) <= Epsilon) then begin Writeln("Sama"); end; end. Pembandingan yang dilakukan di atas memiliki toleransi sebesar 0.0001, artinya jika x dan y berbeda paling banyak sebesar Eplison, kedua variable file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_geom.html

6/7

10/3/13


tersebut dianggap bernilai sama. Tanpa melakukan hal ini, nilai ekspresi (x = y) kemungkinan besar adalah false.

file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_geom.html

7/7

10/3/13

TEKS : Kebiasaan Programming yang Baik 1

TEKS : Kebiasaan Programming yang Baik 1 Pada artikel ini, ada 4 hal yang akan dibahas, yaitu: 1. 2. 3. 4.

Indentasi dan spacing Komentar Konstanta Modularisasi

Hal-hal di atas pada dasarnya berkaitan dengan kerapihan program dan seberapa mudah program dibaca. Di dalam kompetisi OSN, sebetulnya hal-hal ini tentu tidak akan dinilai, sehingga penjelasan di dalam artikel ini tidak harus diikuti. Hal-hal ini dituliskan untuk menambah wawasan saja. Indentasi dan spacing Indentasi adalah menambahkan spasi di awal baris-baris program agar program mudah dibaca, sedangkan "spacing" adalah penambahan spasi pada kode, misalnya di antara dua parameter, di sekitar operator, dan lain-lain. Tujuannya sama, yaitu untuk membuat program lebih mudah dibaca. Contoh program tanpa indentasi dan tanpa spacing: 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. Contoh program dengan indentasi tetapi tanpa spacing: var

n:integer; i:integer; begin readln(n); for i:=1 to n do begin if(i=93)then begin writeln('ERROR'); file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_style1.html

1/4

10/3/13


break; end; if(i mod 10=0)then continue; writeln(i); end; end. Contoh program dengan indentasi dan dengan spacing: 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. Komentar Komentar tidak terlalu berguna untuk membuat program-program yang cukup pendek. Untuk program-program yang panjang, sering kali otak kita tidak mampu untuk mengingat dan memahami seluruh program, sehingga kadang-kadang kita memerlukan catatan. Untungnya, kita bisa menulis catatan di mana pun di dalam program, pada Pascal dengan tanda { ... }, (* ... *), atau //.... Contohnya: {

}

Program ini akan mengembalikan nilai faktorial dari integer yang dibaca dari input, hanya jika integer yang dibaca berada pada jangkauan 1..10

function Valid(n: integer): boolean; begin Valid := (n >= 0) and (n <= 10); end; // n tidak boleh negatif // function Faktorial(n: integer): integer; var i: integer; bil: integer; begin file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_style1.html

2/4

10/3/13


bil := 1; for i := 1 to n do bil := bil * i; Faktorial := bil; end; var

bil: integer; begin readln(bil); if (Valid(bil)) then writeln(Faktorial(bil)); else writeln('ditolak'); // cek lagi, apakah d-nya huruf besar atau kecil? end. Konstanta Konstanta adalah suatu tempat menyimpan sebuah nilai , dan nilai itu tidak dapat diubahubah selama berjalannya program. Sebuah konstanta dapat dideklarasi dengan cara yang mirip dengan cara mendeklarasi variabel. Contoh deklarasi konstanta: const maksimum = 1000; minimum = -1000; N = 2345; nama = 'Pak Dengklek'; Setelah itu, konstanta-konstanta tersebut dapat digunakan seperti variabel biasa. Namun, konstanta tidak bisa diberikan nilai baru. Konstanta memiliki banyak kegunaan, tetapi keguanaan utamanya adalah untuk menghindari menulis nilai yang sama secara berulang-ulang. Misalnya, jika Anda memiliki program: var

i: integer; begin for i := 1 to 1000 do writeln('Saya berjanji tidak akan nyontek lagi'); for i := 1 to 1000 do writeln('Saya minta maaf pada Pak Tono'); for i := 1 to 1000 do writeln('Saya minta maaf pada Ibu Tini'); for i := 1 to 1000 do writeln('Saya minta maaf pada Pak Budi'); for i := 1 to 1000 do writeln('Saya minta maaf pada Ibu Ani'); for i := 1 to 1000 do writeln('Saya minta maaf pada Pak Dengklek'); for i := 1 to 1000 do writeln('Saya minta maaf pada Ibu Ina'); end. lalu kemudian Anda disuruh menulis setiap pernyataan sebanyak 1500 kali, dan bukan 1000 kali, maka Anda harus mengganti semua 1000 dengan 1500. file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_style1.html

3/4

10/3/13


Pemakaian konstanta menghindari hal ini. Misalnya, Anda dapat menggunakan konstanta sebagai berikut: const banyak = 1500; var i: integer; begin for i := 1 to banyak do writeln('Saya berjanji tidak akan nyontek lagi'); for i := 1 to banyak do writeln('Saya minta maaf pada Pak Tono'); for i := 1 to banyak do writeln('Saya minta maaf pada Ibu Tini'); for i := 1 to banyak do writeln('Saya minta maaf pada Pak Budi'); for i := 1 to banyak do writeln('Saya minta maaf pada Ibu Ani'); for i := 1 to banyak do writeln('Saya minta maaf pada Pak Dengklek'); for i := 1 to banyak do writeln('Saya minta maaf pada Ibu Ina'); end. Dengan konstanta, jika Anda harus mengganti banyak penulisan dari 1500 menjadi angka lainnya, Anda tinggal mengganti nilai konstanta pada deklarasinya saja. Modularisasi Modularisasi adalah menstrukturisasi program sehingga terbagi menjadi bagian-bagian kecil yang lebih mudah dimengerti. Misalnya, jika Anda memiliki program yang sangat panjang, Anda dapat membagi program itu ke dalam beberapa fungsi dan beberapa prosedur yang sering digunakan, sehingga program utama menjadi lebih pendek dan lebih mudah dibaca. Namun, biasanya soal-soal OSN tidak memerlukan kode yang terlalu panjang. Sebagai contoh, sebuah program yang sangat panjang mungkin dapat disingkat dengan fungsi dan prosedur, menjadi seperti ini: var

i: integer; harga, jumlah, total, uang, kembalian: integer; begin TransaksiBaru(total); while (MasihAdaTransaksi()) begin Transaksi(harga, jumlah); TambahKeTotal(total, harga, jumlah); end; TerimaUang(uang); BeriKembalian(HitungKembalian(uang, total, HitungDiskon(total))); UcapkanTerimaKasih(); end.

file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_style1.html

4/4

10/3/13

TEKS : Winning the Contest

TEKS : Winning the Contest Kalian telah menjalani Pelatihan Jarak Jauh (PJJ) selama beberapa minggu, dan kami berharap kalian sudah jauh lebih siap menghadapi OSN daripada sebelumnya. Tetapi apa yang dinamakan siap? Ada banyak persiapan yang perlu dilakukan sebelum kontes, misalnya persiapan akademik (teori maupun praktek), mengetahui aturan main OSN, dan persiapan-persiapan lainnya. Di dalam kompetisi, suasana mungkin cukup tegang dan Anda memiliki waktu yang terbatas. Oleh karena itu, kami juga akan memberikan tips dan trik yang dapat digunakan dalam menghadapi kompetisi: 1. Online judge Biasakan diri dengan cara menggunakan online judge. Jangan memakai diperbolehkan

memori

melebihi

batas

memori

yang

Apakah format keluaran sudah persis dengan pada contoh soal? Apakah tidak ada kelebihan spasi, dan tidak lupa writeln untuk baris terakhir? 2. Penggunaan waktu Tujuan kompetisi adalah mencari skor sebanyak-banyaknya. Kerjakan soal yang mudah lebih dahulu. Jangan terjebak di satu soal yang sulit sehingga tidak ada waktu untuk mengerjakan soal lainnya. 3. Tips pemrograman Pastikan program benar lebih dahulu. Lebih baik program yang benar tetapi lambat daripada cepat tapi salah. Apakah tipe

data sudah benar? Apakah diperlukan integer?

file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_winning.html

1/2

10/3/13

TEKS : Winning the Contest

longint? Buat test case sendiri dan uji program Anda sendiri. Jika test case contoh sudah benar, belum tentu program sudah benar. Jika di soal ada batas 1 ≤ N ≤ 10000, uji program Anda untuk N = 1. Kadang-kadang program bisa salah untuk nilai masukan terkecil. 4. Fakta-fakta cepat 210 = 1024 Batas atas integer adalah sekitar 32000 Batas atas longint adalah 231-1 = sekitar 2 milyar panjang string maksimum adalah 255. Jika ingin lebih panjang dari itu, buat array of char sendiri. Dalam satu detik, komputer bisa melakukan sekitar 100 juta operasi. Mengurutkan array dengan 1 juta elemen dengan quicksort hanya memerlukan waktu 1 detik. Persiapkan diri dengan sebaik-baiknya dan selamat berjuang!

file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj_winning.html

2/2

10/3/13

Readln dan Writeln

Readln dan Writeln Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:

pjj0101.PAS / C / CPP 1 detik / test-case 16 MB Standard input (keyboard) Standard output (layar)

Sebagai perkenalan pertama dengan program Pascal, ketikanlah perintahperintah 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 varadalah 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 brsdapat 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. file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0101.html

1/2

10/3/13

Readln dan Writeln

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

file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0101.html

2/2

10/3/13

While Loop

While Loop Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran: 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 do begin 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 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0102.html

1/2

10/3/13

While Loop

CONTOH KELUARAN abc 123


2/2

10/3/13

While Loop + Counter

While Loop + Counter Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


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);


1/2

10/3/13

While Loop + Counter

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. CONTOH MASUKAN 1 2 3 CONTOH KELUARAN 6


2/2

10/3/13

Menjumlah per Kolom

Menjumlah per Kolom Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


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 masingmasing dipisahkan satu spasi. Lalu Anda diminta menjumlahkan bilanganbilangan 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

Namun,

bil1, bil2, bil3, jml1, jml2, jml3: integer; 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); file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0104.html

1/2

10/3/13

Menjumlah per Kolom

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; Pencetakan jml1, jml2, dan jml3 dalam satu baris yang sama (dengan pemisah spasi yang harus dituliskan juga karena kalau tidak maka bilanganbilangan dituliskan bersambungan!) dapat dilakukan dengan perintah writeln(jml1,' ', jml2,' ', jml3); Lakukan juga pengujian seperti pada latihan-latihan sebelumnya. CONTOH MASUKAN 123 234 CONTOH KELUARAN 357


2/2

10/3/13

Menjumlah dalam Satu Baris

Menjumlah dalam Satu Baris Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


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 := to do begin end; adalah variabel yang akan berubah harganya setiap loop dilakukan, dimulai dari harga . Setiap perulangan, harga variabel tersebut bertambah satu. Perulangan demi perulangan dilakukan hingga variabel berharga . Tentu saja harus lebih kecil atau sama dengan , 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 misalnya i. Jadi pada bagian deklarasi ditambah dengan pernyataan jbil, i: integer; Dan bagian badan program diganti dengan jml := 0; read(jbil); file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0105.html

1/2

10/3/13

Menjumlah dalam Satu Baris

for i := 1 to jbil do begin read(bil); jml := jml + bil; end; writeln(jml); 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 512345 CONTOH KELUARAN 15


2/2

10/3/13

If Then

If Then Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


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 ifthen berikut if then begin end; yang diperiksa setelah notasi 'if' adalah 'apakah bil berharga positif'. 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


1/2

10/3/13

If Then

CONTOH KELUARAN 1 4 CONTOH MASUKAN 2 0 CONTOH KELUARAN 2

CONTOH MASUKAN 3 -1 CONTOH KELUARAN 3


2/2

10/3/13

If Then, Multi Condition

If Then, Multi Condition Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


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 berisi dua kondisi yang keduanya harus benar maka Anda menuliskan kedua kondisi tersebut berurutan diperantarai oleh notasi 'and' sebagai berikut if () and () then begin end; Tentu, adalah 'apakah bil positif' dan adalah 'apakah bil bilangan genap', yang dapat diperiksa dengan memeriksa harga modulus (sisa pembagian) dari biljika 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 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). file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0107.html

1/2

10/3/13

If Then, Multi Condition

Beri nama program pjj0107 dan simpanlah dengan nama pjj0107.PAS. CONTOH MASUKAN 1 12 CONTOH KELUARAN 1 12 CONTOH MASUKAN 2 11 CONTOH KELUARAN 2


2/2

10/3/13

If Then Else

If Then Else Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


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 then begin end; Jika pada struktur if-then saat kondisi yang diperiksa tidak benar maka komputer hanya melompati untuk langsung menjalankan

selanjutnya>.

Sementara

pada

struktur if-then-else sebagai berikut. if then begin end else begin end; Jika benar maka komputer akan menjalankan lalu lompat ke dan jika tidak benar maka komputer akan menjalankan lalu ke . file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0108.html

1/3

10/3/13

If Then Else

Jadi dalam latihan ini jika kondisi yang diperiksa adalah bil > 0 maka 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 = 0sebagai berikut. 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-thenelse. 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 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0108.html

2/3

10/3/13

If Then Else

CONTOH MASUKAN 2 0 CONTOH KELUARAN 2 nol CONTOH MASUKAN 3 -2 CONTOH KELUARAN 3 negatif


3/3

10/3/13

Case

Case Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


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; file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0109.html

1/3

10/3/13

Case

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. case of : begin end; : begin end; dan seterusnya... end; Dengan struktur ini maka 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 yang jangkauan bilangannya saling tumpang tindih, program akan menjalankan yang berada pada urutan 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


2/3

10/3/13

Case

CONTOH MASUKAN 2 12345 CONTOH KELUARAN 2 puluhribuan


3/3

10/3/13

Procedure

Procedure Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


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 (); begin 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 memecahkan masalah awal:

ini

dapat

kita

gunakan

untuk

while not eof(input) do begin file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0110.html

1/2

10/3/13

Procedure

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' 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 prosedurprosedur tersebut sudah dibuatkan untuk kita, sehingga kita tinggal menggunakannya saja. Namai program tersebut dengan nama pjj0110 dan simpanlah dengan nama pjj0110.PAS'. CONTOH MASUKAN 1 12 123 CONTOH KELUARAN satuan puluhan ratusan


2/2

10/3/13

Function

Function Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


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 (): ; begin 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;


1/4

10/3/13

Function

begin readln(bil); if (n >= 0) and (n <= 10) then writeln(Faktorial(bil)) else writeln('ditolak'); end. 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 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 billagi. 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 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0111.html

2/4

10/3/13

Function

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. 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 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0111.html

3/4

10/3/13

Function

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. Namai program tersebut dengan nama pjj0111 dan simpanlah dengan nama 'pjj0111.PAS'. CONTOH MASUKAN 1 4 CONTOH KELUARAN 1 24 CONTOH MASUKAN 2 11 CONTOH KELUARAN 2 ditolak


4/4

10/3/13

Var Parameter

Var Parameter Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


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); file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0112.html

1/3

10/3/13

Var Parameter

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 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 adan b ditukarkan di dalam prosedur, sebetulnya nilai yang ditukarkan adalah nilai variabel global adan variabel global b. Untuk lebih jelasnya, meskipun kode prosedur Swap kita ganti menjadi: file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0112.html

2/3

10/3/13

Var Parameter

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. Namai program tersebut dengan nama pjj0112 dan simpanlah dengan nama 'pjj0112.PAS'. CONTOH MASUKAN 45 CONTOH KELUARAN 54


3/3

10/3/13

Break, Continue, Exit

Break, Continue, Exit Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


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. file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0113.html

1/5

10/3/13


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: 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 iberikutnya. 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, file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0113.html

2/5

10/3/13


perintah exit akan menghentikan program seketika. Namai program tersebut dengan nama pjj0113 dan simpanlah dengan nama 'pjj0113.PAS'. CONTOH MASUKAN 1 12 CONTOH KELUARAN 1 1 2 3 4 5 6 7 8 9 11 12 CONTOH MASUKAN 2 94 CONTOH KELUARAN 2 1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0113.html

3/5

10/3/13


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 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0113.html

4/5

10/3/13


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


5/5

10/3/13

Operasi String

Operasi String Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


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, abcdehalofghidiubah menjadi aehalofghi, lalu menjadi aehalosemuafghi. Keluarkan string hasil akhir, yang pada contoh ini adalah aehalosemuafghi. Untuk menyelesaikan masalah tersebut, kita perlu mengenal berbagai fungsifungsi dan prosedur-prosedur penanganan string yang disediakan oleh library Pascal yang bisa kita gunakan. (Dapat dilihat di http://community.freepascal.org:10000/docshtml/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 substrdi dalam s (karakter pertama diberi index 1). Jika tidak ada, fungsi ini akan mengembalikan 0. file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0114.html

1/4

10/3/13

Operasi String

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 smenjadi '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. Namai program tersebut dengan nama pjj0114 dan simpanlah dengan nama 'pjj0114.PAS'. CONTOH MASUKAN abcdehalofghi bcd halo semua CONTOH KELUARAN aehalosemuafghi


2/4

10/3/13

Operasi String

Masih banyak fungsi-fungsi dan berguna, yang bisa dipelajari di

prosedur-prosedur

lain yang

mungkin

http://community.freepascal.org:10000/docs-html/rtl/system/index.html Berikut ini adalah ringkasan dari beberapa fungsi yang mungkin berguna: procedure str(x: integer; var s: string); Prosedur ini akan mengubah nilai integer x menjadi string, lalu dimasukkan ke dalam variabel s. Misalnya, jika xbernilai 10, s akan menjadi bernilai '10'. function lowerCase(s: string): string; Fungsi

ini

akan menghasilkan sebuah string

seperti

s tetapi

semua

seperti

s tetapi

semua

karakternya diubah ke huruf kecil. function upCase(s: string): string; Fungsi

ini

akan menghasilkan sebuah string

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.


3/4

10/3/13

Operasi String

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); 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...).


4/4

10/3/13

Manhattan Distance

Manhattan Distance Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


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


1/1

10/3/13

Floor and Ceiling

Floor and Ceiling Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


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


1/1

10/3/13

Dua Pangkat

Dua Pangkat Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


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


1/1

10/3/13

POLA 1

POLA 1 Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Perhatikan contoh masukan dan keluaran yang diberikan, temukan polanya, lalu buatlah programnya. FORMAT MASUKAN Sebuah bilangan bulat N (0 FORMAT KELUARAN Pola berukuran N, seperti pada contoh keluaran. CONTOH MASUKAN 5 CONTOH KELUARAN * ** *** **** *****


1/1

10/3/13

POLA 2



Perhatikan contoh masukan dan keluaran yang diberikan, temukan polanya, lalu buatlah programnya. FORMAT MASUKAN Sebuah bilangan bulat N (0 FORMAT KELUARAN Pola berukuran N, seperti pada contoh keluaran. CONTOH MASUKAN 1 5 CONTOH KELUARAN 1 0 12 345 6789 01234 CONTOH MASUKAN 2 7 CONTOH KELUARAN 2 0 12 345 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0119.html

1/2

10/3/13

POLA 2

6789 01234 567890 1234567


2/2

10/3/13

POLA 3



Perhatikan contoh masukan dan keluaran yang diberikan, temukan polanya, lalu buatlah programnya. FORMAT MASUKAN Dua buah bilangan bulat N dan K (0 < N < 100 , 1 < K < 10). FORMAT KELUARAN Pola berukuran N, seperti pada contoh keluaran. CONTOH MASUKAN 1 11 3 CONTOH KELUARAN 1 1 2 * 4 5 * 7 8 * 10 11 CONTOH MASUKAN 2 11 2 CONTOH KELUARAN 2 1 * 3 * 5 * 7 * 9 * 11 CONTOH MASUKAN 3 11 5 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0120.html

1/2

10/3/13

POLA 3

CONTOH KELUARAN 3 1 2 3 4 * 6 7 8 9 * 11


2/2

10/3/13

Menghitung

Menghitung Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Pada Latihan 4 program Anda membaca beberapa baris masukan dan pada setiap baris ada tiga bilangan. Pada Latihan 10 masukan juga ada beberapa baris masukan dan pada setiap baris berisikan tiga hal: bilangan, satu karakter tunggal, dan bilangan yang masing-masing diperantarai oleh satu karakter spasi. Kedua bilangan adalah bilangan bulat yang bisa positif, negatif atau nol. String dapat berisikan tanda-tanda operator '+' atau '-' atau '*' atau '<' atau '>' atau '='. Karena program harus membaca dalam satu baris kombinasi bilangan dan tiga buah karakter, yaitu spasi, tanda, dan spasi, maka Anda harus menyebutkan satu demi satu komponen tersebut dalam perintah readln, sbb: readln(bil1, ch1, tanda, ch2, bil2); Variabel dummy ch1 dan ch2 diperlukan untuk 'membaca' karakter spasi. Disebut dummy karena setelah dibaca diabaikan. Sementara variabel tanda digunakan untuk membaca karakter tanda. Variabel bil1 dan bil2 untuk membaca kedua bilangan tersebut. Saat program membaca satu baris masukan, untuk karakter operator '+', '-', atau '*' program akan mengoperasikan kedua bilangan sesuai dengan urutan dan operator tersebut, dan memberikan keluaran hasil operasi tersebut. Misalnya, untuk masukan '100 - 50' program akan melakukan operasi 100 dikurangi 50 yang akan menghasilkan keluaran 50. Untuk karakter operator '<', '>' atau '=', program akan melakukan pemeriksaan kedua bilangan sesuai dengan urutan dan operator tersebut. Jika benar maka program akan memberikan keluaran string 'benar', jika salah memberikan keluaran 'salah'. Misalnya untuk '100 = 50' program akan memberikan keluaran 'salah' sementara untuk '100 > 50' program akan memberikan keluaran 'benar'. file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0201.html

1/2

10/3/13

Menghitung

Untuk hal ini Anda dibebaskan untuk memilih apakah menggunakan nested if-then-else atau struktur case, atau struktur lainnya. Namai program tersebut dengan nama pjj0201 dan simpanlah dengan nama pjj0201.PAS. CONTOH MASUKAN 1 100 - 50 CONTOH KELUARAN 1 50 CONTOH MASUKAN 2 100 < 50 CONTOH KELUARAN 2 salah CONTOH MASUKAN 3 -100 < -50 CONTOH KELUARAN 3 benar


2/2

10/3/13

Array

Array Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Anda diminta untuk belajar menggunakan suatu jenis variabel yang lebih kompleks yang dapat menyimpan sejumlah harga, yang dikenal dengan nama array. Variabel tersebut memiliki elemen-elemen yang masing-masing dapat menyimpan harga tersendiri. Harga-harga yang tersimpan dalam elemen-elemen array dapat diakses menggunakan indeks yang didefinisikan pada deklarasi array tersebut. Dalam Pascal indeks dapat berupa suatu jangkauan harga integer apapun, misalnya dari -5 s.d. 5 atau dari 100 s.d. 200. Tetapi untuk memudahkan berpindah ke bahasa pemrograman yang lain (seperti C, C++ atau Java) maka sebaiknya membiasakan diri agar setiap indeks yang digunakan memiliki jangkauan bilangan bulat nonnegatif yang dimulai dari 0. Suatu variabel array didefinisikan pada bagian deklarasi variabel sbb : array [<jangkauan indeks>] of <jenis data>; Aturan nama variabel array mengacu pada aturan penamaan variabel yang umum. Tipe data elemen array dapat memakai jenis-jenis data sederhana yang ada dalam Pascal seperti integer, longint, real, dll. Jangkauan indeks jika dimulai dari A s.d. B (catatan: A dan B adalah bilangan dengan A ≤ B) ditulis dengan A..B. Dengan demikian harga pada suatu elemen array tersebut dapat diakses melalui indeksnya mulai dari A, A+1, A+2, ..., B dengan menggunakan kurung siku []. Jadi misalnya array string dengan deklarasi sbb: Tabel : array[0..10] of string; Untuk menyimpan harga 'Viva TOKI' pada elemen ke 5 array ditulis Tabel[5] = 'Viva TOKI'; file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0202.html

1/3

10/3/13

Array

Sayangnya menurut aturan resmi dalam Pascal, jumlah elemen array harus dideklarasikan secara tetap, yaitu dari awal hingga akhir berjalannya program, ukuran array tersebut tidak berubah (Suatu ketika akan dibahas cara menggunakan array dengan ukuran dinamis dalam Pascal). Selain itu, hati-hati dengan Turbo Pascal versi DOS (7.0 dan sebelumnya) yang tidak mampu menyimpan array string > 256 elemen (total ukuran array > 64 KB). Dengan FreePascal untuk Windows tidak ada masalah tersebut. Program Anda harus membaca bilangan-bilangan (satu bilangan per baris masukan) namun program menghasilkan keluaran dengan urutan terbalik dari masukan. Untuk itu program Anda harus membaca seluruh baris masukan ke dalam array kemudian mencetak mundur mulai dari baris yang terakhir dibaca hingga yang pertama. Ingat: dalam latihan ini Anda harus menggunakan array, meskipun sebenarnya ada cara lain tanpa menggunakan array. Mengingat array harus berukuran tetap maka masukan dijamin tidak akan berisi lebih dari 25000 bilangan sehingga Anda deklarasikan array penyimpan integer dengan jangkauan 0..24999. Hal yang program Anda harus lakukan juga adalah menghitung jumlah bilangan saat bilangan demi bilangan dibaca. Setelah bilangan bilangan terakhir (bilangan ke-N) dibaca, pencetakan dilakukan mundur mulai dari elemen berindeks N-1 hingga 0. Jika pada Latihan 5 anda diperkenalkan dengan struktur loop for-do dengan harga iterator menaik, berikut ini kita bisa menggunakan loop for-do dengan harga iterator menurun sbb for := downto do begin end; Perbedaannya terletak pada kata 'downto' menggantikan 'to'. Ingat bahwa harus tidak lebih kecil dari . Namai program tersebut dengan nama pjj0202 dan simpanlah dengan nama pjj0202.PAS. CONTOH MASUKAN 1 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0202.html

2/3

10/3/13

Array

2 3 4 5 CONTOH KELUARAN 5 4 3 2 1


3/3

10/3/13

Matriks

Matriks Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Setelah mahir menggunakan array, Anda akan belajar menggunakan array dua dimensi yang berguna misalnya untuk menyimpan sebuah matriks. Array dua dimensi adalah array yang diakses menggunakan dua indeks. Misalnya, Tabel[a,b]adalah elemen dari array dua dimensi bernama Tabel pada baris berindeks a dan kolom berindeks b. Deklarasi array dua dimensi mirip dengan array satu dimensi, kecuali bagian <jangkauan harga indeks> berisikan dua jangkauan yang dipisahkan tanda koma (','). Misalnya Tabel: array[0..99, 0..99] of integer; adalah array dua dimensi (membentuk matriks dua dimensi) berukuran 100 x 100. Buatlah program yang dapat membaca data matriks kemudian mengeluarkan isi matriks yang telah diputar 90 derajat menurut arah jarum jam. Misalnya matriks yang dibaca 34 66 47 45

87 71 47 75

15 52 48 35

Program akan mencetak 45 47 66 34 75 47 71 87 35 48 52 15 Ukuran matriks

tidak akan lebih dari

100 x 100, jadi

Anda dapat

mendeklarasikan matriks dengan ukuran maksimum ini. Namun berhubung data tidak selalu berukuran 100 x 100, maka Anda perlu memiliki variabel file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0203.html

1/3

10/3/13

Matriks

yang mencatat berapa banyak baris dan berapa banyak kolom pada matriks. Untuk memudahkan pembacaan, pada baris pertama masukan, banyak baris dan banyak kolom diberikan sebagai dua bilangan bulat yang dipisahkan spasi. Pembacaan dua bilangan dalam satu baris dilakukan sekaligus oleh satu perintah readlnseperti pada Latihan 3. Kemudian, pada setiap baris masukan berikutnya, harga-harga matriks dapat dibaca dengan urutan baris masukan sesuai dengan urutan baris matriks, dan pada setiap baris masukan harga elemen-elemen matriks dalam satu baris dituliskan dari kiri ke kanan dengan dipisahkan satu spasi. Untuk membaca satu baris, program Anda harus membaca satu demi satu harga dengan for-loop. Agar pembacaan masih pada baris yang sama, maka jangan gunakan perintah readln, tetapi gunakan read. Jadi program Anda perlu menggunakan dua nested for loop: for loop luar untuk per baris, dan for loop dalam untuk elemen-elemen dalam satu baris. Demikian juga, saat penulisan keluaran diperlukan dua nested for loop tetapi dengan iterator yang berbeda. Jumlah baris dan jumlah kolom tidak perlu dicetak pada keluaran ini, hanya isi matriks yang terputar. Penulisan setiap elemen bukan dengan writeln tetapi dengan write, agar dapat menuliskan beberapa harga dalam satu baris. Setelah selesai menuliskan harga-harga dalam satu baris, gunakan writeln untuk turun ke baris berikutnya. Jangan lupa menyertakan satu spasi untuk memisahkan satu elemen dengan elemen berikutnya, dan jangan ada spasi yang berlebih di akhir setiap baris. Namai program tersebut dengan nama pjj0203 dan simpanlah dengan nama pjj0203.PAS. CONTOH MASUKAN 43 34 87 66 71 47 47 45 75

15 52 48 35

CONTOH KELUARAN


2/3

10/3/13

Matriks

45 47 66 34 75 47 71 87 35 48 52 15


3/3

10/3/13

Perkalian Matriks

Perkalian Matriks Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Setelah mahir menggunakan array dua dimensi, Anda diminta untuk membaca dua buah matriks, mengalikannya, dan mencetak hasilnya. Banyak kolom pada matriks pertama dijamin sama dengan banyak baris pada matriks kedua (kalau tidak tentu tidak dapat diperkalikan). Untuk latihan ini data masukan matriks mirip dengan data masukan pada Latihan 12, tetapi masukan akan berisi dua matriks. Baris pertama berisikan banyak baris dan banyak kolom matriks pertama, dilanjutkan isi matriks pertama, kemudian satu baris yang berisikan banyak baris dan banyak kolom matriks kedua, serta isi matriks kedua. Masing-masing matriks tidak akan berukuran lebih besar dari 75 x 75. Keluarannya hanya berisikan matriks hasil perkalian saja (tanpa menyebutkan jumlah baris dan jumlah kolom, seperti pada keluaran Latihan 12). Namai program tersebut dengan nama pjj0204 dan simpanlah dengan nama pjj0204.pas. Informasi Mengenai Perkalian Matriks Matriks sebagai struktur data adalah array dua dimensi, sementara sebagai entitas matematik adalah sekumpulan bilangan yang tersusun dalam nomor baris dan nomor kolom sedemikian rupa. Banyak baris biasanya disebutkan terlebih dahulu daripada banyak kolom. Misalnya, jika sebuah matriks memiliki banyak baris m dan banyak kolom n, maka matriks itu kita sebut berukuran m x n. Dalam matematika matriks A dan matriks B dapat diperkalikan. Syaratnya: jika ukuran matriks A adalah m x n, maka ukuran matriks B haruslah n x p. Matriks baru hasil perkalian, misalnya C, akan berukuran m x p. Rumus perkaliannya sebagai berikut (C[i,j] adalah elemen C pada baris ke-i dan kolom ke-j): file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0204.html

1/2

10/3/13

Perkalian Matriks

CONTOH MASUKAN 23 111 112 34 1111 1111 1112 CONTOH KELUARAN 3334 4446


2/2

10/3/13

Rotasi matriks

Rotasi matriks Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Diberikan dua buah matriks berukuran sama n x n (1 ≤ n ≤ 75). Periksalah apakah kedua matriks tersebut identik rotasional. Matriks A dan B identik rotasional jika B diputar (dirotasi) akan menghasilkan A. Putarannya tentu 0, 90, 180 atau 270 derajat (Catatan: dalam soal ini putaran matriks berlawanan arah dengan jarum jam). Misalnya matriks pertama 123 123 123 dan matriks kedua 333 222 111 Kedua matriks adalah identik rotasional karena jika matriks kedua diputar 270 derajat akan menghasilkan matriks pertama. Misalnya matriks pertama 123 123 123 dan matriks kedua 321 321 321


1/3

10/3/13

Rotasi matriks

Kedua matriks adalah identik rotasional karena jika matriks kedua diputar 180 derajat akan menghasilkan matriks pertama. Masukan adalah dari standard input dengan format yang sama dengan masukan untuk Latihan 13. Dipastikan bahwa ukuran kedua matriks sama. Jika kedua matriks bukanlah identik rotasional maka program anda menghasilkan keluaran 'tidak sama' sementara jika sama maka program anda menghasilkan keluaran besar sudut rotasi matriks kedua untuk menghasilkan matriks pertama. Jadi untuk kasus ini keluaran adalah salah satu dari 4 kemungkinan bilangan berikut: 0, 90, 180, atau 270. Dipastikan untuk setiap testcase tidak akan lebih dari satu kemungkinan jawaban. CONTOH MASUKAN 1 33 123 123 123 33 333 222 111 CONTOH KELUARAN 1 270 CONTOH MASUKAN 2 33 123 123 123 33 123 231 312 CONTOH KELUARAN 2 tidak sama


2/3

10/3/13


Rotasi matriks

3/3

10/3/13

Refleksi Matriks

Refleksi Matriks Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Diberikan dua buah matriks berukuran sama n x n (1 ≤ n ≤ 75). Periksalah apakah kedua matriks tersebut identik, atau identik refleksional, atau tidak identi sama sekali. Dua matriks disebut identik tentu jika kedua matriks persis sama. Dua matriks disebut identik refleksional jika jika salah satu adalah pencerminan dari matriks yang lain. Pencerminan bisa dengan sumbu vertikal (|), dengan sumbu horisontal (—), dengan sumbu diagonal ke kiri bawah (/), atau dengan sumbu diagonal ke kanan bawah (\). Misalnya matriks pertama 123 456 789 dan matriks kedua 789 456 123 Kedua matriks adalah identik refleksional dengan sumbu horisontal (—). Misalnya matriks pertama 123 456 789 dan matriks kedua 321 654 987 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0206.html

1/4

10/3/13

Refleksi Matriks

Kedua matriks adalah identik refleksional dengan sumbu vertikal (|). Misalnya matriks pertama 123 456 789 dan matriks kedua 147 258 369 Kedua matriks adalah identik refleksional dengan sumbu diagonal ke kanan bawah (\). Misalnya matriks pertama 123 456 789 dan matriks kedua 963 852 741 Kedua matriks adalah identik refleksional dengan sumbu diagonal ke kiri bawah (/). Masukan adalah dari standard input dengan format yang sama dengan masukan untuk Latihan 13. Dipastikan bahwa ukuran kedua matriks sama dan jumlah baris dan kolom juga sama. Jika kedua matriks bukanlah identik rotasional maka program anda menghasilkan keluaran "tidak identik" sementara jika benar-benar identik maka program anda menghasilkan "identik" sementara jika identik refleksional maka program anda menghasilkan salah satu dari keluaran berikut: "vertikal" atau "horisontal" atau "diagonal kanan bawah" atau "diagonal kiri bawah". Dipastikan juga untuk setiap testcase hanya ada satu kemungkinan jawaban.


2/4

10/3/13

Refleksi Matriks

CONTOH MASUKAN 1 33 123 456 789 33 963 852 741 CONTOH KELUARAN 1 diagonal kiri bawah CONTOH MASUKAN 2 33 123 456 789 33 123 456 789 CONTOH KELUARAN 2 identik CONTOH MASUKAN 3 33 123 456 789 33 741 852 963 CONTOH KELUARAN 3 tidak identik file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0206.html

3/4

10/3/13


Refleksi Matriks

4/4

10/3/13

Matriks Overlapping

Matriks Overlapping Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Diberikan dua buah matriks berukuran sembarang, N x M (1 ≤ N ≤ 25, 1 ≤ M ≤ 25). Catatan: jumlah baris dan jumlah kolom belum tentu sama dan kedua matriks belum tentu berukuran sama pula. Dalam latihan ini Anda memeriksa apakah kedua matriks tersebut bertumpukan (overlapping). Kedua matriks overlapping apabila kedua matriks tersebut dapat diposisikan di dunia nyata sehingga ada submatriks dari matriks pertama yang sama dengan submatriks dari matriks kedua. Ada banyak cara dua buah matriks dapat saling overlapping di dunia nyata:

Daerah yang berwarna abu-abu adalah submatriks dari kedua matriks yang saling bertumpukan. Catatan: pada gambar ke-4, sebuah matriks tepat adalah submatriks dari matriks lainnya. Program anda harus menemukan submatriks dengan sebanyak-banyaknya elemen yang overlapping dari kedua matriks yang diberikan, dan mengeluarkan banyak baris dan banyak kolom dari submatriks tersebut. Jika tidak ada yang bertumpukan maka keluarkan '0 0'. Format

masukan

untuk kedua

matriks

adalah

seperti

latihan-latihan

sebelumnya. Format keluaran adalah banyak baris dan banyak kolom submatriks yang file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0207.html

1/4

10/3/13

Matriks Overlapping

Anda temukan, dalam satu baris dipisahkan spasi. Panjang dan lebar submatriks terbesar untuk setiap test case dijamin unik. CONTOH MASUKAN 1 33 123 456 789 33 789 236 561 CONTOH KELUARAN 1 22 CONTOH MASUKAN 2 24 2112 2112 42 22 22 11 11 CONTOH KELUARAN 2 22 CONTOH MASUKAN 3 34 1111 1551 1111 45 11111 11551 11111 11111 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0207.html

2/4

10/3/13

Matriks Overlapping

CONTOH KELUARAN 3 34 CONTOH MASUKAN 4 33 123 456 789 33 123 456 788 CONTOH KELUARAN 4 00 Penjelasan Untuk masukan pertama, kedua matriks bertumpukan di submatriks berukuran 1 x 1 1 dan submatriks berukuran 1 x 3 789 serta submatriks berukuran 2 x 2 23 56 Submatriks yang terbesar adalah submatriks 2 x 2 (ada 4 elemen). Hasil keluaran untuk masukan 1, 2, dan 3 dapat digambarkan dengan diagram berikut:


3/4

10/3/13

Matriks Overlapping

Petunjuk Ada banyak cara memecahkan soal ini. Salah satu cara yang bisa dipakai adalah sebagai berikut: Bayangkan bahwa matriks pertama diletakkan di tempat tertentu dan tidak bergerak. Bayangkan bahwa matriks kedua diletakkan di sebelah kiri atas matriks pertama, tetapi tidak menyentuh matriks pertama. "Jalankanlah" matriks kedua sehingga overlapping pada submatriks 1 x 1 dengan matriks pertama, lalu overlapping pada submatriks 1 x 2, 1 x 3, dan seterusnya. Lalu matriks kedua diletakkan lagi di sebelah kiri atas matriks pertama. Matriks kedua dijalankan sehingga submatriks 2 x 1, 2 x 2, 2 x 3, dan seterusnya.

overlapping

pada

Coba semua kemungkinan (matriks kedua dijalankan terus menerus) sampai pada akhirnya, matriks kedua berada di sebelah kanan bawah matriks pertama. Jika masih belum begitu jelas, dapat didiskusikan dengan peserta lain atau pembina di forum diskusi.


4/4

10/3/13

Rata-rata

Rata-rata Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Anda sudah pernah belajar statistika? Jika diketahui sejumlah N bilangan: x1, x2, ..., xN, yang masing-masing merupakan hasil pengukuran, misalnya nilai-nilai pelajaran Y siswa-siswa di kelas anda, maka untuk mengetahui kecenderungan nilai-nilai tersebut digunakan besaran-besaran seperti: harga terkecil, harga terbesar, harga rata-rata, dsb., yang diperoleh dari perhitungan. Harga terkecil adalah salah satu dari N bilangan di atas yang mana tidak ada bilangan lain yang lebih kecil dari padanya. Harga terbesar adalah salah satu dari N bilangan di atas yang mana tidak ada bilangan lain yang lebih besar dari padanya. Harga rata-rata adalah jumlah dari N bilangan tersebut dibagi dengan N. Buatlah program yang membaca masukan dari standard input, menghitung besaran-besaran tersebut, dan menuliskan keluaran ke standard output. FORMAT MASUKAN Baris pertama berisi bilangan bulat N (1 ≤ N ≤ 10000), diikuti N buah bilangan real. Baris ke-(i+1) berisi bilangan xi (-1000000.00 ≤ xi ≤ +1000000.00) dengan dua digit di belakang tanda desimal (tanda desimal menggunakan titik mengikuti standar penulisan di Pascal). Dipastikan tidak akan ada kesalahan dalam file masukan sehingga program anda tidak perlu memeriksa adanya kesalahan penulisan file masukan. Catatan: Cara membaca bilangan real pada Pascal sama dengan cara membaca bilangan bulat. FORMAT KELUARAN file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0208.html

1/3

10/3/13

Rata-rata

Keluarkan dalam satu baris: bilangan terkecil, bilangan terbesar, dan ratarata, dipisahkan dengan satu spasi. Bilangan rata-rata dibulatkan ke dua digit di belakang tanda desimal. Pada Pascal ada perintah khusus untuk mengeluarkan bilangan real dibulatkan ke L digit di belakang tanda desimal, yaitu dengan perintah writeln(r:0:L);di mana radalah variabel bilangan real dan L adalah banyak digit di belakang tanda desimal. Untuk program ini Anda dapat menggunakan writeln(r:0:2);. CONTOH MASUKAN 1 10 297536.26 526260.62 828177.56 -45559.92 978715.10 383672.24 467737.00 67692.93 -765057.71 790913.04 CONTOH KELUARAN 1 -765057.71 978715.10 353008.71 CONTOH MASUKAN 2 30 -810984.36 -579222.13 -117867.17 849146.53 -109313.71 852713.84 925273.01 -471109.60 -344732.29 806856.12 556582.16 616013.89 295053.48 142864.77 -502461.22 -248941.25 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0208.html

2/3

10/3/13

Rata-rata

-429372.21 -441792.48 -421294.55 888891.92 230231.19 -476848.18 -703358.42 739601.31 47096.13 953740.58 -891076.69 -841539.26 -334396.20 317560.98 CONTOH KELUARAN 2 -891076.69 953740.58 16577.21


3/3

10/3/13

SDS

SDS Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Dalam soal pjj0208 ada besaran penting yang tertinggal, yaitu simpangan baku sampel. Dari N bilangan: x1, x2, ..., xN, yang masing-masing merupakan hasil pengukuran, harga simpangan baku sampel didefinisikan sebagai

Anda tidak perlu menyimpan seluruh data dalam memori karena penghitungannya dapat dilakukan seiring pembacaan data. Untuk itu anda perlu variabel pembantu yang menyimpan jumlah xi2 dari semua xi yang telah dibaca. Setelah seluruh data terbaca barulah dilakukan penghitungan sesuai dengan rumus tersebut. Untuk tugas ini, tambahkanlah penghitungan simpangan baku sampel pada program sebelumnya. FORMAT MASUKAN Baris pertama berisi bilangan bulat N (1 ≤ N ≤ 10000), diikuti N buah bilangan real. Baris ke-(i+1) berisi bilangan xi (-1000000.00 ≤ xi ≤ +1000000.00) dengan dua digit di belakang tanda desimal (tanda desimal menggunakan titik mengikuti standar penulisan di Pascal). Dipastikan tidak akan ada kesalahan dalam file masukan sehingga program anda tidak perlu memeriksa adanya kesalahan penulisan file masukan. FORMAT KELUARAN Keluarkan dalam satu baris: bilangan terkecil, bilangan terbesar, rata-rata, file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0209.html

1/3

10/3/13

SDS

dan simpangan baku sampel, dipisahkan dengan satu spasi. Rata-rata dan simpangan baku sampel dibulatkan ke dua digit di belakang tanda desimal. CONTOH MASUKAN 1 10 297536.26 526260.62 828177.56 -45559.92 978715.10 383672.24 467737.00 67692.93 -765057.71 790913.04 CONTOH KELUARAN 1 -765057.71 978715.10 353008.71 510618.90 CONTOH MASUKAN 2 30 -810984.36 -579222.13 -117867.17 849146.53 -109313.71 852713.84 925273.01 -471109.60 -344732.29 806856.12 556582.16 616013.89 295053.48 142864.77 -502461.22 -248941.25 -429372.21 -441792.48 -421294.55 888891.92 230231.19 -476848.18 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0209.html

2/3

10/3/13

SDS

-703358.42 739601.31 47096.13 953740.58 -891076.69 -841539.26 -334396.20 317560.98 CONTOH KELUARAN 2 -891076.69 953740.58 16577.21 607823.72


3/3

10/3/13

Bilangan Prima

Bilangan Prima Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Anda seharusnya sudah tahu apakah bilangan prima itu. Singkatnya bilangan prima adalah bilangan bulat lebih dari 1 yang tidak dapat dibagi menjadi bilangan bulat lagi oleh bilangan bulat lain kecuali oleh dirinya sendiri. Contoh bilangan prima: 2, 3, 5, 7, 11, 13, 17, dst. Misalnya, 9 bukan bilangan prima karena 9 dapat dibagi 3. Apakah -5 bilangan prima? Menurut definisi di atas, bilangan prima adalah bilangan bulat positif, sehingga -5 bukan prima. Buatlah program yang dapat memeriksa apakah suatu bilangan bulat sembarang (-32000 < bilangan < 32000) yang diberikan adalah bilangan prima atau bukan. Program anda akan membaca masukan yang berisi sejumlah baris yang masing-masing baris berisi bilangan yang akan diperiksa. Untuk setiap baris masukan program akan mencetak keluaran 'YA' jika masukan adalah prima atau 'TIDAK' jika masukan bukan prima. Jadi, untuk setiap baris masukan terdapat satu baris keluaran dengan urutan masukan dan keluaran bersesuaian. Note: Ada banyak cara (algoritma) untuk memeriksa apakah suatu bilangan prima. Namun untuk sekarang Anda boleh menggunakan cara ini: Jika bilangan itu adalah A maka anda dapat memeriksa apakah A dapat dibagi oleh setiap bulangan bulat mulai dari 2 sampai dengan trunc(sqrt(A)). (Cara lain yang terkenal dikenal dengan nama 'The Sieve' yaitu singkatan dari 'The Sieve of Erastosthenes'. Suatu waktu akan dijelaskan cara bekerja algoritma tersebut.) CONTOH MASUKAN 23 -7 9000 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0210.html

1/2

10/3/13

Bilangan Prima

1 CONTOH KELUARAN YA TIDAK TIDAK TIDAK


2/2

10/3/13

Faktor Bilangan

Faktor Bilangan Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Buatlah program untuk menemukan faktor-faktor dari suatu bilangan bulat. Faktor-faktor suatu bilangan bulat N adalah bilangan-bilangan bulat positif yang habis membagi N. Misalnya, faktor dari 24 adalah 24, 12, 8, 6, 4, 3, 2, dan 1. FORMAT MASUKAN Baris pertama berisi sebuah bilangan bulat N (1 ≤ N ≤ 1000000). FORMAT KELUARAN Keluarkan faktor-faktor dari N, satu bilangan pada setiap baris, terurut dari besar ke kecil. CONTOH MASUKAN 1 24 CONTOH KELUARAN 1 24 12 8 6 4 3 2 1 CONTOH MASUKAN 2 9 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0211.html

1/2

10/3/13

Faktor Bilangan

CONTOH KELUARAN 2 9 3 1


2/2

10/3/13

Faktor Prima

Faktor Prima Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Setiap bilangan bulat positif yang lebih besar daripada 1 adalah hasil perkalian sejumlah bilangan prima. Tepatnya, setiap bulangan bulat positif yang lebih besar daripada 1 adalah hasil perkalian dari pemangkatan sejumlah bilangan prima. Misalnya, 7 = 7, 20 = 22 x 5, dan 75 = 3 x 52. Diberikan suatu bilangan bulat positif N, dapatkah anda menemukan bilangan-bilangan prima a1, a2, ..., ak dan pangkat-pangkatnya, b1, b2, ..., bk, sehingga N = a1^b1 x a2^b2 x ... x ak^bk? FORMAT MASUKAN Baris pertama berisi sebuah bilangan bulat N (1 ≤ N ≤ 1000000). FORMAT KELUARAN Keluaran harus memiliki format a1^b1 x a2^b2 x ... x ak^bk. Bilangan prima a1, a2, ..., ak harus terurut dari kecil ke besar. Tanda pangkat diwakili dengan tanda ^ tanpa spasi, dan tanda kali diwakili oleh huruf x kecil, diawali dan diikuti oleh sebuah spasi. Jika suatu pangkat bernilai 1, cukup ditulis faktornya saja. CONTOH MASUKAN 1 75 CONTOH KELUARAN 1 3 x 5^2


1/2

10/3/13

Faktor Prima

CONTOH MASUKAN 2 1000 CONTOH KELUARAN 2 2^3 x 5^3 CONTOH MASUKAN 3 20 CONTOH KELUARAN 3 2^2 x 5 CONTOH MASUKAN 4 7 CONTOH KELUARAN 4 7


2/2

10/3/13

PrimaPrima

PrimaPrima Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Jika A dan B adalah bilangan prima, apakah AB (A ditempelkan dengan B) juga prima? Bisa ya bisa tidak. Jika A = 2 dan B = 3, 23 juga prima. Namun jika A = 2 dan B = 5, 25 bukan prima. Diberikan dua buah bilangan bulat, M dan N, Anda diminta untuk mencari pasangan-pasangan bilangan-bilangan prima A dan B (M ≤ A, B ≤ N) sehingga AB (A ditempelkan dengan B) juga prima. Secara manual ini adalah pekerjaan yang melelahkan, jadi biarlah komputer yang akan mencarinya. Tapi komputer kan benda yang bodoh. Dia tidak dapat menghitung sendiri kecuali kalau Anda buatkan program untuknya agar dia dapat melakukannya untuk Anda. FORMAT MASUKAN Baris pertama berisi dua bilangan bulat, M dan N (2 ≤ M ≤ N ≤ 10000). Untuk mengurangi running time program, dibatasi (N - M) ≤ 50. FORMAT KELUARAN Keluarkan pasangan-pasangan bilangan prima yang memenuhi syarat di atas, satu pasang setiap baris dengan kedua bilangan prima dipisahkan sebuah spasi. Jika tidak ada pasangan yang memenuhi, keluarkan 'TIDAK ADA'. Untuk memudahkan server memeriksa (maklum servernya bodoh), urutkan pasangan-pasangan tersebut, sehingga bilangan pertama terurut menaik, dan untuk bilangan pertama yang sama, bilangan kedua terurut menaik. CONTOH MASUKAN 1 2 10 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0213.html

1/2

10/3/13

PrimaPrima

CONTOH KELUARAN 1 23 37 53 73 CONTOH MASUKAN 2 4 10 CONTOH KELUARAN 2 TIDAK ADA CONTOH MASUKAN 3 950 1000 CONTOH KELUARAN 3 953 977 953 983 971 977 977 971 997 991


2/2

10/3/13

Saling Silang

Saling Silang Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Suatu permainan iseng-iseng asah otak berikut mungkin pernah anda temukan. Diberikan matriks yang setiap selnya berisikan satu huruf kapital. Pada matriks terdapat sejumlah kata yang karakter-karakternya tersusun secara horisontal dari kiri ke kanan, atau dari kanan ke kiri, atau vertikal dari atas ke bawah, atau dari bawah ke atas, atau diagonal dari kiri atas ke kanan bawah, atau dari kanan bawah ke kiri atas, atau dari kiri bawah ke kanan atas, atau dari kanan atas ke kiri bawah Buatlah program yang diberikan suatu matriks dan sejumlah kata, menentukan kata-kata mana saja yang ada di dalam matriks tersebut. FORMAT MASUKAN Baris pertama berisi dua buah bilangan bulat yang merupakan banyak baris dan kolom matriks, R dan C (2 ≤ R, C ≤ 100). R baris selanjutnya berisi matriks masukan. Pada setiap baris, huruf-hurus kapital dipisahkan dengan sebuah spasi. Baris berikutnya berisi sebuah bilangan bulat N (1 ≤ N ≤ 100) yang menyatakan banyak kata yang ingin dicari. N baris berikutnya berisi katakata yang ingin dicari. FORMAT KELUARAN


1/3

10/3/13

Saling Silang

Keluarkan satu baris keluaran untuk setiap dari N kata yang dicari, sesuai urutan. Pada setiap baris keluaran, keluarkan kata yang dicari, lalu karakter 'Y' jika kata yang dimaksud ditemukan dalam matriks, dan 'T' jika tidak ditemukan. CONTOH MASUKAN 65 BABKD UNIDK LDULO UITRN HNAGA FIUTG 6 BULUH UDIK HITAM ANDINI LIAT ARUN CONTOH KELUARAN BULUH Y UDIK Y HITAM T ANDINI Y LIAT Y ARUN Y Penjelasan Diagram untuk kasus di atas:


2/3

10/3/13


Saling Silang

3/3

10/3/13

Prima Ke-K?

Prima Ke-K? Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Dalam soal ini, yang perlu Anda lakukan adalah menjawab pertanyaan "Berapakah bilangan prima ke-K?". Anda akan diberikan masukan yang berisi N buah K, jawablah N pertanyaan tersebut. FORMAT MASUKAN Baris pertama berisi sebuah bilangan bulat N (1 ≤ N ≤ 20000). N baris berikutnya berisi masing-masing sebuah bilangan K (1 ≤ K ≤ 77777). FORMAT KELUARAN N baris berisi masing-masing sebuah bilangan yang merupakan jawaban dari "Berapakah bilangan prima ke-K?". CONTOH MASUKAN 4 1 3 5 2 CONTOH KELUARAN 2 5 11 3 Penjelasan Anda ditanya "Berapakah bilangan prima ke-1, ke-3, ke-5, dan ke-2?", file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0215.html

1/2

10/3/13

Prima Ke-K?

tentu jawabannya adalah 2, 5, 11, dan 3. Untuk menyelesaikan soal ini, Anda mungkin perlu membaca dan mempelajari Teknik Eratosthenes Sieve.


2/2

10/3/13

Faktor Persekutuan Terbesar

Faktor Persekutuan Terbesar Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


GCD (Greatest Common Divisor) atau FPB (Faktor Persekutuan Terbesar) dari dua buah bilangan bulat A dan B adalah bilangan bulat terbesar yang membagi A dan membagi B. Misalnya, GCD dari 12 dan 20 adalah 4. GCD dari dua buah bilangan dapat dicari secara manual. Namun, ada cara yang lebih efisien menggunakan definisi rekursif sebagai berikut: GCD dari 0 dan suatu bilangan sembarang adalah bilangan sembarang tersebut. GCD dari A dan B sama dengan GCD dari B dan (A mod B). Gunakan definisi rekursif ini untuk membuat sebuah fungsi rekursif yang efisien untuk menghitung GCD dari dua buah bilangan, dan pakailah di dalam program Anda. Anda akan diberikan N (1 ≤ N ≤ 10000) pasang bilangan bulat yang berada dalam jangkauan 0 sampai dengan 1000000000. Keluarkan GCD dari setiap pasang bilangan pada setiap baris. FORMAT MASUKAN Baris pertama berisi N. Selanjutnya, baris ke-(i + 1) berisi dua bilangan bulat dipisahkan sebuah spasi, Ai dan Bi (0 ≤ Ai, Bi ≤ 1000000000). FORMAT KELUARAN Keluaran terdiri atas N baris. Baris ke-i berisi GCD dari Ai dan Bi. CONTOH MASUKAN 2 12 20 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0301.html

1/2

10/3/13

Faktor Persekutuan Terbesar

12 CONTOH KELUARAN 4 1


2/2

10/3/13

Penjumlahan Pecahan

Penjumlahan Pecahan Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Persoalan ini adalah persoalan matematika sederhana yang biasa dikerjakan oleh pelajar SD. Anda akan diberikan dua buah bilangan pecahan (tidak ada pembilang maupun penyebut yang bernilai 0), jumlahkanlah lalu cetak hasilnya dalam bentuk yang paling sederhana (FPB dari pembilang dan penyebutnya adalah 1). FORMAT MASUKAN Baris pertama berisi dua buah bilangan bulat dipisahkan spasi yang merupakan pembilang dan penyebut bilangan pecahan pertama. Baris kedua berisi dua buah bilangan bulat dipisahkan spasi yang merupakan pembilang dan penyebut bilangan pecahan kedua. Baik pembilang maupun penyebut dalam masukan (input) tidak akan melebihi batasan integer 64 bit (int64 di PASCAL), begitu pula pembilang dan penyebut dalam keluaran (output). FORMAT KELUARAN Sebuah baris berisi dua buah bilangan bulat dipisahkan spasi, pembilang lalu penyebut hasil penjumlahan dari bilangan pertama dan bilangan kedua pada masukan. CONTOH MASUKAN 1 23 45 CONTOH KELUARAN 1 22 15


1/2

10/3/13

Penjumlahan Pecahan

CONTOH MASUKAN 2 24 38 CONTOH KELUARAN 2 78


2/2

10/3/13

Hitung Bebek

Hitung Bebek Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Bebek-bebek Pak Dengklek sungguh pintar, mereka sudah mengerti penjumlahan dengan sangat baik. Dengan bangga, bebek-bebek sering mempertunjukkan keahliannya kepada Pak Dengklek. Keunikan dari bebekbebek Pak Dengklek, mereka sangat dan hanya suka pada angka 1 dan 2. Sehingga saat Pak Dengklek meminta bebek-bebek untuk menuliskan sebuah angka, bebek-bebek akan menuliskan angka tersebut dengan untaian angka 1 dan 2 yang kemudian dijumlahkan. Misalnya, jika Pak Dengklek meminta bebek-bebek untuk menuliskan angka 4. Bebek-bebek dapat menulis 1111 (1+1+1+1=4), 112, 121, 211, atau 22. Jumlahnya ada 5 cara yang dapat bebek-bebek gunakan untuk menulis angka 4. Dalam soal ini, Anda akan diberikan sebuah angka, hitunglah berapa banyak cara yang dapat bebek-bebek gunakan untuk menulis angka tersebut. FORMAT MASUKAN Sebuah bilangan bulat N (1 ≤ N ≤ 1000000). FORMAT KELUARAN Sebuah bilangan bulat yang merupakan jumlah cara yang dapat bebekbebek gunakan untuk menulis angka N. Bilangan keluaran ini bisa jadi sangat besar (melebihi batas variabel dasar di PASCAL), maka jika bilangan tersebut lebih besar dari 999999, Anda cukup mencetak 6 digit terakhir dari bilangan tersebut. CONTOH MASUKAN 1 5


1/2

10/3/13

Hitung Bebek

CONTOH KELUARAN 1 8 CONTOH MASUKAN 2 3 CONTOH KELUARAN 2 3


2/2

10/3/13

Pangkat Besar

Pangkat Besar Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Soal ini pada dasarnya adalah soal perpangkatan sederhana. Anda akan diberikan dua buah bilangan bulat A dan B, hitunglah berapa A^B. FORMAT MASUKAN Sebuah baris berisi dua buah bilangan bulat dipisahkan spasi, yakni A dan B (1 ≤ A,B ≤ 1000000000). FORMAT KELUARAN Sebuah baris berisi hasil A^B. Bilangan keluaran ini bisa jadi sangat besar (melebihi batas variabel dasar di PASCAL), maka jika bilangan tersebut lebih besar dari 999999, Anda cukup mencetak 6 digit terakhir dari bilangan tersebut. CONTOH MASUKAN 1 38 CONTOH KELUARAN 1 6561 CONTOH MASUKAN 2 99 CONTOH KELUARAN 2 420489 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0304.html

1/2

10/3/13


Pangkat Besar

2/2

10/3/13

Menggambar Pegunungan

Menggambar Pegunungan Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Pak Dengklek ingin mengisi waktu luangnya dengan menggambar pemandangan alam. Namun, dia sedang berada di laboratorium komputer dan di sana tidak ada kertas dan pensil. Oleh karena itu, dia memutuskan untuk menggambar pegunungan dengan program komputer. Pegunungan yang ingin digambar Pak Dengklek memiliki aturan sebagai berikut: Pegunungan level 1 memiliki bentuk seperti ini: * Pegunungan level 2 memiliki bentuk seperti ini: * ** * Pegunungan level 3 memiliki bentuk seperti ini: * ** * *** * ** * dan seterusnya. Secara umum, pegunungan level N untuk N ≥ 2 diawali dengan pegunungan level N - 1, dilanjutkan dengan satu baris berisikan N buah tanda '*', dan diakhiri dengan pegunungan level N - 1. Bantulah

Pak

Dengklek

membuat


program

yang

dapat

menggambar 1/2

10/3/13

Menggambar Pegunungan

pegunungan yang memiliki level N (1 ≤ N ≤ 10). FORMAT MASUKAN Baris pertama berisi sebuah bilangan bulat N. FORMAT KELUARAN Keluarkan gambar pegunungan yang memiliki level N. CONTOH MASUKAN 4 CONTOH KELUARAN * ** * *** * ** * **** * ** * *** * ** *


2/2

10/3/13

Permutasi Zig-zag

Permutasi Zig-zag Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Pada artikel "Rekursi (2)" sudah dibahas cara menulis permutasi dari angkaangka 1, 2, ..., N. Kali ini, Anda diminta untuk menuliskan semua bilangan yang terdiri atas N (1 ≤ N ≤ 9) digit dan digit-digitnya merupakan permutasi dari 1, 2, ..., N, dan mengikuti "aturan zig-zag" sebagai berikut: Untuk setiap tiga digit yang berurutan, salah satu kasus ini harus dipenuhi: Digit yang di tengah harus lebih kecil dari kedua digit lainnya. Digit yang di tengah harus lebih besar dari kedua digit lainnya. Misalnya, bilangan 1423 memenuhi aturan zig-zag di atas, tetapi bilangan 1432 tidak memenuhi aturan tersebut. Jika N < 3, aturan zig-zag tidak perlu dipenuhi. FORMAT MASUKAN Baris pertama berisi sebuah bilangan bulat N. FORMAT KELUARAN Keluarkan semua kemungkinan bilangan yang merupakan permutasi dari digit-digit 1, 2, ..., N dan memenuhi aturan zig-zag, satu bilangan setiap baris. Keluaran harus terurut dari kecil ke besar. CONTOH MASUKAN 3 CONTOH KELUARAN file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0306.html

1/2

10/3/13

Permutasi Zig-zag

132 213 231 312


2/2

10/3/13

Quadtree 1: Pengkodean

Quadtree 1: Pengkodean Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Pernah dengar istilah quadtree? Quadtree adalah suatu struktur data yang dapat dipergunakan untuk mengkodekan isi suatu binary image (citra biner). Kita langsung saja melihat contoh berikut. Perhatikan matriks biner (setiap elemen berisi 2 kemungkinan harga) berikut (bagian berharga 0 diberi warna putih dan bagian berharga 1 diberi warna abu-abu).

Kalau kita membagi matriks dalam empat kuadran yang sama besarnya, maka kita akan mendapatkan kuadran kiri atas berisi harga-harga yang sama (homogen), sementara kuadran lain tidak homogen. Untuk setiap kuadran yang tidak homogen, dilakukan pembagian lebih lanjut menjadi 4 kuadran yang lebih kecil, dan seterusnya, sehingga akan terbentuk submatriks-submatriks homogen sebagai berikut.


1/5

10/3/13


Tentu, kuadran terkecil (tidak dapat dipecah lagi) yang mungkin adalah elemen matriks itu sendiri, dan kuadran terbesar yang homogen adalah seluruh matriks tersebut, seandainya semua elemen berharga sama. Karena proses pemecahan ini selalu membagi matriks menjadi 4 bagian yang sama besar, maka matriks haruslah berbentuk bujur sangkar berukuran 2p x 2p. Sekarang kita melakukan pengkodean atas Aturan kode suatu kuadran:

kuadran-kuadran tersebut.

Digit pertama menyatakan harga dari kuadran yang homogen tersebut. Karena elemen-elemen matriks berharga biner maka hanya ada dua harga: 0 atau 1. Digit-digit berikutnya menyatakan kode lokasi sebagai berikut: Pada sekali pembagian menjadi 4 kuadran, masing-masing kuadran dinomori sbb: 0 untuk kiri atas, 1 untuk kanan atas, 2 untuk kiri bawah, dan 3 untuk kanan bawah. Pembagian berikutnya sama dengan pembagian sebelumnya, dan digit yang baru dituliskan pada posisi setelah digit sebelumnya. Misalnya, pada contoh di atas, kuadran berkode 1 dipecah ke dalam kuadran berkode 10 dan 11 yang homogen berharga 0, dan kuadran berkode 12 dan 13 yang homogen berharga 1. Jadi dengan aturan pengkodean ini contoh matriks di atas dapat dikodekan seperti pada gambar berikut.

Buatlah program yang mengeluarkan kode-kode setiap kuadran homogen berharga 1 dari matriks biner yang diberikan.


2/5

10/3/13


FORMAT MASUKAN Baris pertama berisikan dua integer R dan C yang dipisahkan spasi. Bilangan R menyatakan banyak baris matriks dan bilangan C menyatakan banyak kolom matriks (2 ≤ R ≤ 128, dan 2 ≤ C ≤ 128). R baris berikutnya berisi baris-baris matriks tersebut, dengan baris-baris pada input sesuai urutan baris pada matriks. Dalam satu baris, elemen-elemen berharga biner dituliskan dari kiri ke kanan sesuai urutan pda matriks, dipisahkan dengan spasi. Jika ukuran matriks tidak tepat berharga 2p x 2p, Anda perlu memperluas matriks tersebut ke ukuran 2p x 2p dengan nilai p terkecil, dengan menambahkan baris-baris berharga 0 di bawah matriks, dan kolom-kolom berharga 0 di sebelah kanan matriks semula. FORMAT KELUARAN Keluaran hanya berupa kode-kode dari kuadran-kuadran homogen berharga 1, dengan masing-masing kode dituliskan pada baris berbeda dan terurut secara leksikografi (urutan dalam kamus). Ingat bahwa kuadran yang sudah homogen tidak boleh dipecahkan. Untuk menandakan akhir keluaran, cetak string 'END' setelah kode kuadran terakhir. CONTOH MASUKAN 1 88 00000000 00000000 00001111 00001111 00011111 00111111 00111100 00111000 CONTOH KELUARAN 1 112 113 1211 1212 1213 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0307.html

3/5

10/3/13


123 130 131 1320 1321 1322 END CONTOH MASUKAN 2 35 00000 00000 00000 CONTOH KELUARAN 2 END CONTOH MASUKAN 3 44 1111 1111 1111 1111 CONTOH KELUARAN 3 1 END CONTOH MASUKAN 4 33 111 111 111 CONTOH KELUARAN 4 10 110 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0307.html

4/5

10/3/13


112 120 121 130 END Penjelasan Pada contoh masukan 2, tidak ada kuadran berharga 1 yang akan dioutputkan sehingga keluarannya hanya string 'END' saja. Pada contoh masukan 3, matriks yang hanya berisi harga-harga 1 dan berukuran tepat 2p x 2p, sehingga keluaran hanya terdiri dari sebuah kode '1' dan 'END'. Kode '1' menandakan bahwa kode lokasi adalah string kosong (tidak ada pembagian menjadi 4 kuadran). Namun, hal tersebut tidak terjadi pada matriks yang tidak berukuran 2p x 2p. Pada contoh masukan 4, matriks harus dijadikan berukuran 4 x 4 dan kolom terkanan dan baris terbawah diisi 0. Maka terbentuklah 6 kuadran berharga 1 dan 7 kuadran berharga 0.


5/5

10/3/13

Quadtree 2: Decode

Quadtree 2: Decode Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Jika pada Quadtree 1 anda diminta untuk mengkodekan matriks biner berukuran 2p x 2p menjadi sejumlah kode quadtree, berikut ini anda diminta untuk melakukan kebalikannya. Diberikan sejumlah kode quadtree, dapatkan data matriks biner semula. FORMAT MASUKAN Masukan terdiri atas sejumlah kode-kode quadtree untuk kuadran-kuadran homogen berharga 1, dituliskan satu kode setiap baris, terurus secara leksikografi (urutan pada kamus), diikuti dengan 'END'. Baris selanjutnya berisikan dua bilangan bulat R dan C (2 ≤ R ≤ 128, dan 2 ≤ C ≤ 128). dipisahkan oleh sebuah spasi, yang menyatakan bahwa matriks semula berukuran R baris x C kolom. Dijamin bahwa setiap kode mengkodekan secara unik kumpulan elemen matriks tersebut (tidak ada yang overlap) dan konsisten (tidak ada yang tidak mungkin). FORMAT KELUARAN Keluarkan R baris, setiap baris mewakili baris pada matriks sesuai urutan. Setiap baris berisi elemen-elemen matriks pada baris tersebut sesuai urutan, dipisahkan spasi. Ingat bahwa tidak boleh ada spasi di akhir setiap baris. CONTOH MASUKAN 1 112 113 1211 1212 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0308.html

1/3

10/3/13

Quadtree 2: Decode

1213 123 130 131 1320 1321 1322 END 88 CONTOH KELUARAN 1 00000000 00000000 00001111 00001111 00011111 00111111 00111100 00111000 CONTOH MASUKAN 2 END 35 CONTOH KELUARAN 2 00000 00000 00000 CONTOH MASUKAN 3 1 END 44 CONTOH KELUARAN 3 44 1111 1111 1111 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0308.html

2/3

10/3/13

Quadtree 2: Decode

1111 CONTOH MASUKAN 4 10 110 112 120 121 130 END 44 CONTOH KELUARAN 4 1110 1110 1110 0000


3/3

10/3/13

Jawbreaker 1: Menghitung Skor

Jawbreaker 1: Menghitung Skor Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Anda mungkin pernah melihat permainan komputer berikut ini, bahkan mungkin pernah memainkannya. Di depan anda terdapat sejumlah bola dari berbagai warna, dengan banyak warna yang berbeda adalah tertentu. Bolabola tersebut tersusun dalam suatu matriks M x N dan ditempatkan secara acak dalam matriks. Pemain dapat "mengambil" sejumlah bola berwarna sama sekaligus (minimal dua bola) asalkan bola-bola tersebut tersebut dalam satu rangkaian. Bola-bola dalam satu rangkaian didefinisikan sbb: '*' adalah bola yang akan dipilih (atau ikut terpilih) dan '+' adalah bola yang berwarna sama dengan '*'. Jika '+' berada tepat di bawah atau di samping kiri atau di samping kanan atau di atas '*', maka '+' ikut terpilih dan diganti dengan tanda '*'. Begitu seterusnya sampai tidak ada lagi tanda '+' yang dapat diganti dengan tanda '*'. Jika Anda memperoleh T bola dalam satu pengambilan maka Anda mendapat nilai T(T-1). Karena paling sedikit ada dua bola yang Anda ambil sekaligus maka tentu nilai minimal yang didapat adalah 2. Berikut ini contoh-contohnya: Contoh dengan dua rangkaian bola

'*' adalah Semua yang ikut bola yang terpilih bertanda '*', dipilih dan yang tidak '+'

Nilai yang didapatkan

-------+++---+-++------+-

-------*++---+-++------+-

-------***---*-**------+-

30

----++-+++----++---

----++-+++----++---

----++-***----**---


56 1/4

10/3/13


---+++-

---*++-

---***-

-+-----+++---++-++--++-+-

-+-----+++---++-+*--++-+-

-+-----+++---++-**--++-*-

6

Dalam permainan komputer yang sebenarnya, tentu ada cerita selanjutnya, yaitu bahwa Anda harus memilih bola yang lain lagi dan mengambil sekumpulan bola sehingga anda bisa mendapatkan total nilai sebesarbesarnya. Pengambilan tersebut mengubah struktur bola pada matriks. Lalu Anda melakukan pengambilan berikutnya, dan seterusnya hingga tidak ada lagi bola yang dapat diambil. Kali ini Anda hanya diminta untuk membuat program yang melakukan penghitungan nilai yang akan Anda peroleh berdasarkan data susunan matriks bola dan sebuah bola yang dipilih. FORMAT MASUKAN Baris pertama berisi dua bilangan M dan N (4 ≤ M, N ≤ 25) yang dipisahkan spasi yang menyatakan jumlah baris dan jumlah kolom. M baris berikutnya berisi susunan bola, dan pada setiap baris terdapat N bilangan bulat yang dapat berharga 1 sampai dengan 5 (yang menyatakan warna bola), dipisahkan oleh sebuah spasi. Baris terakhir berisi 2 buah bilangan, B dan K (0 ≤ B ≤ M - 1 dan 0 ≤ K ≤ N - 1), yang menyatakan nomor baris dan nomor kolom dari bola yang akan dipilih. Kolom pertama dan baris pertama diberi nomor 0, sehingga bola di pojok kiri atas memiliki lokasi (0, 0) dan di pojok kanan bawah memiliki lokasi (M - 1, N - 1). FORMAT KELUARAN Program anda hanya mengoutputkan satu angka, yaitu nilai sebagai hasil pemilihan bola pada data masukan tersebut. Jika bola yang dipilih tidak memiliki rentetan karena tidak ada bola yang berwarna sama di sekitarnya maka anda mengoutputkan bilangan 0. CONTOH MASUKAN 1 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0309.html

2/4

10/3/13


47 3342435 2111355 3141145 3343315 11 CONTOH KELUARAN 1 30 CONTOH MASUKAN 2 47 1111221 1222111 3322444 3332224 33 CONTOH KELUARAN 2 56 CONTOH MASUKAN 3 47 1111111 2555222 3551551 3355151 25 CONTOH KELUARAN 3 6 Penjelasan Semua contoh masukan sesuai dengan contoh-contoh yang diberikan di deskripsi soal.


3/4

10/3/13


Tips Program dapat menggunakan sebuah array global dua dimensi, yang menyimpan apakah setiap posisi (x, y) sudah pernah dikunjungi atau belum.


4/4

10/3/13

Jawbreaker 2: Cari Terbesar

Jawbreaker 2: Cari Terbesar Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Setelah berhasil menyelesaikan soal Jawbreaker pertama, pada soal ini, Anda berusaha mendapatkan nilai terbesar dari semua kemungkinan pemilihan posisi bola dalam matriks (hanya 1 kali pengambilan). FORMAT MASUKAN Baris pertama berisi dua bilangan M dan N (4 ≤ M, N ≤ 25) yang dipisahkan spasi yang menyatakan jumlah baris dan jumlah kolom. M baris berikutnya berisi susunan bola, dan pada setiap baris terdapat N bilangan bulat yang dapat berharga 1 sampai dengan 5 (yang menyatakan warna bola), dipisahkan oleh sebuah spasi. FORMAT KELUARAN Program anda hanya mengoutputkan satu angka yaitu nilai tertinggi yang bisa diperoleh dari satu kali pengambilan bola. CONTOH MASUKAN 1 47 3342435 2111355 3141145 3343315 CONTOH KELUARAN 1 30 CONTOH MASUKAN 2 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0310.html

1/2

10/3/13

Jawbreaker 2: Cari Terbesar

47 3333221 3222111 3322444 3332224 CONTOH KELUARAN 2 90 CONTOH MASUKAN 3 47 1111111 2555222 3551551 3355151 CONTOH KELUARAN 3 42


2/2

10/3/13

Jawbreaker 3: Cari Terbesar dan Runtuhkan

Jawbreaker 3: Cari Terbesar dan Runtuhkan Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Soal ini mirip dengan soal Jawbreaker versi kedua. Tentukan bola yang harus dipilih sehingga Anda akan mendapatkan nilai terbesar, lalu ambil bola-bola yang termasuk dalam rangkaian bola yang dipilih tersebut. Namun, dalam soal ini, bola-bola yang diambil dihilangkan sehingga terbentuk sel-sel kosong (sebuah sel kosong ditandai dengan karakter '.'). Kemudian, bola-bola akan berjatuhan untuk mengisi ruang kosong tersebut. Aturannya, jika sel tepat di bawah sebuah bola kosong, maka bola itu akan jatuh ke sel di bawahnya. Begitu seterusnya sampai tidak ada lagi bola yang mungkin jatuh. Lakukan simulasi runtuh tersebut dan keluarkan susunan bola pada matriks setelah keruntuhan. FORMAT MASUKAN Baris pertama berisi dua bilangan M dan N (4 ≤ M, N ≤ 25) yang dipisahkan spasi yang menyatakan jumlah baris dan jumlah kolom. M baris berikutnya berisi susunan bola, dan pada setiap baris terdapat N bilangan bulat yang dapat berharga 1 sampai dengan 5 (yang menyatakan warna bola), dipisahkan oleh sebuah spasi. FORMAT KELUARAN Keluarkan M baris yang menyatakan susunan bola pada matriks setelah pengambilan maksimal dan keruntuhan. Sebuah sel kosong ditandai dengan karakter '.' CONTOH MASUKAN 1 47 3342435 2111355 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0311.html

1/2

10/3/13

Jawbreaker 3: Cari Terbesar dan Runtuhkan

3141145 3343315 CONTOH KELUARAN 1 3....35 2.4.455 3342345 3343315 CONTOH MASUKAN 2 47 1111111 2551222 3551551 3355151 CONTOH KELUARAN 2 ....... 255.222 355.551 3355151


2/2

10/3/13

Jawbreaker 4: Cari Terbesar 2 Langkah

Jawbreaker 4: Cari Terbesar 2 Langkah Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Misalkan Anda memilih posisi yang memberikan nilai terbesar A, kemudian setelah bola-bola pada rangkaian diambil dan bola-bola lain diruntuhkan, Anda memilih lagi posisi yang memberikan nilai terbesar B. Percayakah anda bahwa nilai (A + B) belum tentu paling besar dari semua kemungkinan dua langkah yang bisa dilakukan? Logikanya, mungkin ada dua langkah yang menghasilkan A' pada langkah pertama dan B' pada langkah kedua, dan meskipun A' < A, tetapi B’ jauh lebih besar daripada B sehingga A' + B' > A + B. Contohnya sebagai berikut: 12122 11211 11211 11211 Dengan algoritma sebelumnya, pertama kali rangkaian bola berwarna '1' di bagian kiri akan diambil, dengan nilai 7 x 6 = 42, sehingga setelah diruntuhkan menjadi: ..122 ..211 ..211 .2211 Setelah itu, rangkaian bola berwarna '1' di bagian kanan akan diambil, dengan nilai 6 x 5 = 30. Jadi nilai total kedua langkah ini adalah 72. ..1.. ..2.. ..2.. .2222 Mari kembali ke posisi awal. Jika yang dipilih adalah rangkaian bola berwarna '2' yang ada di tengah terlebih dahulu, kita mendapat nilai 3 x 2 = file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0312.html

1/3

10/3/13


6. 12.22 11.11 11.11 11111 Setelah diruntuhkan, akan terbentuk rangkaian bola berwarna '1' yang sangat besar, yang jika diruntuhkan akan menghasilkan nilai 14 x 13 = 182, sehingga total nilai yang diperoleh adalah 188, meskipun langkah pertama tidak menghasilkan banyak nilai. ..... ..... ..... .2.22 Algoritma untuk melakukan langkah yang menghasilkan nilai paling besar satu demi satu, tetapi tidak peduli apakah pada akhirnya totalnya maksimal atau tidak, dikenal dengan istilah algoritma greedy. Untuk sejumlah masalah, algoritma greedy bisa digunakan, tetapi dalam kebanyakan masalah lainnya tidak, contohnya dalam masalah ini. Sebuah harga yang dicapai secara greedy tersebut dikenal dengan istilah "local maximum" sementara harga optimal yang dicari adalah "global maximum". Pada soal ini, Anda diminta untuk mencari global maximum untuk dua langkah saja. FORMAT MASUKAN Baris pertama berisi dua bilangan M dan N (4 ≤ M, N ≤ 25) yang dipisahkan spasi yang menyatakan jumlah baris dan jumlah kolom. M baris berikutnya berisi susunan bola, dan pada setiap baris terdapat N bilangan bulat yang dapat berharga 1 sampai dengan 5 (yang menyatakan warna bola), dipisahkan oleh sebuah spasi. FORMAT KELUARAN Keluarkan nilai terbesar yang dapat dicapai dari dua langkah pengambilan yang optimal.


2/3

10/3/13


CONTOH MASUKAN 45 12122 11211 11211 11211 CONTOH KELUARAN 188


3/3

10/3/13

Jawbreaker 5: Cari Optimal

Jawbreaker 5: Cari Optimal Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Jika pada Jawbreaker 4 Anda mencari global maximum dalam dua langkah saja, kali ini Anda diminta untuk mencari global maximum sampai permainan berakhir (seperti pada permainan Jawbreaker yang sesungguhnya). Tentukan langkah-langkah yang harus diambil sedemikian rupa sehingga jika disimulasikan (ambil rangkaian, runtuhkan, ambil rangkaian, runtuhkan, dst.), jumlah nilai semua langkah ketika permainan selesai adalah sebesar mungkin. Permainan dianggap selesai jika tidak ada lagi rangkaian bola yang terdiri atas minimal dua bola yang dapat diambil. FORMAT MASUKAN Baris pertama berisi dua bilangan M dan N (4 ≤ M, N ≤ 25) yang dipisahkan spasi yang menyatakan jumlah baris dan jumlah kolom. M baris berikutnya berisi susunan bola, dan pada setiap baris terdapat N bilangan bulat yang dapat berharga 1 sampai dengan 5 (yang menyatakan warna bola), dipisahkan oleh sebuah spasi. Dijamin bahwa untuk setiap test case, dengan urutan pengambilan apapun, paling banyak hanya dibutuhkan 7 langkah pengambilan sampai permainan selesai. FORMAT KELUARAN Keluarkan total nilai akhir maksimal yang diperoleh setelah permainan selesai. CONTOH MASUKAN 45 12122 11211 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0313.html

1/3

10/3/13


11211 11211 CONTOH KELUARAN 190 Penjelasan Pertama, ambil rangkaian tiga bola berwarna '2' di tengah. Nilai yang didapatkan adalah 6. Setelah keruntuhan, selanjutnya runtuhkan rangkaian 14 bola berwarna '1'. Nilai yang didapatkan adalah 182. Selanjutnya, ambil rangkaian dua bola berwarna '2' yang tersisa. Nilai yang didapatkan adalah 2. Total nilai: 6 + 182 + 2 = 190.

Petunjuk Rekursi Jika Anda menggunakan prosedur / fungsi rekursif untuk memecahkan masalah ini, kemungkinan besar program Anda memerlukan teknik khusus, yaitu

konfigurasi

bola-bola

sementara

perlu

disimpan

pada

daftar

parameter. Bagaimana cara memakai konfigurasi bola sementara sebagai parameter? Caranya, Anda perlu mendeklarasikan tipe data untuk matriks konfigurasi bola. Setelah itu, tipe data tersebut dapat dipakai sebagai parameter. Misalnya: type TMatriks = array[1..4, 1..25] of byte; ... procedure Rekursi(matriks: TMatriks; ... ); begin ... end;


2/3

10/3/13


Secara umum, jika Anda ingin memasukkan suatu data struktur ke dalam parameter (misalnya array, record, dll.), data struktur tersebut harus memiliki nama (dideklarasikan dengan type).

Petunjuk Optimisasi Jika program Anda sudah berjalan dengan benar tetapi agak lambat, mungkin ide ini bisa dipertimbangkan: Ukuran maksimum matriks adalah 4 x 25, yang berarti ada maksimal 100 posisi bola yang dapat dipilih. Tetapi, apa yang terjadi jika program kita mencoba satu demi satu posisi pada matriks? Jumlah pencobaan yang dilakukan bisa menjadi besar sekali: 100 x 100 x 100 x ... Soal ini menjamin bahwa maksimal hanya ada 7 rangkaian yang berbeda pada setiap konfigurasi. Jadi, Anda dapat mengoptimisasi program Anda dengan mencoba mengambil maksimum 7 rangkaian yang berbeda saja, dan tidak perlu mencoba setiap posisi pada matriks. Pada setiap langkah pada rekursi, hal ini dapat dilakukan dengan menandai pada matriks posisi mana yang tidak perlu dicoba lagi.


3/3

10/3/13

Kandang Terbesar

Kandang Terbesar Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Diberikan sebuah peta dengan ukuran N x M (3 ≤ N, M ≤ 500). Pada tiap posisi dalam peta terdapat batuan penghalang (#) maupun tanah (.). Suatu hari bebek dan kucing bertengkar tentang seberapa luas daerah mereka, karena mereka tidak begitu pintar dalam ilmu ukur maka keduanya tidak tahu persis berapa luas daerah mereka sebenarnya dan selalu menganggap daerah mereka masing-masing adalah yang terluas. Tugas kalian adalah tentukan siapa sebenarnya yang memiliki luas daerah lebih besar, kucing atau bebek? Definisi luas daerah kucing adalah jumlah unit tanah (.), termasuk tempat awal kucing berada, yang dapat dijangkau oleh kucing (ditandai dengan karakter "K") tanpa harus melewati batuan, sebaliknya begitu pula luas daerah bebek (bebek ditandai dengan karakter "B"). Arah gerak yang dapat dilakukan bebek maupun kucing hanya lah empat arah yakni atas, bawah, kanan, dan kiri, tentunya selama tidak keluar dari peta. FORMAT MASUKAN Baris pertama berisi dua buah bilangan bulat N dan M yang menunjukkan banyak kolom dan baris peta. M baris berikutnya berisi N karakter (.), (#), (B), (K). Dalam sebuah peta dijamin hanya terdapat seekor kucing (K) dan seekor bebek (B). FORMAT KELUARAN Jika daerah bebek lebih luas, maka keluarkan B X, sedangkan jika daerah kucing lebih luas, maka keluarkan K X, dan jika kedua daerah sama luasnya, keluarkan SERI dimana X adalah besar selisih luas. CONTOH MASUKAN 1 10 10 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0314.html

1/3

10/3/13

Kandang Terbesar

........#. #####...#. .#K.###### .#..#.###. .#..#..B#. .#.##.##.. .#######.. ....#.#... #####.#### ....#..... CONTOH KELUARAN 1 K2 CONTOH MASUKAN 2 9 10 .......#. ####...#. #K.###### #..#....# #.##..B#. #.##..#.. #######.. ...#.#... ####.#### ...#..... CONTOH KELUARAN 2 B3 CONTOH MASUKAN 3 10 8 #####...#. .#K.###### .#..#.###. .#.#...B#. .#.##.##.. .#######.. ....#.#... #####.####


2/3

10/3/13

Kandang Terbesar

CONTOH KELUARAN 3 SERI


3/3

10/3/13

Potong Kue

Potong Kue Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Hari ini Pak Dengklek sedang gembira (entah kenapa) sehingga ia membeli sebuah kue berbentuk lingkaran dan hendak membaginya kepada N ekor bebek yang ia miliki. Ia sangat mengetahui seberapa banyak biasanya bebek-bebeknya makan, sehingga ia sudah tahu seberapa besar (dalam persen) setiap ekor bebek harus mendapatkan potongan kue yang ia beli. Pak Dengklek mengetahui jika melakukan potongan penuh (potongan yang tepat melalui titik pusat lingkaran dan membentuk diameter) potongan kue akan makin rapi, sehingga kini ia meminta bantuan Anda untuk menentukan berapa jumlah potongan penuh terbanyak yang dapat ia lakukan dengan proporsi makan bebeknya. FORMAT MASUKAN Sebuah baris berisi beberapa bilangan bulat. Bilangan pertama adalah N (1 ≤ N ≤ 8), jumlah bebek yang dimiliki Pak Dengklek, diikuti N bilangan berikutnya berisi persen dari kue yang akan diberikan kepada masingmasing bebek (jumlah semuanya tentu 100). FORMAT KELUARAN Sebuah baris berisi sebuah bilangan bulat yang merupakan jumlah potongan penuh terbanyak yang dapat Pak Dengklek lakukan dengan proporsi makan bebeknya. CONTOH MASUKAN 1 4 20 15 30 35 CONTOH KELUARAN 1 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0315.html

1/2

10/3/13

Potong Kue

1 CONTOH MASUKAN 2 4 25 25 25 25 CONTOH KELUARAN 2 2 Penjelasan Berikut penjelasan bagaimana pada contoh kasus 1 Pak Dengklek dapat melakukan 1 potongan penuh. Tidak ada cara lain agar dapat melakukan 2 potongan penuh atau lebih.


2/2

10/3/13

Mengurutkan Kata

Mengurutkan Kata Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Untuk berlatih menggunakan algoritma sort, Anda diberikan N (1 ≤ N ≤ 10000) buah kata, di mana setiap kata terdiri atas huruf kecil ("a", "b", ..., "z") dan panjangnya minimal 1 karakter dan maksimal 100 karakter. Urutkanlah kata-kata tersebut dari yang paling pendek sampai yang paling panjang. Jika ada beberapa kata yang panjangnya sama, urutkan secara leksikografi (menurut urutan kamus). (Disarankan berlatih menggunakan quicksort) FORMAT MASUKAN Baris pertama berisi sebuah bilangan bulat N. N baris berikutnya berisi N buah kata, satu kata per baris. FORMAT KELUARAN Keluarkan N baris yang berisi kata-kata yang sudah diurutkan menurut aturan di atas, satu kata per baris. CONTOH MASUKAN 4 toki maju pantang mundur CONTOH KELUARAN maju toki mundur file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0401.html

1/2

10/3/13

Mengurutkan Kata

pantang


2/2

10/3/13

Bilangan Ke-K

Bilangan Ke-K Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Anda diberikan N (1 ≤ N ≤ 100000) buah bilangan bulat, di mana setiap bilangan bulat minimal bernilai -2000000000 dan maksimal 2000000000 (gunakan tipe data longint). Keluarkanlah bilangan ke-K terbesar (1 ≤ K ≤ N). FORMAT MASUKAN Baris pertama berisi dua buah bilangan bulat, N dan K, dipisahkan oleh sebuah spasi. N baris berikutnya berisi N buah bilangan bulat. Bisa ada dua bilangan bulat yang bernilai sama. FORMAT KELUARAN Keluarkan bilangan ke-K terbesar. Jika ada dua bilangan bulat yang bernilai sama, anggap mereka adalah bilangan bulat yang berbeda. Jadi, bilangan ke-N terbesar selalu adalah bilangan terkecil. CONTOH MASUKAN 32 10 8 9 CONTOH KELUARAN 9


1/1

10/3/13

Membuang Perulangan

Membuang Perulangan Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Anda diberikan N (1 ≤ N ≤ 100000) buah longint. Jika ada bilangan yang diulang lebih dari satu kali, buanglah kemunculan bilangan-bilangan tersebut selain kemunculan pertama. Lalu keluarkan kembali bilanganbilangan tersebut sesuai urutan pada input. FORMAT MASUKAN Baris pertama berisi sebuah bilangan bulat N. N baris berikutnya berisi N buah longint, satu buah longint setiap baris. FORMAT KELUARAN Keluarkan bilangan-bilangan sesuai urutan pada input sesuai deskripsi di atas. CONTOH MASUKAN 5 4 2 4 3 2 CONTOH KELUARAN 4 2 3


1/1

10/3/13

Dua Bilangan yang Hilang

Dua Bilangan yang Hilang Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Dari antara bilangan-bilangan 1, 2, 3, ..., N, Anda hanya akan diberi N - 2 bilangan. Dua buah bilangan manakah yang hilang? FORMAT MASUKAN Baris pertama berisi sebuah bilangan bulat N (2 ≤ N ≤ 100000). N - 2 baris berikutnya berisi N - 2 buah bilangan bulat yang berbeda-beda, yang berada dalam jangkauan 1 sampai dengan N. FORMAT KELUARAN Keluarkan dua buah bilangan bulat dalam jangkauan 1 sampai dengan N yang tidak ada pada input, satu bilangan pada setiap baris. Bilangan yang lebih kecil dari antara kedua bilangan itu dituliskan pada baris pertama. CONTOH MASUKAN 5 1 5 3 CONTOH KELUARAN 2 4


1/1

10/4/13

Anagram

Anagram Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Dua kata A dan B disebut anagram jika kata B dapat dibentuk dari hurufhuruf penyusun kata A. Sebuah anagram dapat terdiri dari dua buah kata atau lebih, misalnya: ibu ubi bisa basi abis Perlu dicatat bahwa jika dua buah kata membentuk anagram, banyak dari setiap huruf-huruf penyusun dua kata tersebut harus sama. Jadi, "saksi" dan "aksi" bukan anagram. Pada soal ini, Anda akan diberikan N (1 ≤ N ≤ 10000) buah string yang memiliki antara 1 sampai dengan 100 karakter. Setiap string terdiri atas karakter-karakter huruf kecil "a", "b", ..., "z". Carilah anagram yang terdiri atas sebanyak-banyaknya kata. Jika ada beberapa anagram yang memilki banyak kata yang sama, pilihlah yang kata terawal secara leksikografi dalam anagram tersebut adalah yang paling awal secara leksikografi, dibandingkan dengan kata-kata terawal dari anagram lainnya. Jika tidak ada dua kata atau lebih yang membentuk anagram, keluarkan "TIDAK ADA". FORMAT MASUKAN Baris pertama berisi sebuah bilangan bulat N. N baris berisi N buah string, sebuah string setiap baris. Dijamin tidak ada string yang disebutkan lebih dari dua kali pada input. file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0405.html

1/2

10/4/13

Anagram

FORMAT KELUARAN Baris pertama berisi sebuah bilangan K, yang merupakan banyaknya kata dalam anagram yang ditemukan dengan banyak kata terbanyak, sesuai deskripsi soal di atas. K baris berikutnya berisi kata-kata yang ada di dalam anagram tersebut, satu kata per baris. Urutkan K kata tersebut secara leksikografi. CONTOH MASUKAN 1 4 kami ubi mika ibu CONTOH KELUARAN 1 2 ibu ubi CONTOH MASUKAN 2 3 ayo maju toki CONTOH KELUARAN 2 TIDAK ADA Penjelasan Pada contoh pertama, pasangan "ibu" dan "ubi" dipilih karena kata yang secara leksikografi paling awal pada anagram ini ("ibu") lebih awal daripada kata paling awal pada anagram lainnya ("kami").


2/2

10/4/13

Root Mean 'To the 1.5' Average

Root Mean 'To the 1.5' Average Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Sebetulnya dalam dunia matematika tidak ada yang namanya "root mean to the 1.5 average". Yang ada adalah "root mean square average" (RMS average) yang banyak ditemui pada pelajaran fisika atau statistika. Tetapi karena untuk menghitung RMS average sudah ada rumusnya, jadi dalam soal ini Anda tidak diminta untuk menghitung RMS average. Mari kita singkat "root mean to the 1.5 average" menjadi RM1.5 average (untuk meniru RMS average). RM1.5 average dari bilangan-bilangan real X1, X2, X3, ..., XN (1 ≤ N ≤ 50000) adalah suatu nilai Y sehingga nilai |X1 Y|1.5 + |X2 - Y|1.5 + |X3 - Y|1.5 + ... + |XN - Y|1.5 adalah sekecil-kecilnya. Catatan: tanda |...| artinya adalah nilai absolut dari ekspresi apapun yang berada di dalamnya. Carilah nilai RM1.5 average dari masukan. FORMAT MASUKAN Baris pertama berisi sebuah bilangan bulat N. N baris berikutnya berisi N buah bilangan real, di mana setiap bilangan berada pada jangkauan -1000.00 hingga 1000.00 dengan maksimal dua angka di belakang koma. FORMAT KELUARAN Dalam satu baris, keluarkan nilai RM1.5 average dari bilangan-bilangan pada masukan. Formatlah keluaran Anda sehingga dibulatkan ke dua angka di belakang koma (dengan cara writeln(variabel:0:2)). CONTOH MASUKAN file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0406.html

1/2

10/4/13

Root Mean 'To the 1.5' Average

3 1.23 2.34 3 CONTOH KELUARAN 2.30 Catatan Gunakanlah tipe data doubleuntuk bilangan real, supaya akurat.

Petunjuk Jika kita definisikan f(Y) = |X1 - Y|1.5 + |X2 - Y|1.5 + |X3 - Y|1.5 + ... + |XN - Y|1.5, maka dijamin bahwa grafik f(Y) terhadap Y akan tepat memiliki sebuah nilai f(Y) minimum, dan grafiknya akan berbentuk mangkuk menghadap ke atas, seperti pada gambar.

Karakteristik ini dapat dimanfaatkan untuk mem-binary-search nilai Y.


2/2

10/4/13

Barisan Hewan Ternak

Barisan Hewan Ternak Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Pak Dengklek memiliki peternakan yang sangat besar. Di dalam peternakan itu ada banyak sekali hewan ternak, maksimum 2000000000 ekor. Di dalam peternakan tersebut, hewannya juga bermacam-macam: ada kuda, sapi, ayam, burung, kerbau, dan lain-lain (dan tentu saja ada bebek). Secara umum, ada N (1 ≤ N ≤ 100000) jenis hewan ternak di peternakan tersebut, dan untuk setiap jenis hewan ke-i ada Xi (1 ≤ Xi ≤ 20000) ekor. Karena terkagum-kagum dengan banyaknya hewan di peternakan Pak Dengklek, kepala desa suka berkunjung ke peternakan tersebut dan membuat suatu permainan. Hewan-hewan ternak itu dibariskan, mulai dari semua jenis ke-1, lalu semua jenis ke-2, dan seterusnya sampai dengan jenis ke-N. Setelah itu, kepala desa akan menanyakan Q (1 ≤ Q ≤ 100000) buah pertanyaan, yang setiap pertanyaan berbunyi seperti ini: "Hewan jenis keberapakah yang berada pada urutan ke-Y j dari depan?" (1 ≤ Y j ≤ (X1+X2+...+XN)) Tentu Pak Dengklek kebingungan menjawab pertanyaan-pertanyaan kepala desa. Bantulah Pak Dengklek dengan membuat program yang akan menjawab pertanyaan-pertanyaan tersebut dengan cepat. FORMAT MASUKAN Baris pertama berisi sebuah bilangan bulat N. N baris berikutnya berisi X1, X2, ..., XN, satu bilangan per baris. Setelah itu, baris berikutnya berisi sebuah bilangan bulat Q. Lalu, Q baris berikutnya berisi Y 1, Y 2, ..., Y Q, satu bilangan per baris. FORMAT KELUARAN file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0407.html

1/2

10/4/13

Barisan Hewan Ternak

Keluaran terdiri atas Q baris. Baris ke-j berisi jawaban atas pertanyaan "Hewan jenis keberapakah yang berada pada urutan ke-Y j dari depan?" CONTOH MASUKAN 3 10 10 10 3 5 15 25 CONTOH KELUARAN 1 2 3


2/2

10/4/13

Pesta Bebek

Pesta Bebek Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Pak Dengklek tahun ini terpilih menjadi tuan rumah Pesta Bebek. Pesta tersebut akan dihadiri oleh semua pemilik bebek ternama di Indonesia. Pada acara tersebut, setiap tamu yang baru hadir akan diberikan sebuah nomor (yang kemudian mungkin akan dijadikan nomor undian) yang merupakan posisi namanya di daftar tamu yang sudah hadir (daftar tersebut diurutkan berdasarkan urutan kamus tanpa membedakan huruf besar dan huruf kecil). Jadi, simpelnya, setiap kali ada tamu yang baru hadir, nama tamu yang sudah hadir (termasuk yang baru hadir) akan diurutkan, dan tamu yang baru hadir tersebut akan mendapatkan nomor sesuai posisi namanya di urutan tamu yang sudah hadir. Diberikan daftar urutan hadir semua tamu Pesta Bebek, tentukanlah nomor yang didapatkan setiap tamu. FORMAT MASUKAN Baris pertama berisi sebuah bilangan bulat N (1 ≤ N ≤ 1000). N baris berikutnya berisi masing-masing nama tamu sesuai dengan urutan hadirnya (pada saat tamu ke-i hadir, tamu ke-1 sampai ke-(i-1) tentunya sudah hadir, dan tamu ke-(i+1) sampai ke-N tentunya belum hadir). Tidak ada dua tamu yang hadir secara bersamaan dan tidak ada dua tamu yang memiliki nama sama persis. Nama tersebut hanya akan berisi karakter 'a'..'z', 'A'..'Z', dan spasi (pada kamus, spasi muncul terlebih dahulu dibanding semua karakter alfabet) dengan jumlah maksimal 20 karakter. FORMAT KELUARAN N baris masing-masing berisi sebuah bilangan bulat yang merupakan nomor file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0408.html

1/3

10/4/13

Pesta Bebek

tamu yang datang pada urutan tersebut. CONTOH MASUKAN 1 5 BUDI ANI R ANISA ANDI TARZAN CONTOH KELUARAN 1 1 1 2 1 5 CONTOH MASUKAN 2 3 ANDI BUDI TARZAN CONTOH KELUARAN 2 1 2 3 Penjelasan Pada contoh pertama, saat BUDI datang, dia hanya sendirian, tentunya dia mendapatkan nomor 1. Saat ANI R datang, menurut urutan kamus ia muncul terlebih dahulu sebelum BUDI, sehingga ANI R mendapatkan nomor 1. Saat ANISA datang, menurut urutan kamus ia muncul terlebih dahulu sebelum BUDI tapi muncul setelah ANI R, sehingga ANISA mendapat nomor 2. Begitu selanjutnya sampai TARZAN mendapatkan nomor 5.


2/3

10/4/13


Pesta Bebek

3/3

10/4/13

Hitung Bebek Lagi

Hitung Bebek Lagi Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Bebek-bebek Pak Dengklek sungguh pintar, mereka sudah mengerti penjumlahan dengan sangat baik. Dengan bangga, bebek-bebek sering mempertunjukkan keahliannya kepada Pak Dengklek. Keunikan dari bebekbebek Pak Dengklek, mereka sangat dan hanya suka pada angka 1 dan 2. Sehingga saat Pak Dengklek meminta bebek-bebek untuk menuliskan sebuah angka, bebek-bebek akan menuliskan angka tersebut dengan untaian angka 1 dan 2 yang kemudian dijumlahkan. Misalnya, jika Pak Dengklek meminta bebek-bebek untuk menuliskan angka 4. Bebek-bebek dapat menulis 1111 (1+1+1+1=4), 112, 121, 211, atau 22. Jumlahnya ada 5 cara yang dapat bebek-bebek gunakan untuk menulis angka 4. Dalam soal ini, Anda akan diberikan beberapa angka, hitunglah berapa banyak cara yang dapat bebek-bebek gunakan untuk menulis angka-angka tersebut. FORMAT MASUKAN Baris pertama berisi sebuah bilangan bulat N (1 ≤ N ≤ 100000). Baris kedua sampai ke-(N+1) berisi masing-masing sebuah bilangan bulat K (1 ≤ K ≤ 10000000). FORMAT KELUARAN N baris masing-masing berisi sebuah bilangan bulat yang merupakan jumlah cara yang dapat bebek-bebek gunakan untuk menulis angka K. Bilangan keluaran ini bisa jadi sangat besar (melebihi batas variabel dasar di PASCAL), maka jika bilangan tersebut lebih besar dari 999999, Anda cukup mencetak 6 digit terakhir dari bilangan tersebut. CONTOH MASUKAN file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0409.html

1/2

10/4/13

Hitung Bebek Lagi

3 5 3 6 CONTOH KELUARAN 8 3 13


2/2

10/4/13

Perkalian Skalar

Perkalian Skalar Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Anda diberikan dua buah vektor berisi N bilangan bulat, v1=(x1,x2,x3,...,xN) dan v2=(y1,y2,y3,...yN). Perkalian skalar dari dua vektor adalah sebuah bilangan yang didapatkan dari x1y1+x2y2+x3y3+...+xNyN. Dalam soal ini, anggap Anda bebas mengacak-acak urutan bilangan dalam setiap vektor. Tentukan permutasi yang tepat untuk kedua vektor sehingga hasil perkalian skalarnya minimum. FORMAT MASUKAN Baris pertama berisi sebuah bilangan bulat N (1 ≤ N ≤ 10000) yang menunjukkan jumlah bilangan bulat dalam v1 dan v2. Baris kedua berisi N buah bilangan yang merupakan bilangan bulat dalam v1. Baris ketiga berisi N buah bilangan yang merupakan bilangan bulat dalam v2. Setiap bilangan bulat penyusun v1 maupun v2 akan berkisar antara -100000 sampai 100000. FORMAT KELUARAN Sebuah bilangan bulat yang merupakan hasil perkalian skalar minimum seperti yang sudah dijelaskan di atas. CONTOH MASUKAN 1 3 1 3 -5 -2 4 1 CONTOH KELUARAN 1 -25


1/2

10/4/13

Perkalian Skalar

CONTOH MASUKAN 2 5 12345 10101 CONTOH KELUARAN 2 6


2/2

10/4/13

Bukit dan Lembah

OSN 2005 : Bukit dan Lembah Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Diberikan data ketinggian yang di catat dalam perjalanan dari suatu posisi awal ke posisi akhir. Data ketinggian adalah bilangan-bilangan integer (bulat) positif. Jalan kadang menaik, kadang menurun, kadang datar saja. Posisi dimana terjadi perubahan menaik kemudian menurun (boleh diselingi jalan datar) didefinisikan sebagai puncak dari suatu bukit. Sebaliknya, posisi terjadi perubahan dari menurun terus menaik (boleh diselingi bagian jalan yang datar) didefinisikan sebagai titik terbawah suatu lembah. Walaupun perubahan tersebut kecil saja, definisi itu tetap berlaku. Carilah beda ketinggian terbesar antara puncak bukit dengan titik terbawah lembah berikutnya atau sebaliknya antara titik terbawah lembah dengan puncak bukit berikutnya pada data perjalanan tersebut. FORMAT MASUKAN Masukan berisi data yang bisa sangat banyak sekali. Setiap elemen data dalam baris tersendiri. Anda membacanya dari yang pertama hingga end of file; minimal ada dua data dalam masukan. FORMAT KELUARAN Program hanya menghasilkan satu bilangan yang menyatakan beda ketinggian terbesar yang diperoleh. Perbedaan tinggi paling besar dijamin tidak akan melebihi harga long integer dalam Pascal. CONTOH MASUKAN 10 26 26 35 35 27 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0501.html

1/2

10/4/13

Bukit dan Lembah

30 30 45 10 8 9 CONTOH KELUARAN 37 Penjelasan Ada 12 data. Beda ketinggian pertama (10 ke 35) adalah 25, beda kedua (35 ke 27) adalah 8, beda ketiga (27 ke 45) adalah 18, beda ketinggian keempat (45 ke 8) adalah 37, dan beda ketinggian kelima (8-9) adalah 1. Jadi beda ketinggian tertinggi adalah 37.


2/2

10/4/13

Kata Spiral

OSN 2005 : Kata Spiral Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Suatu sistem sandi menyandikan kalimat yang diberikan dalam bantuk spiral. Penyusunan tersebut dilakukan membentuk matriks spiral yang dimulai pusat matriks 1 karakter pertama, lalu 1 karakter berikutnya ke kanan, lalu 1 karakter berikutnya ke bawah, lalu 2 karakter berikutnya ke kiri, lalu 2 karakter berikutnya ke atas, 3 karakter berikutnya ke kanan, 3 karakter berikutnya ke bawah, dan seterusnya hingga semua karakter dalam kalimat termasuk dalam spiral. Khususnya, karakter spasi di ganti dengan “_” (underscore), dan jika ada baris/kolom tersisa setelah karakter terakhir maka elemen-elemen matriks diisi juga dengan “_” (underscore) tsb. Misalnya kalimat “Seluruh peserta OSN bidang komputer harus mengerjakan soal-soal sebaikbaiknya untuk mendapatkan peringkat terbaik.” Dikodekan kedalam matriks sebagai berikut. baik.______ raiknya_unt ebmengerjau t-_bidangkk _ks_h_pe_a_ tiuNuSesknm aarSruleo_e kbaO_atrmsn geh_retupod ns_laos-laa irep_naktap FORMAT MASUKAN Program membaca satu baris teks paling panjang 250 karakter. FORMAT KELUARAN Program harus menghasilkan sejumlah baris sesuai dengan matriks yang dibentuk. Setiap baris keluaran berisikan karakterkarakter dari baris yang sama berturut-turut dari kolom paling kiri ke paling kanan tanpa pemisahan (karakter-karakter dituliskan bersambungan menjadi satu string serta jangan lupa setiap spasi menjadi underscore). CONTOH MASUKAN 1

Seluruh peserta OSN bidang komputer harus mengerjakan soal-soal sebaik-baiknya untuk mendapatkan peringkat terbai CONTOH KELUARAN 1 baik.______ raiknya_unt ebmengerjau t-_bidangkk _ks_h_pe_a_ tiuNuSesknm aarSruleo_e kbaO_atrmsn geh_retupod ns_laos-laa irep_naktap CONTOH MASUKAN 2 TOKI CONTOH KELUARAN 2 TO IK CONTOH MASUKAN 3 Bisakah Kamu????? file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0502.html

1/2

10/4/13

Kata Spiral

CONTOH KELUARAN 3 _h_Ka _aBim _kasu ?????


2/2

10/4/13

Faktorial

OSN 2005 : Faktorial Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Pasti anda sudah pernah belajar apakah itu bilangan faktorial. Sesuai dengan definisinya bilangan faktorial n! = n.(n-1).(n-2)…..1. Untuk n yang kecil bilangan tersebut masih mudah dihitung dengan manual tetapi untuk n yang cukup besar bisa menghasilkan bilangan dengan jumlah digit yang amat banyak sehingga tentu melelahkan jika dihitung dengan manual bahkan dengan komputerpun kita perlu cara khusus untuk menanganinya akibat adanya batasan representasi bilangan integer. Oleh sebab itu dalam rumus-rumus bilangan faktorial tetap dinyatakan dalam bentuk n!, misalnya n!/(n-k)!k!. Untuk perhitungan (50! * 100! * 75!)/(73! * 99! * 52!) tentu tidak memungkinkan kalau masing-masing bilangan faktorialnya dihitung terlebih dahulu lalu diperkalikan/diperbagikan kemudian. Sebaliknya, akan lebih mudah jika dilakukan penyederhanaan dengan menghilangkan faktorfaktor yang sama antara pembilang (di atas tanda bagi) dan penyebut (di bawah tanda bagi) sampai tinggal sejumlah bilangan nonfaktorial yang tersisal. Contohnya. (50! * 100! * 75!)/(73! * 99! * 52!) = ( 74 * 75 * 100 ) / ( 51 * 52 ) yang berikutnya, dengan menguraikan ke faktor-faktor bilangan prima dapat disederhanakan lebih lanjut menjadi (catatan: notasi ^ adalah tanda pangkat). = (2 * 37 * 3 * 52 * 22 * 52) /(3 * 17 * 22 * 13) = (2 * 54 * 37)/(13 * 17) Dengan ekspresi tersebut, perhitungan kemudian menjadi lebih memungkinkan untuk dilakukan dibandingkan saat masih dalam bentuk faktorial. Buatlah program yang dapat melakukan penyederhanaan ekspresi perkalian/pembagian bilangan-bilangan bilangan prima seperti di atas.

faktorial

hingga

faktor-faktor

FORMAT MASUKAN file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0503.html

1/3

10/4/13

Faktorial

Masukan terdiri atas dua baris. Baris pertama menyatakan harga-harga n dari bilangan-bilangan faktorial yang berada pada bagian pembilang (yang dibagi). Baris kedua menyatakan harga-harga n dari bilangan-bilangan faktorial yang berada pada bagian penyebut. Format masing-masing bilangan sama sbb. Bilangan pertama menyatakan jumlah bilangan faktorial pada baris ybs. Jumlah bilangan tersebut paling sedikit 1 dan paling banyak 20. Misalkan jumlah bilangan itu m, berikutnya ada m bilangan bulat positif a, b, c, …,dst. yang masing-masing dapat berharga 2 sampai dengan 1000. Masing-masing bilangan tersebut menyatakan bilanga-bilangan faktorial a, b, c, … dst. FORMAT KELUARAN Keluaranya terdiri dari dua baris, baris pertama untuk pembilang dan beris kedua untuk penyebut. Bilangan-bilangan adalah bilangan prima yang tersisa dan untuk pangkat yang lebih dari 1 dituliskan di dalam tanda kurung langsung setelah bilangan prima ybs (tanpa spasi). Bilanganbilangan prima dituliskan dari yang terkecil ke yang terbesar. Sekali lagi, penulisan pangkat hanya untuk bilangan prima dengan pangkat lebih dari 1. Jika salah satu dari pembilang atau penyebut berharga 1 maka baris untuk ybs dikosongkan (sebagai konsekuensi tidak adanya faktor bilangan prima padanya. CONTOH MASUKAN 1 3 50 100 75 3 73 99 52 CONTOH KELUARAN 1 2 5(4) 37 13 17 CONTOH MASUKAN 2 1 100 1 99 CONTOH KELUARAN 2 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0503.html

2/3

10/4/13

Faktorial

2(2) 5(2) CONTOH MASUKAN 3 1 48 1 49 CONTOH KELUARAN 3 7(2) Penjelasan Penjelasan: pada contoh kedua, baris kedua kosong dan pada contoh ketiga, baris pertama yang kosong.


3/3

10/4/13

Sandi Ayam

OSN 2005 : Sandi Ayam Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:

pjj0504.PAS / C / CPP 0.5 detik / test-case 16 MB Standard input (keyboard) Standard output (layar)

Pak Dengklek punya tetangga baru yang berprofesi sebagai peternak ayam. Tentunya, tetangga baru ini memiliki beberapa ayam. Bebek-bebek Pak Dengklek tidak suka dengan kehadiran ayam-ayam ini, antara lain karena mereka curiga ayam-ayam tersebut akan melakukan hal-hal yang tidak baik. Dalam beberapa hari semenjak kedatangannya saja, bebek-bebek sudah menemukan goresan-goresan aneh di tanah. Setelah diteliti, para bebek menyimpulkan bahwa ayam-ayam tersebut sedang menuliskan sandi angka. Penelitian lebih lanjut memberikan hasil mengenai arti dari setiap sandi, seperti yang dijelaskan di bawah ini. Ayam-ayam menggunakan 20 macam simbol. Setiap simbol adalah hasil dari patokan paruh ayam (bulatan kecil) dan/atau goresan cakar ayam (garis). Bukti-bukti yang sejauh ini ada menunjukkan bahwa setiap simbol memiliki padanan seperti yang tertera pada gambar 1.

Untuk membentuk angka yang benilai lebih dari 19, simbol-simbol di atas ditulis secara vertikal dan dibaca seperti layaknya bilangan dengan basis file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0504.html

1/3

10/4/13

Sandi Ayam

20. Simbol dengan bobot lebih besar digores paling atas. Tentunya, dengan sistem ini para bebek berharap bahwa nilai satuan dari setiap simbol, mulai dari simbol yang mewakili satuan terkecil, adalah 1, 20, 400, 8000, dst. Akan tetapi, ayam-ayam tersebut lebih cerdas. Ternyata, harga satuan simbol ketiga dari bawah (bila ada) hanya 18 kali lebih besar dari harga satuan simbol kedua dari bawah. Akan tetapi untuk simbol-simbol berikutnya, nilai satuannya tetap 20 kali lebih besar daripada satuan sebelumnya. Untuk lebih jelasnya, lihat contoh berikut ini.

Seperti yang tertera pada gambar di atas, sandi di atas terdiri dari 4 simbol. Simbol paling atas melambangkan angka 2, simbol di bawahnya melambangkan angka 0, berikutnya angka 17 dan yang paling bawah melambangkan angka 1. Bila kita mengikuti sistem bilangan yang digunakan oleh para bebek (yang untungnya adalah sama seperti kita, desimal), maka angka yang dimaksud oleh sandi di atas adalah 14741 (= 2x7200 + 0x360 + 17x20 + 1). Para bebek memiliki kesulitan untuk menerjemahkan sandi-sandi yang panjang. Untuk itu, mereka meminta bantuan kalian untuk menerjemahkannya. FORMAT MASUKAN Masukan akan berisi sebuah angka yang tertulis dalam sandi ayam. Untuk mempermudah tugas kalian, patokan ayam akan dimasukkan sebagai titik (.), dan cakaran ayam akan dimasukkan sebagai tanda hubung (-). Simbol 0 (lingkaran besar) akan dimasukkan sebagai angka 0. Setiap dua simbol akan dipisahkan oleh sebuah baris kosong. Masukan akan diakhiri oleh penanda akhir berkas (end-of-file). Masukan berisi setidaknya sebuah simbol, tapi tidak lebih dari 30 simbol. Untuk setidaknya setengah dari total bobot testcase yang diujikan, masukan terdiri tidak lebih dari 14 simbol. FORMAT KELUARAN file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0504.html

2/3

10/4/13

Sandi Ayam

Keluaran hanya terdiri dari sebuah baris berisi sebuah bilangan bulat yang merupakan hasil penerjemahan sandi ayam pada masukan. CONTOH MASUKAN .. 0 .. . CONTOH KELUARAN 14741 Peringatan Keluaran untuk masukan dengan banyak simbol lebih dari 14 buah tidak dijamin dapat dimuat oleh sebuah variabel integer 64-bit bertanda (int64 di FreePascal).


3/3

10/4/13

Maze

OSN 2005 : Maze Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Anda tahu permainan maze? Kalau melihat gambar berikut ini pasti tahu. Dalam permainan maze ini makhluk yang digambarkan dengan bulatan wajah Mr Groovy harus mencari jalan ke luar dari grid maze yang diberikan.

Jalan keluar yang harus dilaluinya adalah kota-kotak yang berwarna kuning tsb. Masalahnya karena bisa terdapat beberapa cara untuk mencapai jalan keluar maka disini anda harus menemukan jumlah kotak yang paling sedikit dalam lintasan (menyatakan juga jumlah langkah terpendek untuk mencapai bagian luar). Dalam hal contoh maze di atas yang paling sedikit adalah 17 kotak/langkah yaitu yang berwana kuning tsb. FORMAT MASUKAN Baris pertama berisikan b dan k yang menyatakan jumlah baris dan jumlah kolom matriks grid tersebut. Kedua bilangan dipisahkan satu spasi. Jumlah baris/kolom terkecil adalah 3 dan jumlah baris/kolom terbesar adalah 100. Pada b baris berikutnya maze didefinisikan sbb. Harga -1 menyatakan file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0505.html

1/2

10/4/13

Maze

dinding yang tidak dapat ditembus, harga 0 menyatakan ruang yang dapat dilalui. Dipastikan sekurangnya ada satu jalan keluar. Setiap baris grid pada baris masukan tersendiri. Pada baris yang sama hargaharga tersebut dituliskan terpisah satu spasi dengan harga berikutnya. Pada baris terakhir terdapat dua bilangan a dan b yang menyakan posisi awal Mr Groovy berada, a nomor baris dan b nomor kolom dengan penomoran baris: 1, 2, 3, …, dimulai dari atas ke bawah dan penomoran kolom: 1, 2, 3, …, dimulai dari kiri ke kanan. Dipastikan posisi awal ini selalu berada pada ruangan (bukan tembok!) dan di dalam matriks. FORMAT KELUARAN Program hanya mengeuarkan jumlah langkah paling sedikit untuk mencapai luar (sama juga dengan jumlah kotak paling sedikit yang dilalui). CONTOH MASUKAN 8 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 -1 0 0 0 -1 0 0 -1 -1 0 0 0 -1 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 0 0 0 -1 0 -1 -1 -1 -1 -1 0 -1 0 -1 0 -1 0 0 -1 -1 0 -1 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 75 CONTOH KELUARAN 17


2/2

10/4/13

Segitiga Bebek

OSN 2005 : Segitiga Bebek Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Suatu hari Pak Dengklek mendapat penghasilan lebih dari hasil berjualan telur bebek asin. Oleh karena itu ia ingin membagi keuntungannya dengan bebek-bebeknya, dengan cara memberi makan lebih untuk mereka. Sayangnya uangnya hanya cukup untuk memberi makan lebih kepada tiga ekor bebek. Untuk itu ia membuat suatu cara untuk memil ih tiga ekor bebek mana yang akan diberinya makan lebih hari itu. Saat itu, bebek-bebeknya sedang berkeliaran di ladangnya yang luas. Pak Dengklek memutuskan untuk memberi makan lebih kepada tiga ekor bebek yang di posisinya sekarang membentuk segitiga dengan luas minimum. Yang dimaksud segitiga dengan luas minimum di sini adalah, semua segitiga lain yang dibentuk oleh bebek-bebek memiliki luas yang lebih besar dari luas segitiga tersebut. Karena banyaknya jumlah bebek-bebek, Pak Dengklek meminta bantuanmu untuk masalah ini. Bantulah Pak Dengklek dengan mencari luas segitiga minimum tersebut akurat hingga dua tempat desimal. FORMAT MASUKAN Baris pertama dari masukan berisi sebuah bilangan N, yang menyatakan jumlah bebek-bebek yang tersebar di ladang Pak Dengklek saat ini. 1 <= N <= 300. Baris kedua hingga baris ke N+1 masing masing akan berisi dua buah bilangan bulat xi dan yi, yang merupakan koordinat bebek ke-i di sistem koordinat kartesian. -10000 <= xi,yi <= 10000. Tidak akan ada dua bebek yang berbeda yang berada di posisi (x, y) yang sama. FORMAT KELUARAN Keluaran hanya terdiri dari sebuah baris berisi bilangan yang merupakan file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0506.html

1/2

10/4/13

Segitiga Bebek

luas segitiga minimum menurut syarat yang sudah dijelaskan dengan dua tempat desimal. Jika tidak ada segitiga yang memenuhi syarat tersebut, keluarkan angka -1.00 . CONTOH MASUKAN 1 4 00 -5 10 30 09 CONTOH KELUARAN 1 13.50


2/2

10/4/13

Faktorial

OSN 2006 : Faktorial Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


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: a. N=10: 10! = 3 628 800, maka jumlah angka nol adalah 2. b. 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 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0507.html

1/2

10/4/13

Faktorial

1 Catatan Jika Anda dapat memanfaatkan sifat rumus faktorial, maka Anda akan mendapatkan hasil yang lebih efisien

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


2/2

10/4/13

Tebak Lagu

OSN 2006 : Tebak Lagu Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Pak Dengklek dan bebek-bebeknya punya permainan baru, yaitu tebak lagu. Sesuai namanya, dalam permainan ini salah satu bebek akan menyanyikan fragmen/potongan sebuah lagu untuk kemudian ditebak oleh Pak Dengklek. Karena tahu bahwa Pak Dengklek bukanlah seorang penghafal yang handal, para bebek menyiapkan sebuah buku yang berisikan daftar lagu yang akan mereka nyanyikan, lengkap dengan nadanya. Seperti halnya manusia, para bebek tidak menyanyi dengan ketinggian nada yang sama satu sama lain. Oleh sebab itu, mereka sepakat untuk menuliskan nada-nada lagu di buku lagu mereka dalam nada dasar C tengah (C4 pada piano manusia, yang mereka beri simbol c.), yaitu nada dengan frekuensi 261.6 Hz. Untuk nadanada yang lain, perhatikan daftar lengkap nada, simbol, dan frekuensi yang digunakan oleh para bebek (terurut menaik berdasar ketinggian nada), yang diberikan pada tabel di bawah ini:


1/3

10/4/13

Tebak Lagu

Sebagai contoh, misalkan ada dua bebek (bebek Kwek dan bebek Kwak) yang akan menyanyikan sebuah lagu yang sama. Bebek Kwek menyanyikan lagu tersebut dalam nada dasar D4 (d.) dan bebek Kwak menyanyikannya dalam nada dasar E4 (e.). Rangkaian nada yang mereka nyanyikan adalah: Bebek Kwek: d.e.f#e.d. Bebek Kwak: e.f#g#f#e. Sedangkan dalam buku lagu mereka, lagu tersebut akan dituliskan sebagai c.d.e.d.c.. Karena perbedaan nada dasar itulah, meski dapat mengenali nada dengan sangat akurat, Pak Dengklek merasa kesulitan dalam menebak lagu apa yang para bebeknya nyanyikan. Karena itulah, Olimpiade Sains Nasional V Bidang Informatika Pak Dengklek meminta bantuan Anda untuk membuatkan sebuah program yang dapat mengetahui lagu mana yang dinyanyikan para bebek. Informasi yang akan Pak Dengklek berikan pada Anda adalah: 1. Potongan lagu yang didengar oleh Pak Dengklek (dengan nada dasar sesuai yang dinyanyikan bebek yang bersangkutan). 2. Banyaknya lagu yang ada pada buku lagu bebek. 3. Rangkaian nada dari lagu-lagu dalam buku lagu tersebut. FORMAT MASUKAN Baris pertama berisikan serangkaian karakter yang merepresentasikan rangkaian nada yang ingin dicari (sesuai simbol pada tabel pada deskripsi soal). Baris kedua berupa sebuah integer n (1 <= n <= 100) yang menunjukkan banyaknya data lagu yang ada. n-baris berikutnya berisikan data lagu yang tersedia, masing-masing dalam satu baris. Tiap baris masukan rangkaian nada terdiri atas tidak lebih dari 250 karakter. FORMAT KELUARAN Nomor lagu yang di dalamnya terdapat rangkaian nada yang bersesuaian dengan nada yang dicari, atau # jika rangkaian nada yang dicari tidak ditemukan. Penomoran lagu dimulai dari 1 (i.e. baris setelah integer n pada masukan merupakan data lagu ke-1). Jika ada lebih dari satu lagu yang bersesuaian dengan potongan lagu yang diberikan, tuliskan lagu dengan nomor terkecil saja. CONTOH MASUKAN 1 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0508.html

2/3

10/4/13

Tebak Lagu

g.g.g.f.e.d.c. 6 d.c.e.d.c.f.e.d.g.g.g.f.e.d.e. c.d.e.c#d.e.f#a.d.c. c.d#e. c.d.e.f.g.g.g.d.e.f.c.d.e. c.c#d.d#e.f.f#g.g#a.a#b.C. G.F.D#G#G.F.A#A#A#G#G.F.D# CONTOH KELUARAN 1 6 CONTOH MASUKAN 2 c.d.e. 1 C.D.C. CONTOH KELUARAN 2 #


3/3

10/4/13

Ulang Tahun

OSN 2006 : Ulang Tahun Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Beberapa hari lagi, Pak Dengklek akan merayakan ulang tahunnya yang ke61. 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 namanama 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. file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0509.html

1/2

10/4/13

Ulang Tahun

FORMAT KELUARAN Keluarkan Q baris, di mana setiap barisnya berisi nomor telepon dari teman yang ditanyakan oleh Pak Dengklek. 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


2/2

10/4/13

Runtuh

OSN 2006 : Runtuh Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Game (permainan) ini adalah sebuah game yang bertujuan untuk membuat penuh satu baris (horizontal) dari sebuah board (papan) menggunakan beberapa bangun yang disediakan. Jika sebuah baris penuh terisi maka baris tersebut akan dihilangkan dan sisa bangun di atasnya akan "diruntuhkan" satu demi satu turun melewati ruang yang telah kosong sampai menumpuk di atas bangun yang ada di bawahnya. Penumpukan yang terjadi dapat menghasilkan situasi seperti pada saat awal di atas yaitu terdapat baris-baris yang penuh terisi, yang selanjutnya akan dihilangkan lagi (setelah semua runtuh). Demikian berlangsung bisa berulang-ulang sampai tidak ada lagi baris yang penuh terisi. Anda akan diberikan sebuah kondisi board dari suatu game ini untuk ditentukan kondisi akhirnya. Misalnya untuk board seperti di bawah ini:

Kondisi board setelah baris yang terisi penuh dihilangkan, akan menyisakan ruang kosong seperti di bawah ini: file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0510.html

1/3

10/4/13

Runtuh

Bangun-bangun yang terletak di atas baris terbawah yang dihilangkan akan diruntuhkan ke bawah sehingga kondisi board setelah terjadi penurunan adalah seperti di bawah ini:

Dalam contoh di atas kebetulan keruntuhan hanya sekali saja dalam sejumlah testcase bisa terjadi berulang-ulang. FORMAT MASUKAN


2/3

10/4/13

Runtuh

Baris 1: Jumlah baris (1..20) dan kolom (1..8) board. Dipisahkan oleh spasi. Baris 2..jumlah baris+1: Berisi konfigurasi awal board dalam bentuk angka 0 atau 1 sebanyak jumlah kolom. 1 berarti ada bangun pada posisi tersebut, 0 berarti ruang kosong pada posisi tersebut. FORMAT KELUARAN Tuliskan konfigurasi akhir dari board setelah proses penghilangan dan penurunan berhenti. CONTOH MASUKAN 11 6 000000 000000 011100 110011 111111 111000 111111 111111 111001 001100 111011 CONTOH KELUARAN 000000 000000 000000 000000 000000 010000 111000 111001 111101 001110 111011


3/3

10/4/13

Tinggi Kandang Susun

OSN 2007 : Tinggi Kandang Susun Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Selain bebek, Pak Dengklek berkeinginan memelihara kucing dan karena itu ia bermaksud membangun kandang untuk kucing-kucingnya. Harga tanah kini sangat mahal, Pak Dengklek tidak memiliki lahan yang cukup luas untuk membangun kandang berlantai satu, maka kandang susunlah solusi untuk tempat tidur N kucingnya (1 <= N <= 1000000). Namun dalam kasus ini, justru yang kita pedulikan adalah total tinggi dari kandang susun tersebut, bukan luasnya. Sekedar informasi, kucing-kucing Pak Dengklek adalah hewan yang rewel, mereka tidak ingin tempat tinggalnya lebih rendah dari batas yang sudah mereka tentukan. Untuk tiap lantai kandang, Pak Dengklek hanya dapat memasukkan K (1 <= K <= 1000000) kucing secara berurutan, sehingga kucing 1 sampai K pasti akan berada di lantai pertama, kucing ke K+1 sampai 2K pasti akan berada di lantai kedua, dan seterusnya. Agar semua kucing senang, tinggi setiap lantai haruslah nilai maksimal dari batas yang ditentukan oleh kucing-kucing yang ada dalam lantai tersebut. Tugas Anda kini adalah mencari berapa total tinggi dari kandang susun yang akan dibangun Pak Dengklek. Perlu diingat untuk alas dan atap dibutuhkan papan setebal 1 sentimeter, di antara kedua lantai pun ada sekat setebal 1 sentimeter dan tebal-tebal diperhitungkan juga dalam menentukan total tinggi kandang.

itu

harus

FORMAT MASUKAN Baris pertama berisi dua buah bilangan bulat N dan K. Baris ke-2 sampai ke N+1 masing-masing berisi sebuah bilangan Ti yang merupakan batas tinggi yang diinginkan oleh kucing ke-i (dalam sentimeter). FORMAT KELUARAN Sebuah bilangan bulat yang menunjukkan total tinggi kandang susun yang akan Pak Dengklek bangun (dalam sentimeter). file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0511.html

1/2

10/4/13

Tinggi Kandang Susun

CONTOH MASUKAN 1 53 30 20 15 19 29 CONTOH KELUARAN 1 62 CONTOH MASUKAN 2 22 2 2 CONTOH KELUARAN 2 4 Penjelasan Pada contoh 1, total tinggi = 62 = 30 + 29 + 1 (alas) + 1 (atap) + 1 (sekat lantai 1 dan lantai 2)


2/2

10/4/13

Menghitung Ruang Tertutup

OSN 2007 : Menghitung Ruang Tertutup Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Pada suatu hari yang indah, Pak Dengklek bermain-main dengan komputernya. Dia berusaha menggambar sesuatu menggunakan karakterkarakter yang tersedia di keyboard. Setelah lama bermain-main, Pak Dengklek tertarik dengan karakter slash "/", karakter backslash "\", dan karakter period "." pada keyboard, karena dengan karakter-karakter itu dia dapat membuat gambar abstrak seperti gambar berukuran 5 x 5 di bawah ini: ./\.. .\/\. .///. ///./ \/./. Pak Dengklek memiliki kreativitas yang besar. Dari gambar-gambar abstrak yang dibuatnya, dia ingin mengetahui ada berapa ruang tertutup yang dihasilkan oleh gambarnya. Ruang tertutup adalah ruang yang seluruhnya dibatasi oleh dinding. Karakter slash "/" dan backslash "\" berfungsi sebagai dinding. Anggaplah karakter "/" pada suatu kotak tepat menghubungkan titik sudut kanan atas dan kiri bawah kotak itu, dan karakter "\" pada suatu kotak tepat menghubungkan titik sudut kiri atas dan kanan bawah kotak itu. Sedangkan karakter "." mewakili ruang kosong, walaupun tidak semua ruang kosong ditandai dengan karakter ".". Untuk lebih jelasnya, gambar abstrak di atas dapat diterjemahkan menjadi gambar di bawah ini:


1/3

10/4/13


Perhatikan bahwa ruang yang dibatasi dengan garis merah dan garis biru merupakan dua ruang tertutup yang dimaksud. Catatan: ruang yang ditandai dengan X bukan ruang tertutup, karena ruang itu tidak seluruhnya dibatasi oleh dinding (sisi kanan dan sisi bawah terbuka). FORMAT MASUKAN Baris pertama berisi bilangan bulat N dan M (1 <= N, M <= 250) yang merupakan tinggi dan lebar gambar. N baris berikutnya masing-masing memiliki panjang M karakter dan berisi gambar abstrak yang dibuat oleh Pak Dengklek. Gambar abstrak ini hanya terdiri atas karakter "/", "\", dan "." saja. FORMAT KELUARAN Baris pertama berisi sebuah bilangan bulat yang merupakan jumlah ruang tertutup pada gambar abstrak pada masukan. CONTOH MASUKAN 1 55 ./\.. .\/\. .///. ///./ \/./. CONTOH KELUARAN 1 2 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0512.html

2/3

10/4/13


CONTOH MASUKAN 2 56 ../\.. .//\\. .\\.\\ ..\\// ...\/. CONTOH KELUARAN 2 2 CONTOH MASUKAN 3 44 \../ .\/. ./\. /..\ CONTOH KELUARAN 3 0


3/3

10/4/13

Pemberat

OSN 2007 : Pemberat Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Setelah membeli beberapa ekor kucing, kini Pak Dengklek memiliki dua jenis binatang di kebun belakang rumahnya. Kucing dan bebek tentunya. Di belakang rumahnya tersebut, Pak Dengklek juga memiliki sebuah jungkatjungkit untuk kucing dan bebeknya bermain. Agar tidak dinilai pilih kasih, untuk setiap kali permainan jungkat-jungkit, Pak Dengklek selalu mengatur sedemikian rupa sehingga di satu sisi pastilah seekor bebek dan di sisi lainnya pastilah seekor kucing. Sayangnya semua kucing Pak Dengklek gemuk-gemuk sehingga berat kucing terkurus Pak Dengklek pun tetap lebih besar dari berat bebek tergemuk. Oleh karena itu jungkat-jungkit Pak Dengklek sering kali lebih berat ke sisi di mana kucing berada dan permainan pun tidak berjalan dengan mengasyikan. Untuk mengatasi masalah ini, dasar Pak Dengklek yang banyak akalnya, ia menggunakan beberapa pemberat di sisi bebek berada, sedemikian sehingga berat satu sisi dan lainnya kini sama. Sayangnya Pak Dengklek tidak memiliki pemberat dalam setiap ukuran, Pak Dengklek hanya memiliki pemberat dengan ukuran 2^K dimana 0 <= K <= 60. Dan Pak Dengklek hanya memiliki satu buah pemberat untuk setiap ukuran tersebut. Nah, tugas kalian adalah membantu Pak Dengklek untuk menentukan pemberat mana saja yang harus ia gunakan. Asumsikan bahwa input selalu valid dan selalu ada solusi akan input yang diberikan. FORMAT MASUKAN Baris pertama berisi sebuah bilangan bulat yang menunjukkan berat bebek yang akan bermain. Baris kedua berisi sebuah bilangan bulat yang menunjukkan berat kucing yang akan bermain. 1 <= berat bebek, berat kucing <= 2^61. FORMAT KELUARAN file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0513.html

1/2

10/4/13

Pemberat

Beberapa baris dengan satu bilangan bulat setiap barisnya yang merupakan berat dari masing-masing pemberat yang digunakan Pak Dengklek. Keluaran ini diatur dalam keadaan terurut mengecil. CONTOH MASUKAN 1 1 6 CONTOH KELUARAN 1 4 1 CONTOH MASUKAN 2 10 101 CONTOH KELUARAN 2 64 16 8 2 1


2/2

10/4/13

Permutasi Ekspresi

OSN 2007 : Permutasi Ekspresi Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Anda akan diberikan sebuah angka yang panjangnya maksimal 12 digit dan minimal 2 digit. Misalkan Anda diberikan angka 111. Angka tersebut tidak terlalu menarik bukan? Mari kita membuat hal yang lebih menarik dengan menyelipkan tanda '+' atau '-' di antara angka-angka tersebut. Jika Anda menyelipkan tanda '+' di antara setiap dua angka, Anda akan mendapatkan 1+1+1 = 3. Jika Anda menyelipkan tanda '-' di antara setiap dua angka, Anda akan mendapatkan 1-1-1 = -1. Hal yang menarik adalah Anda dapat membuat berbagai ekspresi dari angka 111 ini yang memiliki hasil ekspresi yang berbedabeda. Untuk setiap dua angka yang bersebelahan, Anda dapat memilih untuk menyelipkan tanda '+', tanda '-', atau tidak menyelipkan apa-apa. Jika anda memilih untuk tidak menyelipkan apa-apa, Anda akan mendapatkan 111 = 111. FORMAT MASUKAN Baris pertama berisi sebuah bilangan bulat N yang panjangnya maksimal 12 digit dan minimal 2 digit. Bilangan bulat ini selalu diawali dengan digit positif. FORMAT KELUARAN Baris pertama berisi sebuah bilangan bulat, yang merupakan banyaknya kemungkinan hasil ekspresi yang dapat dibuat dari bilangan N pada masukan. CONTOH MASUKAN 1 111 CONTOH KELUARAN 1 file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0514.html

1/2

10/4/13

Permutasi Ekspresi

7 CONTOH MASUKAN 2 101 CONTOH KELUARAN 2 5 Penjelasan Penjelasan Contoh 1 Tujuh hasil ekspresi yang dimaksud pada contoh keluaran 1 adalah 111 = 111 11+1 = 1+11 = 12 11-1 = 10 1+1+1 = 3 1+1-1 = 1-1+1 = 1 1-1-1 = -1 1-11 = -10 Penjelasan Contoh 2 Lima hasil ekspresi yang dimaksud pada contoh keluaran 2 adalah 101 = 101 10+1 = 11 10-1 = 9 1+0+1 = 1-0+1 = 1+01 = 2 1+0-1 = 1-0-1 = 1-01 = 0


2/2

10/4/13

Deciphering The Mayan Writing

IOI 2006 : Deciphering The Mayan Writing Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Deciphering the Mayan writing has proven to be a harder task than anticipated by the early investigations. After almost two hundred years, very little of it was actually understood. It has been only in the last three decades that real advances have been made. Mayan writing is based on small drawings known as glyphs which represent sounds. Mayan words are normally written as glyphs put together at various positions. One of several problems in deciphering Mayan writing arises in the order of reading. When placing several glyphs in order to form a word, Mayan writers sometimes decided the position based more on their own esthetic views than on any particular rule. This leads to the fact that, even though the sound for many glyphs is known, sometimes archaeologists are not sure how to pronounce a written word. The archaeologists are looking for a special word W. They know the glyphs for it, but they don't know all the possible ways of arranging them. Since they knew you were coming to IOI'06, they have asked for your help. They will provide you with the g glyphs from W and a sequence S of all the glyphs (in the order they appear) in the carvings they are studying. Help them by counting the number of possible appearances of the word W. Write a program that, given the glyphs for W and the sequence S of glyphs in the carvings, counts the number of possible appearances of W in S; that is, every sequence of consecutive g glyphs in S that is a permutation of the glyphs in W. FORMAT MASUKAN LINE 1: Contains 2 space-separated integers that represent g and |S|. file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0515.html

1/2

10/4/13

Deciphering The Mayan Writing

LINE 2: Contains g consecutive characters that represent the glyphs in W. Valid characters are 'a'-'z' and 'A'-Z'; uppercase and lowercase characters are considered different. LINE 3: Contains |S| consecutive characters that represent the glyphs in the carvings. Valid characters are 'a'-z' and 'A'-Z'; uppercase and lowercase characters are considered different. 1 ≤ g ≤ 3 000 , the number of glyphs in W g ≤ |S| ≤ 3 000 000 , where |S| is the number of glyphs in the sequence S FORMAT KELUARAN LINE 1: Must contain the count of possible appearances of W in S. CONTOH MASUKAN 4 11 cAda AbrAcadAbRa CONTOH KELUARAN 2


2/2

10/4/13

N-Queen Problem

N-Queen Problem Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:

queen.PAS / C / CPP 1 detik / test-case 16 MB Standard input (keyboard) Standard output (layar)

Anda diminta untuk membuat sebuah program yang dapat mengeluarkan banyaknya meletakkan N buah ratu (queen) pada papan berukuran N x N (1 ≤ N ≤ 8), sehingga tidak ada ratu yang saling menyerang ratu lainnya pada papan. Ratu dianggap menyerang sebuah ratu lainnya jika ratu lain tersebut berada di kolom yang sama, atau baris yang sama, atau diagonal yang sama dengan sang ratu. Pada gambar, kotak-kotak yang diserang sang ratu diberi warna abu-abu.

FORMAT MASUKAN Baris pertama berisi sebuah bilangan bulat, N. FORMAT KELUARAN Baris pertama berisi sebuah bilangan bulat, yaitu banyaknya kemungkinan peletakkan N ratu di papan berukuran N x N sehingga tidak ada ratu yang menyerang ratu lainnya.


1/2

10/4/13

N-Queen Problem

CONTOH MASUKAN 1 4 CONTOH KELUARAN 1 2 CONTOH MASUKAN 2 2 CONTOH KELUARAN 2 0 Penjelasan Pada kasus N = 4, hanya ada dua konfigurasi yang mungkin, seperti pada gambar.

Pada kasus N = 2, tidak ada cara meletakkan ratu-ratu sehingga mereka tidak saling menyerang.


2/2

10/4/13

Jalan Tol Menuju Roma

Jalan Tol Menuju Roma Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Seorang pengelana yang mengendarai mobil berada di sebuah kota, dan ingin menuju kota Roma. Di negara Italia, ada N (1 ≤ N ≤ 500) buah kota, dan kota-kota ini dihubungkan oleh L buah ruas jalan (1 ≤ L ≤ 125000), di mana sebuah ruas jalan menghubungkan dua kota yang berbeda. Selain itu, ada juga T (1 ≤ T ≤ 125000) buah ruas jalan tol, di mana sebuah ruas jalan tol menghubungkan dua kota yang berbeda. Setiap pasang kota dapat dihubungkan hanya oleh sebuah ruas jalan biasa, atau hanya oleh sebuah ruas jalan tol, atau tidak dihubungkan oleh ruas jalan. Sang pengelana ingin mencapai kota Roma dalam waktu yang secepatcepatnya. Sang pengelana tahu bahwa sebuah ruas jalan biasa atau jalan tol dapat ditempuh dalam waktu 1 jam. Namun, sang pengelana hanya memiliki satu buah tiket jalan tol, yang hanya dapat digunakan untuk melintasi satu ruas jalan tol saja. Selebihnya, sang pengelana harus menggunakan jalan biasa. Sang pengelana juga boleh saja untuk tidak memakai tiket jalan tolnya, jika dia dapat mencapai kota Roma dalam waktu yang secepat-cepatnya. Buatlah program yang dapat mengeluarkan banyak jam paling sedikit untuk mencapai kota Roma dari kota asal. FORMAT MASUKAN Baris pertama berisi lima buah bilangan bulat, masing-masing dipisahkan oleh sebuah spasi: N, L, T, nomor kota awal, dan nomor kota Roma. Kotakota dinomori 1 sampai dengan N. L baris berikutnya masing-masing mendeskripsikan sebuah ruas jalan. Setiap baris terdiri atas dua buah kota, yaitu nomor kedua kota yang dihubungkan oleh ruas jalan tersebut. file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0522.html

1/3

10/4/13


T baris berikutnya masing-masing mendeskripsikan sebuah ruas jalan tol. Setiap baris terdiri atas dua buah kota, yaitu nomor kedua kota yang dihubungkan oleh ruas jalan tol tersebut. FORMAT KELUARAN Baris pertama berisi sebuah bilangan bulat, yaitu banyak jam paling sedikit untuk mencapai kota Roma dari kota asal, dengan atau tanpa menggunakan satu-satunya tiket jalan tol. Dijamin pasti ada rute dari kota asal ke kota Roma. CONTOH MASUKAN 79217 12 13 32 24 43 45 46 57 67 36 56 CONTOH KELUARAN 3 Penjelasan Contoh masukan dapat diilustrasikan dengan gambar di bawah ini. Ruas garis berwarna biru berarti jalan tol. Rute tercepat adalah dari 1 ke 3 ke 6 ke 7.


2/3

10/4/13


Tips Coba pikirkan apakah yang disebut sebuah state dalam masalah pencarian ini.


3/3

10/4/13

Kotak-kotak

Kotak-kotak Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:

kotak.PAS / C / CPP 1 detik / test-case 16 MB Standard input (keyboard) Standard output (layar)

Pak Dengklek memiliki sebuah papan berukuran N x M (1 ≤ N, M ≤ 20). Ketika masih kecil, Pak Dengklek menciptakan sebuah permainan dengan papan tersebut, yang sekarang sudah dipatenkan di desa Sukamaju. Aturan permainan itu seperti berikut ini: Permainan ini menggunakan papan tersebut dan sebuah kelereng. Beberapa kotak-kotak pada papan tersebut akan dipasangi kayu-kayu dengan posisi / atau \. Fungsi kayu-kayu tersebut adalah untuk memantulkan kelereng seperti pada gambar:

Lingkaran-lingkaran menandakan kelereng dan tanda panah menandakan arah gerak kelereng ketika dipantulkan oleh kayu-kayu. Kayu-kayu itu juga memiliki keunikan. Tepat setelah kelereng menabrak sepotong kayu dan dipantulkan, kayu itu berubah posisi (jika semula / menjadi \, dan jika semula \ menjadi /). Jika kayu itu ditabrak lagi, kayu itu akan berubah posisi lagi. file:///E:/Olimpiade Komputer/Problem/pjj1/chapter 5/problems/pjj0523.html

1/4

10/4/13

Kotak-kotak

Nah misalkan Pak Dengklek memiliki papan dengan konfigurasi seperti ini (tanda titik artinya tidak ada kayu pada kotak tersebut). .... .... /./. .../ Misalkan Pak Dengklek memasukkan kelereng dari atas, kolom ketiga dari kiri. Maka kelereng itu akan dipantulkan ke arah kiri, lalu dipantulkan ke bawah, lalu keluar ke arah bawah dari kolom pertama dari kiri. Jadi setelah bola keluar dari bawah, konfigurasi papan menjadi seperti di bawah ini. Ingat bahwa jika sebuah kayu ditabrak kelereng, kayu itu akan berubah posisi. Dan sebuah kayu mungkin saja ditabrak kelereng beberapa kali sebelum kelereng itu keluar dari papan. .... .... \.\. .../ Nah Pak Dengklek ditantang temannya untuk menjawab soal ini: Diberikan posisi di mana kelereng dimasukkan (dari kiri, kanan, atas, atau bawah, dan pada kolom / baris ke berapa), di manakah kelereng akan keluar, dan berapa kali dipantulkan sebelum keluar? Pak Dengklek hanya diberi waktu satu detik untuk berpikir, jadi dia ingin Anda membuat program untuknya untuk menjawab pertanyaan tersebut. FORMAT MASUKAN Baris pertama berisi dua buah bilangan bulat, N dan M, dipisahkan spasi. N adalah jumlah baris dan M adalah jumlah kolom. Baris kedua berisi sebuah karakter dan sebuah bilangan bulat, dipisahkan spasi. Jika karakternya adalah "L", artinya kelereng dimasukkan dari kiri (Left). Bilangan bulatnya adalah nomor baris dari atas. Jika karakternya adalah "R", artinya kelereng dimasukkan dari kanan (Right). Bilangan bulatnya adalah nomor baris dari atas. file:///E:/Olimpiade Komputer/Problem/pjj1/chapter 5/problems/pjj0523.html

2/4

10/4/13

Kotak-kotak

Jika karakternya adalah "T", artinya kelereng dimasukkan dari atas (Top). Bilangan bulatnya adalah nomor kolom dari kiri. Jika karakternya adalah "B", artinya kelereng dimasukkan dari bawah (Bottom). Bilangan bulatnya adalah nomor kolom dari kiri. Penomoran kolom dimulai dari kiri, dengan kolom terkiri diberi nomor 1. Penomoran baris dimulai dari atas, dengan baris teratas diberi nomor 1. Setelah itu, N baris berikutnya berisi M karakter. N baris ini adalah konfigurasi papan, dengan setiap karakter adalah ".", "/", atau "\" seperti dijelaskan di atas. FORMAT KELUARAN Baris pertama berisi sebuah karakter dan sebuah bilangan bulat, dipisahkan sebuah spasi. Karakter dapat bernilai "L", "R", "T", atau "B", yang menandakan arah keluar kelereng. Jika karakter bernilai "L" atau "R", bilangan bulat sesudahnya menunjukkan nomor baris tempat kelereng keluar. Jika karakter bernilai "T" atau "B", bilangan bulat sesudahnya menunjukkan nomor kolom tempat kelereng keluar. Baris kedua berisi sebuah bilangan bulat, yang menandakan berapa kali kelereng tersebut dipantulkan sebelum keluar dari papan. CONTOH MASUKAN 1 44 T3 .... .... /./. .../ CONTOH KELUARAN 1 B1 2 CONTOH MASUKAN 2

file:///E:/Olimpiade Komputer/Problem/pjj1/chapter 5/problems/pjj0523.html

3/4

10/4/13

Kotak-kotak

22 T1 \\ \/ CONTOH KELUARAN 2 T2 6 Penjelasan Untuk kasus kedua, kelereng tersebut akan dipantulkan ke kanan, lalu ke bawah, lalu ke kiri, lalu ke atas, lalu ke kanan (perhatikan bahwa "\"telah berubah menjadi "/"), lalu ke atas (perhatikan bahwa "\"telah berubah menjadi "/"), lalu keluar.

file:///E:/Olimpiade Komputer/Problem/pjj1/chapter 5/problems/pjj0523.html

4/4

10/4/13

5 Segmen Garis

5 Segmen Garis Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Anda diminta untuk membuat program yang menentukan apakah sebuah segmen garis yang diberikan berpotongan dengan sebuah segiempat yang diberikan. Sebuah garis dikatakan berpotongan dengan segiempat jika ada minimal sebuah titik yang dilalui keduanya. Segiempat dalam soal ini adalah 4 buah garis lurus yang menjadi sisinya saja, tidak termasuk daerah di dalamnya. Garis dalam soal ini adalah sepotong garis lurus yang dimulai dari sebuah titik awal hingga titik akhir. FORMAT MASUKAN Baris pertama berisi sebuah bilangan bulat N (N ≤ 200000), jumlah kasus yang ditanyakan. N baris berikutnya berisi data untuk setiap kasus, yang terdiri dari 8 buah bilangan bulat, x1, y1, x2, y2, x3, y3, x4, y4 (-100 ≤ x,y ≤ 100) 4 bilangan pertama menjelaskan deskripsi segiempat dimana (x1,y1), (x1,y2), (x2,y1), (x2,y2) merupakan titik-titik sudut dari segiempat. 4 bilangan selanjutnya menyatakan titik awal (x3,y3) dan titik akhir (x4,y4) dari garis. FORMAT KELUARAN N baris, tiap baris berisi "YA" atau "TIDAK". Keluarkan "YA" jika garis dan segiempat pada kasus itu berpotongan, "TIDAK" jika tidak. CONTOH MASUKAN 4 00654387 -12 20 24 -35 -4 3 2 -1 12342561 3 4 8 9 2 1 12 7


1/2

10/4/13

5 Segmen Garis

CONTOH KELUARAN YA TIDAK YA YA


2/2

10/4/13

Tebak Segiempat

Tebak Segiempat Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Pak Dengklek dan bebeknya baru saja menemukan permainan baru yaitu Tebak Segiempat. Permainannya sangat sederhana, yakni sebagai berikut: Pertama, pemain pertama menggambar N buah segiempat (putih) pada sebuah kertas yang sudah diberi kordinat kartesius (-1000 ≤ x,y ≤ 1000) dengan skala 1 satuan = 1 cm. Pemain pertama hanya memberitahu N dan total luas daerah segiempat yang dia gambar kepada pemain kedua, tanpa menunjukan gambarnya. Selanjutnya giliran pemain kedua menggambar M buah segiempat (hitam) pada kertas serupa. Kemudian kedua gambar tersebut dicocokan. Luas daerah yang dilalui kedua segiempat hitam dan putih (daerah abu-abu) dihitung total luasnya. Bila luasnya lebih besar dari setengah total luas daerah putih, dan juga lebih besar dari setengah total luas daerah hitam, maka pemain kedua menang. Jika tidak pemain pertama yang menang. (Tidak ada dua segiempat putih yang saling berpotongan. Begitupula dengan segiempat hitam, tidak berpotongan dengan segiempat hitam lainnya) Tugas Anda kali ini bukanlah untuk memainkan permainan ini. :D Anda hanya diminta oleh Pak Dengklek untuk menghitung total luas daerah abuabu, daerah yang dilalui oleh kedua segiempat, putih maupun hitam. FORMAT MASUKAN Baris pertama berisi bilangan bulat N, jumlah segiempat putih. N baris selanjutnya berisi deskripsi setiap segiempat putih. Baris ke i+1 berisi 4 bilangan bulat x1i, y1i, x2i, y2i yang menyatakan bahwa segiempat putih ke i memiliki titik-titik sudut (x1i,y1i), (x1i,y2i), (x2i,y1i), (x2i,y2i). file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0525.html

1/2

10/4/13

Tebak Segiempat

Baris selanjutnya berisi bilangan bulat M, jumlah segiempat hitam. M baris selanjutnya berisi deskripsi setiap segiempat hitam. Baris ke N+j+2 berisi 4 bilangan bulat x1j, y1j, x2j, y2j yang menyatakan bahwa segiempat hitam ke j memiliki titik-titik sudut (x1j,y1j), (x1j,y2j), (x2j,y1j), (x2j,y2j). FORMAT KELUARAN Keluaran hanya berupa sebuah bilangan bulat L, yaitu luas daerah abu-abu (daerah yang dilalui oleh kedua jenis segiempat, putih maupun hitam) dalam centimeter persegi. CONTOH MASUKAN 2 1234 3163 1 0253 CONTOH KELUARAN 4


2/2

10/4/13

Lingkar Sebesar-Besarnya

Lingkar Sebesar-Besarnya Nama Program: Batas Run-time: Batas Memori: Nama Berkas Masukan: Nama Berkas Keluaran:


Bebek Pak Dengklek baru saja belajar membuat lingkaran dengan titik pusat (Xp,Yp) dan jari-jari R. Pak Dengklek yang melihat gambar lingkaranlingkaran tersebut tidak ingin kalah dari bebeknya. Dengan menggunakan kertas yang sudah ada gambar N lingkaran, Pak Dengklek ingin menggambar sebuah lingkaran sebesar-besarnya tanpa memotong lingkaran yang sudah ada. (Lingkaran-lingkaran tersebut boleh saja bersentuhan tapi tidak berpotongan) Untuk itu Pak Dengklek meminta Anda untuk menentukan berapa maksimum besar jari jari lingkaran yang bisa dibuat bila titik pusatnya sudah ditentukan di (Xp,Yp). (Tidak ada lingkaran yang berada di dalam lingkaran lain, dan tentu saja pertanyaan Pak Dengklek tidak mungkin menggunakan titik yang berada di dalam lingkaran yang sudah ada) FORMAT MASUKAN Baris pertama berisi sebuah bilangan bulat N (1 ≤ N ≤ 10000), jumlah lingkaran yang sudah ada pada kertas gambar. N baris berikutnya berisi deskripsi lingkaran-lingkaran yang sudah ada. Baris ke i+1 berisi 3 buah bilangan bulat Xpi, Ypi, Ri (-10000 ≤ Xpi,Ypi ≤ 10000 ; 1 ≤ Ri ≤ 10000) yang menyatakan lingkaran ke i memiliki titik pusat (Xpi,Ypi) dan jari-jari Ri. Baris selanjutnya berisi sebuah bilangan bulat M (1 ≤ M ≤ 10000), jumlah pertanyaan Pak Dengklek. M baris berikutnya berisi pertanyaanpertanyaan Pak Dengklek. Baris ke N+j+2 berisi 2 buah bilangan bulat Xpj, Ypj yang berarti Pak Dengklek menanyakan berapa jari-jari lingkaran maksimum yang dapat dibuat bila titik pusatnya di (Xpj,Ypj). FORMAT KELUARAN Terdiri dari M buah baris. Baris ke j berisi sebuah bilangan Rj, jari-jari file:///E:/Olimpiade Komputer/Problem/TOKI Pack/PJJ OSN 2010/pjj0526.html

1/2

10/4/13

Lingkar Sebesar-Besarnya

lingkaran maksimum yang dapat dibuat untuk lingkaran dengan titik pusat (Xpj,Ypj). Keluarkan Rj dengan ketelitian 2 angka dibelakang koma. CONTOH MASUKAN 3 002 902 551 4 03 40 52 CONTOH KELUARAN 1.00 2.00 2.00


2/2

TEKS : Pengenalan Sistem Online Judge

Recommend Documents