Olimpiade Internasional dalam Informatika (bahasa Inggris: International Olympiad in Informatics/IOI) adalah kompetisi pemrograman tahunan yang paling bergengsi bagi siswa sekolah menengah.
Pelajar SMA Indonesia yang tergabung dalam Tim Olimpiade Komputer Indonesia (TOKI) berhasil meraih empat medali di ajang International Olympiad in Informatics (IOI) 2020. Dengan perolehan medali ini Indonesia berada di peringkat 13 dari 87 negara peserta IOI 2020.
Indonesia bersaing dengan 347 peserta dari berbagai negara, termasuk tuan rumah Singapura dalam IOI ke-32 ini. Ajang ini merupakan olimpiade sains di bidang informatika khususnya pemrograman yang diselenggarakan setiap tahun. IOI ke-32 ini dilaksanakan secara daring pada 13-19 September.
Tim Indonesia terdiri dari empat siswa terbaik Indonesia, yaitu Pikatan Arya Bramajati asal SMA Semesta BBS Semarang yang meraih medali emas, Rama Aryasuta Pangestu asal SMAK Kanisius Jakarta yang meraih medali perak, Dasco Gabriel asal SMA Sutomo 1 Medan dan Edbert Geraldy Cangdinata asal SMA Sutomo 1 Medan yang masing-masing meraih medali perunggu.
Berikut Beberapa Lampiran Soal dan Pembahasan OSK, OSP, OSN, KSK, KSP, KSN
Soal, Kunci dan Pembahasan OSK Informatika ( Komputer ) 2019
1. Sebuah Tangki air memiliki enam buah kran air dibagian dasarnya, jika semua kran dibuka maka tangki yang terisi penuh akan habis isinya dalam 8 jam. Berapa jamkah yang dibutuhkan untuk menghabiskan isi tangki bila hanya 4 kran yang dibuka.
Pembahasan
Jika semua kran dibuka dalam 1 jam maka 1/8 isi tangki akan habis.
Jika hanya 4 kran yang dibuka dalam 1 jam maka akan diperoleh 4/6 × 1/8 = 1/12 isi tangki habis
Sehingga membutuhkan waktu 12 jam untuk menghabiskan semua isi tangki.
2. Jika operasi (a mod b) adalah sisa dari operasi pembagian a oleh b, berapakah hasil penjumlahan dari ( 7⁷.⁷⁷⁷.⁷⁷⁷ mod 100) + (5⁵.⁵⁵⁵.⁵⁵⁵ mod 10)
Pembahasan
7⁰ = 1
7¹ = 7
7² = 49
7³ = 343
7⁴ = 2.401
Sehingga bisa disimpulkan akan selalu kembali setiap pengulangan 4x. Maka diperoleh
7⁷.⁷⁷⁷.⁷⁷⁷ ^ (mod 4). Mod 100
= 7¹ mod 100
= 7
Dan 5⁵.⁵⁵⁵.⁵⁵⁵ mod 10 = 5
Sehingga dapat disimpulkan
( 7⁷.⁷⁷⁷.⁷⁷⁷ mod 100) + (5⁵.⁵⁵⁵.⁵⁵⁵ mod 10)
= 7 + 5
= 12
3. Berapakah banyaknya angka antara 100 hingga 1000 yang habis dibagi 3 dan 5 tetapi tidak habis dibagi oleh 30
Penyelesaian
(|1000/3*5| - |100/3*5|) - (|1000/30| - |100/30|)
= (66 - 6) - (33 - 3)
= 60 - 30
= 30
Maka dapat disimpulkan terdapat 30 angka antara 100 sampai 1000 yang habis dibagi 3 dan 5 tetapi tidak habis dibagi 30
Perhatikan dan pahami naskah berikut.
Ikan Dek Makrit saat ini berjumlah 120 ekor yang dinomorinya 1 sampai 120. Seluruh ikan dek Makrit yang bernomor genap suka makanan rasa bayam, ikan yang nomornya habis dibagi 5 suka makanan rasa pisang, dan ikan yang nomornya habis dibagi 7 suka makanan rasa kangkung.
4. Berapa banyak ikan yang menyukai rasa kangkung tapi tidak menyukai rasa bayam.
Penyelesaian
Bisa menggunakan diagram venn atau menggunakan metode Inklusi dan Ekslusi.
Berikut.
Jumlah ikan yang menyukai rasa kangkung - jumlah ikan yang menyukai rasa kangkung dan bayam
= (|120/7| - |120/2×7|)
= 17 - 8 = 9
5. Berapa banyak ikan yang tidak menyukai ketiga rasa.?
Penyelesaian.
Jumlah total ikan - jumlah ikan yang hanya suka 1 macam rasa + jumlah ikan yang suka hanya 2 macam rasa - jumlah ikan yang suka semua rasa
Perhatikan naskah berikut (lanjutan dari naskah sebelumnya).
Dek Makrit kemudian membeli 80 ekor ikan lagi sehingga sekarang totalnya adalah 200. Ternyata Nek Dengklek ibunya pak Dengklek, hobi mewarnai makanan ikan sehingga selain beragam rasa, makanan juga berwarna warni. Dengan makan yang berwarna warni, ikan-ikan dek Makrit semakin suka makan, dari 200 ekor itu, 100 ekor menyukai makanan berwarna kuning, 70 ekor menyukai warna biru, dan 140 menyukai makanan berwarna merah. 40 diantaranya menyukai makanan berwarna kuning dan juga biru, 30 menyukai makanan berwarna biru dan juga merah, dan 60 menyukai makan berwarna kuning dan merah, ada 10 ekor yang tidak menyukai ketiganya.
Dari naskah tersebut tentukanlah
1. Berapa jumlah ikan yang tidak menyukai semua warna.?
2. Berapa jumlah ikan yang hanya menyukai satu warna.?
Untuk menentukan keterbagian bilangan berpangkat, sering kita gunakan istilah kongruen (=_), dan modulo (Mod). Suatu bilangan a dikatakan kongruen dengan b modulo n dapat dituliskan dengan a =_ b mod (n) jika a dan b memberikan sisa yang sama apabila dibagi oleh n.
(an + b)^m = b^m mod (n)
Contoh:
Tentukanlah sisa dari 7²⁰¹⁸ dibagi oleh 5
Penyelesaian.
Cara 1
Dalam hal ini, lebih dahulu kita cari k sehingga 7^k = 5 × l ± 1
7¹ = 7
7² = 49
7³ = 343
7⁴ = 2401 = 5 × 480 + 1
Jadi
7²⁰¹⁸ =_ 7⁴*⁵⁰⁴+² mod 5
=_ (7⁴)⁵⁰⁴ × 7² mod 5
=_ (5 × 480 + 1)⁵⁰⁴ × 7² mod 5
=_ (1)⁵⁰⁴ × 49 mod 5
=_ 49 mod 5
Jadi sisa pembagian 7²⁰¹⁸ oleh 5 adalah 4.
Cara 2.
Sebelumnya kita ingat bahwa bilangan yang habis dibagi 5 cukup diperhatikan pada satuanya, sehingga bisa kita cek bahwa.
Jika angka satuanya adalah 0 atau 5 maka sisanya adalah 0
Jika angka satunya adalah 1 dan 6 maka sisanya adalah 1
Jika angka satunya adalah 2 dan 7 maka sisanya adalah 2
Jika angka satuanya adalah 3 dan 8 maka sisanya adalah 3
Jika angka satuanya adalah 4 atau 9 maka sisanya adalah 4
Sehinga
Kita harus mencari pola pangkat dari bilangan tersebut.
7¹ = 7
7² = 49
7³ = 343
7⁴ = 2401
7⁵ = 16.807
Artinya pola satuan dari pangkat tersebut selalu berulang setiap 4 kali sehingga.
Selanjutnya kita membagi pangkatnya sesuai dengan polanya.
2018 mod 4 bersisa 2
Jadi 7² = 49 dengan satuanya adalah 9 maka sisa dari Pembagian tersebut adalah 4
B. Bilangan Prima dan Kuadrat
Bilangan prima adalah bilangan asli yang hanya dapat dibagi oleh bilangan itu sendiri dan satu. Dengan perkataan lain, bilangan prima hanya mempunyai dua faktor yaitu 1 bilangan itu sendiri. Misalnya 2, 3, 5, 7, 11 , . . .
Bilangan asli yang mempunyai lebih dari dua faktor disebut sebagai bilangan komposit. Misalnya 4, 6, 8, 9, . . .
Teorema (Topik eratosthenes)
Untuk setiap bilangan komposit n ada bilangan prima p sehingga p | n dan p ≤ √n
Teorema tersebut mempunyai makna "jika tidak ada bilangan prima p yang dapat membagi n dengan p ≤ √n maka n adalah bilangan prima".
Contoh.
Tentukan bilangan-bilangan berikut merupakan bilangan prima atau komposit.
a. 157 b. 221
Penyelesaian
a. Bilangan prima ≤ √157 adalah 2, 3, 5, 7, 11 karena tidak ada dari bilangan-bilangan tersebut yang dapat membagi 157 maka 157 merupakan bilangan prima
b. Bilangan prima yang ≤ √221 adalah 2, 3, 5, 7, 11, 13 karena dari bilangan tersebut ada yang bisa membagi 221 yaitu 13 | 221 maka 221 adalah bilangan komposit.
Untuk Penjelasan lebih lengkap, Yuk dinonton video berikut.
Untuk Soal latihan.
1. Tentukan angka terakhir dari 777³³³
2. Tentukan apakah bilangan berikut termasuk dalam bilangan prima atau komposit. 123, 349 dan 371
3. Berapakah sisa pembagian dari (43⁴³)⁴³ oleh 100
Secara umum suatu bilangan yang dapat dibagi dapat dinyatakan kedalam bentuk.
untuk sebarang a dan b, bilangan bulat dengan a ≠ 0, maka terdapat m dan n, bilangan bulat yang tunggal sedemikian sehingga b dapat dinyatakan sebagai
b = (a*m) + n atau b = am + n, dengan 0 ≤ n < │a│
a, kemudian disebut sebagai pembagi, m disebut hasil bagi dan n disebut sebagai sisa hasil bagi. pernyataan b = am + n, biasanya disebut juga sebagai algoritma pembagian. untuk kasus n = 0, maka b dikatakan habis dibagi oleh a. Akibat dari pernyataan tersebut muncul suatu definisi yaitu.
Suatu bilangan bulat b dikatakan habis dibagi oleh suatu bilangan bulat tidak nol, jika ada suatu bilangan bulat m sedemikian sehingga b = am. atau dapat dituliskan sebagai a │ b (dibaca a habis membagi b)
Sifat-Sifat pada hasil bagi.
jika a│b maka a│bc untuk sembarang c bilangan bulat
jika a│b dan b│c maka a│c
jika a│b dan a│c maka a│bx + cy untuk x dan y, sembarang bilangan bulat.
jika a│b dan b│a maka a = ±b
jika a│b dan b ≠ 0maka │a│ ≤ │b│
2. Algoritma Euclide
Defenisi
Diberikan dua bilangan bulat a dan b dengan a > b > 0 maka FPB(a,b) dapat dicari dengan mengulang algoritma pembagian
Contoh :
Tentukan FPB (4840,1512)
Penyelesaian.
4840 = 1512 * 3 + 304
1512 = 304 * 4 + 296
304 = 296 * 1 + 8
296 = 8 * 37 + 0
maka kta peroleh FPB (4840,1512) = 8
Akibat dari teorema Algoritma Euchlide yaitu untuk setiap FPB(a,b) maka terdapat bilangan bulat x dan y sehingga FPB(a,b) = ax + by.
sehingga dari contoh diatas dapat dinyakan sebagai berikut.
8 = 304 - 296
= 304 - [1512 - (304 * 4)]
= (304 * 5) - 1512
= [(4840 - 1512*3)*5 -1512
= 4840 * 5 - 1512 * 16
jadi nilai x = 5 dan y = 16
Akibat Selanjutnya dari teorema algoritma euclide yaitu Persamaan linear diophantine.
3. Persamaan linear Diophantine
Teorema
Suatu Persamaan linear diophantine ax + by = c dengan a, b dan c bilangan bulat mempunyai penyelesaian bilangan bulat, jika dan hanya jika FPB(a,b) membagi habis c.
Contoh
Tentukan penyelesaian umum persamaan diophantine 754x + 221y = 13
Penyelesaian
Dengan menggunakan algoritma euclid diperoleh FPB(754,221) = 13, karena 13│13, akibatnya persamaan diatas mempunyai penyelesaian bilangan bulat.
kita akan mencari nilai dari m dan n sehingga
13 = m * 754 + n * 221 Karena
13 = 5 *754 - 17 * 221 maka m = 5 dan n = -17 jadi penyelesaian umumny adalah.
1. Jika A679B adalah bilangan yang habis dibagi 72 tentukanlah nilai dari A dan B.
Penyelesaian
Perhatikan Bahwa 72 = 8 .9 karena 72 | A679B, maka 9 | A679B dan 8 | A679B Sehingga dari bentuk ini dapat disimpulkan bahwa :
Agar A679B habis dibagi 8, maka haruslah 790 + B habis dibagi 8. sehingga diperoleh Nilai B adalah 2. Jadi bilangan A679B sekarang adalah A6792.
Kemudian A6792 habis dibagi oleh 9 maka haruslah A + 6 + 7 + 9 + 2 juga harus habis dibagi oleh 9, sehingga kita peroleh nilai A yang mungkin adalah 3.
Jadi, A = 3 dan B = 2, Sehingga A679B = 36792
2. Tentukan Banyaknya pembagi positif dari 2010
Penyelesaian
untuk bentuk soal yang seperti sebaiknya pengerjaannya langsung dicoba secara manual dimana hanya ada bilangan positif dikali positif yang menghasilkan bilangan positif jika harus pembagi positif
2010 = 1 . 2010
= 2 . 1005
= 3 . 670
= 5 . 402
= 6 . 335
= 15 . 134
= 10 . 201
= 30 . 67
Jadi ada 16 Buah pembagi positif dari 2010
3. Misalkan n adalah bilangan asli. Buktikan bahwa n^3 + 5n habis dibagi oleh 6
Penyelesaian
n^3 + 5n = n^3 - n + 6n
= n (n^2-1) + 6n
= n (n-1) (n+1) + 6n
= (n - 1 ) n (n + 1 ) + 6n
karena (n - 1 ) n (n + 1 ) merupakan ciri dari tiga bilangan asli berurutan maka
6 | (n - 1 ) n (n + 1 ) Selain itu 6 | 6n Sehingga dari bentuk tersebut dapat dinyatakan nahwa n^3 + 5n habis dibagi oleh 6
4. Untuk pejabat pengelola suatu kelas, memerlukan 3 pengurus, yaitu ketua kelas, sekretaris dan bendahara. Tersedia 7 calon. Banyaknya macam susunan pengurus kelas yang mungkin adalah.
Penyelesaian
Karena akan dipilih 3 orang untuk menjadi pengurus kelas dari 7 orang calon serta urutanya diperhatikan (Ketua, Sekretaris dan Bendahara), maka ini merupakan masalah permutasi 3 unsur dari 7 unsur, yakni :
P (7,3) = 7!/ (7-3)! = 7!/4! = 7.6.5 = 210
Jadi banyaknya macam susunan pengurus yang mungkin adalah 210 susunan..
Peluang merupakan kemungkinan terjadinya sautu kejadian, yang besarnya antara 0 dan 1, Untuk suatu peluang kejadian yang sudah pasti terjadi memiliki nilai 1, misalnya matahari terbit dari timur. Peluang dengan nilai Nol yaitu peluang yang tidak mungkin terjadi, Tuhan itu ada banyak.
1. Kaidah Pencacahan
Faktorial
n! = n x (n-1) x (n-2) x (n-3) x . . . x 3 x 2 x 1
Dimana n! = perkalian n bilangan Asli
0! = 1
1! = 1
Permutasi
Permutasi merupakan suatu penyusunan unsur-unsur sejumlah n yang tiap kali diambil sejumlah k dengan memperhatikan urutanya.
Permutasi dengan unsur yang sama
Jika Pada sejumlah n unsur yang ada terdapat tepat a unsur yang sama, b unsur yang sama dan seterusnya, kalian bisa menghitung banyak permutasi dari n unsur tersebut dengan menggunakan rumus:
Permutasi Siklis
Merupakan permutasi dimana objeknya disusun dalam bentuk lingkaran
Kombinasi
Adalah susunan unsur-unsur yang urutanya tidak terlalu diperhatikan. Kombinasi dapat dinyatakan dengan rumus :
