Solusi OSNK Informatika SMA 2022 (Beritaedukasi - Net) - 1 [PDF]

Zitiervorschau

Pembahasan OSN-K Informatika SMA 2022 Oleh: Aswad H. Mangalaeng beritaedukasi.net Bagian A : Analitika / Logika 1. Perhatikan operasi logika berikut! P = ((not A) and B) or (((not C) or D) and E) Q = ((not A) or B) and (((not C) and (not D)) or (not E)) R = P and Q Jika nilai A = True, B = True, C = True, D = True, dan E = False, tentukan nilai P, Q dan R berturut-turut? A. P=False, Q= True, R= False B. P=False, Q= False, R= False C. P=True, Q= True, R= True D. P=True, Q= False, R= False E. P=False, Q= True, R= True Jawab: A P = ((not A) and B) or (((not C) or D) and E) P = (F and T) or ((F or T) and F) = F or (T and F) = F or F = F P = False Q = ((not A) or B) and (((not C) and (not D)) or (not E)) Q = (F or T) and ((F and F) or T) = T and (T or T) = T and T = T Q = True R = P and Q = False and True = False Diperoleh P=False, Q= True, R= False.

2. Dalam pemilihan Ketua Asosiasi Bebek, terdapat sekitar 120 bebek yang akan melakukan voting dengan tiga kandidat ketua yaitu Kwak, Kwik, dan Kwek. Dalam pemilihan ini, setiap bebek boleh tidak melakukan voting atau melakukan voting ke lebih dari satu kandidat. Diketahui bahwa ada 65 bebek yang memilih Kwak, 45 bebek memilih Kwik, dan 42 bebek yang memilih Kwek. Kemudian diketahui juga bahwa ada 20 bebek yang memilih Kwak dan Kwik sekaligus, 25 bebek memilih Kwak dan Kwek

sekaligus, dan 15 bebek yang memilih Kwik dan Kwek sekaligus. Secara aturan jika bebek memilih hanya satu kandidat maka seluruh suara bulat (nilai 3) akan diberikan kepada kandidat tersebut, jika bebek memilih lebih dari satu kandidat maka suara bulat (nilai 3) akan dibagi rata sebanyak kandidat yang dipilih. Kandidat yang mendapatkan suara terbesar pertama, kedua dan ketiga berturut-turut akan menjadi Ketua, Wakil Ketua dan Sekretaris. Manakah pernyataan berikut yang benar? A. Kwak akan menjadi Wakil Ketua. B. Kwik akan menjadi Sekretaris C. Kwek akan menjadi Sekretaris D. Kwik akan menjadi Ketua. E. Kwek akan menjadi Wakil Ketua. Jawab: C Misalkan: A adalah banyaknya bebek yang memilih Kwak → 𝐴 = 65. B adalah banyaknya bebek yang memilih Kwik → 𝐵 = 45. C adalah banyaknya bebek yang memilih Kwek → 𝐶 = 42. 𝐷 adalah banyaknya bebek yang memilih Kwak dan Kwik sekaligus → 𝐷 = 20. E adalah banyaknya bebek yang memilih Kwak dan Kwek sekaligus → 𝐸 = 25. F adalah banyaknya bebek yang memilih Kwik dan Kwek sekaligus → 𝐹 = 15. G adalah banyaknya bebek yang memilih Kwak, Kwik dan Kwek sekaligus. Maka, 120 = 𝐴 + 𝐵 + 𝐶 − 𝐷 − 𝐸 − 𝐹 + 𝐺 120 = 65 + 45 + 42 − 20 − 25 − 15 + 𝐺 𝐺 = 120 − 92 = 28 Diperoleh, ada 28 bebek yang memilih Kwak, Kwik dan Kwek sekaligus. Total voting yang diperoleh adalah Kwak : (65 × 3) + (20 × 1.5) + (25 × 1.5) + (28 × 1) = 290,5 Kwik : (45 × 3) + (20 × 1.5) + (15 × 1.5) + (28 × 1) = 215,5 Kwek : (42 × 3) + (25 × 1.5) + (15 × 1.5) + (28 × 1) = 214 Jadi disimpulkan bahwa •

Kwak akan menjadi Ketua

• •

Kwik akan menjadi Wakil Ketua Kwek akan menjadi Sekretaris

3. Jika 𝑛 adalah bilangan bulat positif yang memenuhi persamaan 7𝑛

4 −3𝑛2 −4

= 11𝑛

4 −3𝑛2 −4

berapakah digit terakhir dari nilai 𝑛2022 ? A. 2 B. 4 C. 8 D. 0 E. 6 Jawab: B Persamaan di soal hanya bernilai benar jika 𝑛4 − 3𝑛2 − 4 = 0 𝑛4 − 3𝑛2 − 4 = (𝑛2 + 1)(𝑛 − 2)(𝑛 + 2) = 0 Diperoleh 𝑛 = ±𝑖, 𝑛 = 2 dan 𝑛 = −2. Karena 𝑛 adalah bilangan bulat positif, maka nilai 𝑛 yang memenuhi hanyalah 𝑛 = 2. Mencari digit terakhir dari nilai 𝑛2022 sama saja dengan menghitung 𝑛2022 𝑚𝑜𝑑 10. Perhatikan bahwa : Untuk suatu bilangan bulat 𝑗 > 0, berlaku 24𝑗 ≡ 6 𝑚𝑜𝑑 10 24𝑗+1 ≡ 2 𝑚𝑜𝑑 10 24𝑗+2 ≡ 4 𝑚𝑜𝑑 10 24𝑗+3 ≡ 8 𝑚𝑜𝑑 10 Maka, untuk 𝑛 = 2, diperoleh 22022 = 24×505+2 ≡ 4 𝑚𝑜𝑑 10. Ini artinya, digit terakhir dari nilai 𝑛2022 adalah 4.

4. Berapakah nilai digit terakhir dari 762575 × 126179 ? A. 1 B. 3

C. 5 D. 9 E. 7 Jawab: D Diketahui : Untuk suatu bilangan bulat 𝑗 ≥ 0, berlaku 74𝑗 ≡ 1 𝑚𝑜𝑑 10 74𝑗+1 ≡ 7 𝑚𝑜𝑑 10 74𝑗+2 ≡ 9 𝑚𝑜𝑑 10 74𝑗+3 ≡ 3 𝑚𝑜𝑑 10 (762575 × 126179 )𝑚𝑜𝑑 10 ≡ (75 × 79 )𝑚𝑜𝑑 10 = 714 𝑚𝑜𝑑 10 = 74×3+2 𝑚𝑜𝑑 10 ≡ 9 𝑚𝑜𝑑 10 Jadi, nilai digit terakhir dari 762575 × 126179 adalah 9.

5. Diketahui ada enam kota A, B, C, D, E, dan F sebagai berikut:

Dua kota dikatakan terhubung jika ada jalan (divisualisasikan sebagai garis) yang menghubungkan keduanya dengan jarak dalam kilometer. Pak Dengklek ditugasi untuk memasang kabel internet di atas beberapa jalan yang ada sedemikian sehingga setiap kota bisa terhubung baik secara langsung maupun tidak langsung (melalui kota lainnya). Berapa panjang kabel minimal yang harus disiapkan oleh Pak Dengklek? A. 25 B. 27 C. 29 D. 32 E. 33

Jawab: B Kasus Minimum Spanning Tree. Bisa gunakan algoritma Prim dan algoritma Kruskal. Kali ini kita pakai metode Kruskal. Langkah-langkah: 1. Graf pada awalnya hanya terdiri dari node-node saja. 2. Tambahkan edge berdasarkan bobot yang paling kecil dan edge yang ditambahkan tidak membentuk sirkuit. 3. Lakukan langkah 2 sebanyak n-1 kali. Karena jumlah node adalah 6, maka 𝑛 − 1 = 6 − 1 = 5 kali. Mulai dari langkah pertama,

Jadi, panjang kabel minimal yang harus disiapkan oleh Pak Dengklek adalah 1 + 2 + 6 + 9 + 9 = 27 km, yaitu melalui B→A→C→F→E→D.

6. Diketahui 8 buah kota dengan label 0, 1, 2, …, 7 yang masing-masing terhubung dengan sebuah jalan. Setiap jalan bersifat satu arah.

Diketahui pula waktu tempuh dari satu kota ke kota yang lain melalui masing-masing jalan sesuai dengan nilai yang ditunjukkan pada masing-masing jalur penghubung (dalam satuan jam). Waktu tempuh antara dua buah kota didefinisikan sebagai nilai terkecil dari total waktu tempuh jalan-jalan yang harus dilewati untuk berpindah dari

satu kota ke kota lainnya. Misalnya, waktu tempuh dari 2 ke 7 adalah 3, karena kita dapat melalui jalur 2→ 3 (waktu tempuh = 2) dan jalur 3→7 (waktu tempuh = 1), sehingga total = 2 + 1 = 3, dan tidak ada jalur lain dari 2 ke 7 yang memiliki total waktu tempuh < 3. Kota manakah yang waktu tempuhnya dari 0 paling besar? A. 3 B. 4 C. 5 D. 6 E. 7 Jawab: B Hitung jarak kota sesuai pilihan jawaban. 𝟎 → 𝟑 = 1 + 3 + 1 = 5, diperoleh waktu tempuh dari 0 ke 3 adalah 5 jam. 𝟎 → 𝟒 = 𝟎 → 𝟏 → 𝟐 → 𝟔 → 𝟒 = 2 + 3 + 2 + 3 = 10, diperoleh waktu tempuh dari 0 ke 4 adalah 10 jam. 𝟎 → 𝟓 = 1, diperoleh waktu tempuh dari 0 ke 5 adalah 1 jam. 𝟎 → 𝟔 = 𝟎 → 𝟏 → 𝟐 → 𝟔 = 2 + 3 + 2 = 7, diperoleh waktu tempuh dari 0 ke 6 adalah 7 jam. 𝟎 → 𝟕 = 𝟎 → 𝟓 → 𝟕 = 1 + 3 = 4, diperoleh waktu tempuh dari 0 ke 7 adalah 4 jam. Jadi, kota 4 adalah yang waktu tempuhnya dari 0 paling besar, yaitu sebesar 10 jam.

7. Pak Dengklek sedang membuat program sederhana yang bisa menggambar sebuah bangun ruang dari masukan sebuah string yang terdiri dari huruf-huruf “T”, “U”, “B”, “S”. Setiap membaca satu karakter pada string, program akan menggambar sebuah garis dengan panjang 1 cm yang terhubung dengan garis sebelumnya yang Digambar dengan ketentuan sebagai berikut: • • • •

Jika terbaca karakter T, maka program akan menggambar garis dengan dari kiri ke kanan. Jika terbaca karakter U, maka program akan menggambar garis dengan dari bawah ke atas. Jika terbaca karakter B, maka program akan menggambar garis dengan dari kanan ke kiri. Jika terbaca karakter S, maka program akan menggambar garis dengan dari atas ke bawah.

arah arah arah arah

Berikut adalah dua contoh hasil gambar dari program yang dibuat Pak Dengklek dengan masukan sebuah string.

Jika diperhatikan meskipun masukan string berbeda, gambar yang dihasilkan bentuknya sama hanya berbeda pada rotasinya saja. Manakah diantara string berikut yang menghasilkan gambar dengan bentuk yang sama dengan string TTTSBSTTSBBBUBUU. A. TTTSTSBSBBUTUBBU B. BBBUTUBBUTTTTSSS C. TTTSTSSBBBUTUBBU D. TTTSSBUBSBUUTTTS E. SSTSBBBUTUBBUTTT Jawab: C Masukan String

TTTSBSTTSBBBUBUU

Bangun Ruang yang tergambar

A. TTTSTSBSBBUTUBBU

B. BBBUTUBBUTTTTSSS

C. TTTSTSSBBBUTUBBU

D. TTTSSBUBSBUUTTTS

E. SSTSBBBUTUBBUTTT

Tips: Kalau sudah menemukan jawaban, langsung lanjut di soal berikutnya. Tidak perlu kerjakan pilihan jawaban lainnya.

8. Tahun ini Pak Dengklek ditunjuk menjadi ketua panitia Olimpiade Internasional Bebek (OIB). Untuk memberikan pengalaman kepada bebek-bebeknya, Pak Dengklek berencana memilih 10 dari 15 bebek yang dimilikinya untuk menjadi peserta. Tentunya kita tahu bahwa di antara 15 bebek tersebut, ada empat bebek kesayangan Pak Dengklek, yaitu Kwak, Kwik, Kwek dan Kwok. Kwak dan Kwik harus dipilih untuk menjadi peserta lomba karena keduanya yang paling pintar. Sedangkan Kwek dan Kwok tidak bisa dipilih sebab saat ini sedang sakit. Ada berapa banyak cara memilih bebek-bebek sebagai peserta OIB? A. 303 B. 286

C. 196 D. 165 E. 120 Jawab: D Memilih 10 dari 15 bebek. Kwak dan Kwik harus dipilih. Sehingga cukup memilih 10-2=8 dari 15-2=13 bebek. Kemudian, Kwek dan Kwok tidak bisa dipilih. Artinya, cukup memilih 8 dari 13-2=11 bebek. 11𝐶8 =

11! = 165 8! 3!

9. Pak Dengklek akan kembali ke kotanya dari Yogyakarta setelah meninjau lokasi yang akan digunakan untuk Olimpiade Internasional Bebek (OIB). Dia membawa oleholeh dari Yogyakarta untuk ketiga bebeknya yaitu Kwak, Kwik, dan Kwek. Tapi sayangnya dia hanya mendapatkan jatah 20 kg bagasi, jika barang bawaannya melebihi dari jatah, Pak Dengklek harus membayar biaya tambahan untuk berat sisanya. Masing-masing oleh-oleh memiliki berat tertentu. Gabungan oleh-oleh untuk Kwak dan Kwik jika ditimbang memiliki berat 13 kg. Gabungan oleh-oleh untuk Kwak dan Kwek jika ditimbang memiliki berat 21 kg. Gabungan oleh-oleh untuk Kwik dan Kwek jika ditimbang memiliki berat 32 kg. Berapakah tambahan berat bagasi yang harus dibayar Pak Dengklek? A. 13 B. 33 C. 14 D. 46 E. 66 Jawab: Total bagasi Pak Denglek =

13+21+32 2

= 33 kg. Sehingga, tambahan berat bagasi yang

harus dibayar Pak Dengklek adalah 33 − 20 = 13 kg.

10. Pak Dengklek mengumpulkan sejumlah bebek, satu diantaranya adalah Kwak. Mereka diminta untuk berbaris secara memanjang ke samping. Pak Dengklek ingin mengetes kemampuan bebeknya dengan menyebutkan sebuah angka mulai dari bebek paling kiri sampai bebek paling kanan dengan urutan angka 1, 4, 7, 10, 13, …

dan saat giliran Kwak, dia menyebutkan angka 46. Proses ini diulangi mulai dari bebek paling kanan sampai bebek paling kiri dengan urutan angka 1, 6, 11, 16, … dan saat giliran Kwak, dia menyebutkan angka 46 lagi. Berapakah jumlah bebek yang ada dalam barisan? A. 23 B. 24 C. 25 D. 26 E. 27 Jawab: C Terdapat barisan dengan suku awal 1 dan beda 3 : 1, 4, 7, 10, 13, …. Kwak menyebutkan angka 46. Berarti 𝑈𝑛 = 46 → 1 + (𝑛 − 1)3 = 46. Diperoleh 𝑛 = 16. Ini artinya, Kwak berada di posisi ke-16 dari sebelah kiri barisan. Terdapat barisan dengan suku awal 1 dan beda 5 : 1, 6, 11, 16, …. Kwak kembali menyebutkan angka 46. Berarti 𝑈𝑚 = 46 → 1 + (𝑛 − 1)5 = 46. Diperoleh 𝑚 = 10. Ini artinya, Kwak berada di posisi ke-10 dari sebelah kanan barisan. Sehingga, jumlah bebek yang ada dalam barisan adalah 16 + 10 − 1 = 25.

11. Jika diketahui bahwa: (1 + 3 + 5 + ⋯ + 𝑎) + (1 + 3 + 5 + ⋯ + 𝑏) = (1 + 3 + 5 + ⋯ + 51) Berapakah nilai 𝑎 + 𝑏? A. 34 B. 66 C. 57 D. 43 E. 45 Jawab: B

Barisan bilangan ganjil: 1, 3, 5, … , 𝑈𝑛 Rumus suku ke-𝑛 adalah 𝑈𝑛 = 2𝑛 − 1 → 𝑛 =

𝑈𝑛 +1 2

Rumus penjumlahan 𝑛suku pertama adalah 𝑆𝑛 = 𝑛2 Misalkan 𝑈𝑛 = 𝑎 dan 𝑈𝑚 = 𝑏, maka 𝑛 =

𝑎+1 2

dan 𝑚 =

𝑏+1 2

.

(1 + 3 + 5 + ⋯ + 𝑎) + (1 + 3 + 5 + ⋯ + 𝑏) = (1 + 3 + 5 + ⋯ + 51) 𝑎+1 2 𝑏+1 2 ( ) +( ) = 262 2 2 Diketahui 102 + 242 = 262 . Maka diperoleh 𝑎+1 2

= 10 dan

𝑏+1 2

= 24. Nilai yang memenuhi adalah 𝑎 = 19 dan 𝑏 = 47.

Diperoleh 𝑎 + 𝑏 = 66. Begitupun sebaliknya, seandainya

𝑎+1 2

= 24 dan

𝑏+1 2

= 10. Diperoleh 𝑎 + 𝑏 = 66.

13. Perhatikan bentuk berikut!

Apabila dibuat 5 garis lurus, berapa maksimal potongan yang terbentuk? A. 6 B. 19 C. 20 D. 26 E. 32 Jawab: D. 26 Gambar tersebut adalah bentuk dari mahkota yang memiliki 3 puncak mahkota, kiri, tengah dan kanan. Perhatikan bahwa:

1 garis lurus membentuk 4 potongan 2 garis lurus membentuk 8 potongan 3 garis lurus membentuk 13 potongan 4 garis lurus membentuk 19 potongan 5 garis lurus membentuk 26 potongan Barisannya adalah 4, 8, 13, 19, 26. Bedanya selalu bertambah satu. 4 4

5 8

6 13

7 19

26

Idenya dari barisan Lazy Caterer: 2, 4, 7, 11, 16, …, yaitu maksimal potongan lingkaran menggunakan n garis lurus. Sehingga, untuk n=5 garis lurus maka banyaknya potongan dari sebuah lingkaran adalah 16. Sekarang, letakkan lingkaran tersebut di tengah dari puncak mahkota tengah. Setelah itu perhatikan ujung dari masing-masing garis. Kita bisa mendesain ujung dari 5 garis akan memotong puncak kiri dan puncak kanan dari mahkota. Misalkan ujung garis a, b, c, d, dan e yang memotong puncak mahkota kanan, sehingga diperoleh 5 potongan baru. kemudian ujung garis f, g, h, i dan j memotong puncak mahkota kiri yang juga membuat 5 potongan baru. Sehingga total diperoleh 16+5+5=26.

14. Di akhir pekan ini Pak Dengklek mendapatkan 5 email dari Koleganya yang harus dia baca satu persatu sesuai dengan aturan berikut: • •

Email Pak Adi akan dibaca paling akhir Email Pak Budi akan dibaca lebih dahulu sebelum email Pak Adi, tetapi bukan email yang pertama kali dibaca.

•

Email Pak Carli dan Pak Dudung dibacakan secara berurutan antara Email Pak Eman dan Pak Budi

Email siapakah yang pertama kali dibaca oleh Pak Dengklek? A. Pak Adi B. Pak Budi C. Pak Carli D. Pak Dudung E. Pak Eman Jawab: E

15. Perhatikan meja lingkar berikut! Bilangan pada piring menunjukkan ukuran dari piring tersebut.

Sebagai karyawan restoran, Pak Dengklek akan mengambil seluruh piring tersebut untuk dicuci. Karena alasan keselamatan kerja, Pak Dengklek harus mengambil piring dari yang ukurannya paling besar sehingga piring yang diambil harus urut dari ukuran 6 hingga 1. Setiap berpindah dari satu meja ke meja lain yang bersebelahan membutuhkan satu langkah. Pak Dengklek hanya bisa berpindah antara dua meja yang saling bersebelahan. Berapa banyak langkah minimal Pak Dengklek untuk mengambil seluruh piring tersebut? A. 18 B. 19 C. 20 D. 21 E. 22 Jawab: C

Mulai dari bagian meja piring nomor 6. ⑥→②→③→⑤ = 3 langkah. ⑤→③→⑤ = 2 langkah. ⑤→ ① →⑤ = 2 langkah. ⑤→④ = 1 langkah. ④→⑥→②→③ = 3 langkah. ③→⑤→③ = 2 langkah. ③→⑤→③→② = 3 langkah. ②→⑥→④→ ⑤ → ① = 4 langkah. Jadi, banyak langkah minimal Pak Dengklek untuk mengambil seluruh piring tersebut adalah 3 + 2 + 2 + 1 + 3 + 2 + 3 + 4 = 20 langkah.

16. Pak Dengklek akan mengadakan pesta untuk memperingati hari kemerdekaan di lingkungan RT/RW-nya. Pesta ini rencananya akan mengundang 100 orang warganya. Dalam rangka menyiapkan jamuan yang sesuai untuk para tamu, pak Dengklek telah mensurvei preferensi setiap warganya terhadap 3 jenis alternatif makanan, yaitu: kue apem, bakso atau cendol. Hasil survei menunjukkan: 20 orang suka makan apem, 30 orang suka makan bakso, dan 45 orang suka cendol, 5 orang suka apem dan bakso, 6 orang suka bakso dan cendol, 1 orang saja yang suka apem dan cendol, dan satu orang juga yang suka ketiga-tiganya. Berapakah orang yang tidak suka ketiga jenis makanan tersebut? Jawaban: ……………. {tuliskan jawaban dalam bentuk ANGKA saja} Jawab: 126 Banyaknya orang yang menyukai sedikitnya satu jenis makanan adalah 20 + 30 + 45 − 5 − 6 − 1 + 1 = 84. Sehingga, jumlah orang yang tidak suka ketiga jenis makanan tersebut adalah 100 − 84 = 126.

17. Berapakah nilai dari 20222000 × 100! (𝑚𝑜𝑑 707)? (dimana 𝑛! = 𝑛 × (𝑛 − 1) × (𝑛 − 2) … × 2 × 1, sedangkan x (mod y) berarti sisa bagi dari 𝑥 dengan 𝑦 dengan nilai antara 0 sampai 𝑦 − 1): Jawaban: ……………. {tuliskan jawaban dalam bentuk ANGKA saja}

Jawab: 504 Diketahui 707 = 7 × 101, dimana 7 dan 101 masing-masing adalah bilangan prima. Gunakan Fermat’s Little Theorem, diperoleh 2022100 ≡ 1 (𝑚𝑜𝑑 101). Sehingga 20222000 = (2022100 )20 ≡ 1 (𝑚𝑜𝑑 101). Gunakan kembali Fermat’s Little Theorem, diperoleh 20226 ≡ 1 (𝑚𝑜𝑑 7). Sehingga 20222000 = (20226 )333 × 20222 ≡ (−337)2 ≡ (−1)2 ≡ 1 (𝑚𝑜𝑑 7). Karena sisa baginya sama dan 101 dan 7 relatif prima, maka 20222000 ≡ 1 (𝑚𝑜𝑑 707). Perhatikan bahwa 100! = 1 × 2 × 3 × 4 × 5 × 6 × 7 × … × 100. Jelas, 100! habis dibagi 7. Tulis 100! = 7𝑎, untuk suatu bilangan bulat 𝑎. Sedangkan dari Wilson Theorem diperoleh 100! ≡ 100 (𝑚𝑜𝑑 101) Substitusi, diperoleh 7𝑎 ≡ 100(𝑚𝑜𝑑 101) 7𝑎 ≡ 7 × 2900 − 101 × 200 ≡ 7 × 2900 (𝑚𝑜𝑑 101) Asumsikan 𝑎 = 2900. Maka, diperoleh 𝑎 ≡ 2900 (𝑚𝑜𝑑 101) 𝑎 ≡ 72 (𝑚𝑜𝑑 101) 𝑎 = 101𝑏 + 72, untuk suatu bilangan bulat 𝑏. Akibatnya 100! = 7𝑎 = 7(101𝑏 + 72) = 707𝑏 + 504. Ini artinya 100! ≡ 504 (𝑚𝑜𝑑 707). Jadi, nilai dari 20222000 × 100! (𝑚𝑜𝑑 707) adalah 504.

18. Pak Dengklek sedang ingin berkeliling mengunjungi tempat-tempat wisata yang ada di Pulau Jawa. Ada 10 kota yang ingin dikunjungi oleh Pak Dengklek, yaitu: Jakarta, Bogor, Bandung, Purwakarta, Tasikmalaya, Cirebon, Semarang, Yogya, Solo dan Surabaya. Pak Dengklek sudah mensurvei jalur antar kota-kota tersebut dan mencatat biaya perjalanan dengan bus antara beberapa kota. Berikut adalah informasi biaya ongkos bus (satu arah) antar kota yang didapatkan pak Dengklek.

No .

Dari Kota

Ke Kota

Biaya (dalam ribuan rupiah)

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Jakarta Jakarta Bogor Jakarta Bandung Bandung Purwakarta Tasikmalaya Cirebon Cirebon Semarang Solo Semarang Solo

Bogor Bandung Bandung Purwakarta Tasikmalaya Purwakarta Cirebon Cirebon Semarang Yogya Solo Yogya Surabaya Surabaya

30 20 80 50 20 30 60 80 70 50 20 20 80 50

Setiap jalur antar kota bersifat dua arah, dengan harga yang sama. Misalnya, Pak Dengklek dapat menaiki bus dari Bogor ke Jakarta dengan harga yang sama (Rp 30 ribu rupiah). Jika Pak Dengklek harus memulai perjalanan dari Jakarta, dan dapat mengakhiri perjalanan di kota mana saja, asalkan semua kota terkunjungi, berapakah total biaya minimal yang diperlukan Pak Dengklek? Jawaban: ……………. {tuliskan jawabannya dalam ribuan rupiah (misalnya, tuliskan 250 jika jawaban Anda adalah Rp 250 ribu rupiah)} Jawab: 370 Ini adalah kasus Minimum Spanning Tree (MST). Bisa menggunakan algoritma Prim dan Kruskal. Karena soal minta dimulai dari Jakarta, maka metode yang lebih cocok digunakan adalah algoritma Prim. Langkah-langkah: 1. Pilih sembarang node sebagai node pertama pada tree yang akan dibentuk. Kemudian, ambil edge yang bersesuaian dengan node tersebut yang memiliki bobot terkecil. 2. Ambil edge dengan bobot minimum yang bersisian dengan node-node pada tree yang telah dibentuk sehingga menambah node baru pada tree. Edge yang dipilih harus tidak membentuk sirkuit. 3. Ulangi langkah 2 sebanyak 𝑛 − 2 kali. Jumlah node atau kota adalah 10, maka 𝑛 − 2 = 10 − 2 = 8 kali. Berikut adalah graf yang diperoleh dari soal:

Total ada 10 node, yaitu kota-kota. Sedangkan edge adalah jalur antar kota dimana bobotnya adalah harga atau biaya bus. Kita mulai dari langkah pertama. 1. Soal menginginkan kita memulai dari kota Jakarta. Jadi pilih node Jakarta sebagai node pertama. Kemudian pilih edge dengan bobot terendah yang bersesuaian dengan node Jakarta. Pilih: Jakarta-Bandung dengan bobot 20. 2. Kemudian pilih edge lain dengan bobot terendah yang bersesuaian dengan node Jakarta dan Bandung yang tidak membentuk sirkuit, yaitu Bandung-Tasikmalaya dengan bobot 20. 3. Lanjutkan, ambil edge lain dengan bobot terendah yang bersesuaian dengan node Jakarta, Surabaya dan Tasikmalaya yang tidak membentuk sirkuit, pilih JakartaBogor dengan bobot 30. 4. Pilih Bandung-Purwakarta dengan bobot 30. 5. Pilih Purwakarta-Cirebon dengan bobot 60. 6. Pilih Cirebon-Yogya dengan bobot 50. 7. Pilih Yogya-Solo dengan bobot 20. 8. Pilih Solo-Semarang dengan bobot 20. 9. Terakhir, pilih Solo-Surabaya dengan bobot 50.

Selanjutnya, masih ada masalah yang belum selesai yaitu harus memilih jalur dua arah atau bolak-balik seperti pada kasus Solo-Semarang atau Solo-Surabaya. Tentu, kita pilih Solo-Semarang dengan bobot 20, yang kalau bola-balik hanya 2 × 20 = 40 dibandingkan Solo-Surabaya dengan 2 × 50 = 100. Sedangkan, Jakarta-Bogor dan Bandung-Tasikmalaya harus bolak balik atau dua arah, karena tidak ada pilihan lain yang lebih baik. Jadi bisa disimpulkan, Pak Dengklek bisa mengunjungi semua kota dimulai dari Jakarta dengan biaya minimum melalui jalur: Jakarta-Bogor-Jakarta-Bandung-Tasikmalaya-Bandung-Purwakarta-CirebonYogya-Solo-Semarang-Solo-Surabaya dengan total biaya: (2 × 30) + 20 + (2 × 20) + 30 + 60 + 50 + 20 + (2 × 20) + 50 = 𝟑𝟕𝟎 ribu rupiah.

19. Pak Dengklek memiliki lahan yang berukuran 1×10 yang nantinya akan ditempatkan tiga jenis kandang dengan ukuran berbeda yaitu ukuran 1×1, 1×2 dan 1×4. Berikut adalah dua contoh penempatan kandang pada lahan Pak Dengklek:

Jika jumlah kandang tidak terbatas, ada berapa banyak cara yang bisa dilakukan oleh Pak Dengklek untuk menyusun kandang-kandang tersebut? Jawaban: ……………. {tuliskan jawaban dalam bentuk ANGKA saja} Jawab: 343 Bagi beberapa kasus: 10!

•

10 kandang 1x1, diperoleh 10! = 1 cara

•

8 kandang 1x1 dan 1 kandang 1x2, diperoleh 8! = 9 cara

•

6 kandang 1x1 dan 2 kandang 1x2, diperoleh 6!×2! = 28 cara

•

4 kandang 1x1 dan 3 kandang 1x2, diperoleh 4!×3! = 35 cara

•

2 kandang 1x1 dan 4 kandang 1x2, diperoleh 2!×4! = 15 cara

•

5 kandang 1x2, diperoleh 5! = 1 cara

•

6 kandang 1x1 dan 1 kandang 1x4 dan, diperoleh

•

4 kandang 1x1, 1 kandang 1x2 dan 1 kandang 1x4, diperoleh 4! = 30 cara

•

2 kandang 1x1, 2 kandang 1x2 dan 1 kandang 1x4, diperoleh 2!×2! = 30 cara

•

3 kandang 1x2 dan 1 kandang 1x4, diperoleh 3! = 4 cara

•

2 kandang 1x1 dan 2 kandang 1x4, diperoleh 2!×2! = 180 cara

•

1 kandang 1x2 dan 2 kandang 1x4, diperoleh 2! = 3 cara

9!

8! 7! 6!

5!

7! 6!

= 7 cara 6!

5!

4!

6!

3!

Jumlahkan semua, diperoleh banyaknya cara untuk menyusun kandang adalah 343 cara.

20. Jika diberikan sembilan buah patok pada lahan Pak Dengklek sebagai berikut:

*

*

*

*

*

*

*

*

*

Pak Dengklek ingin membuat sebuah kandang yang berbentuk segitiga dimana setiap pojok sudut kandang harus merupakan patok-patok tersebut. Sisi kandang boleh melewati atau mengandung patok-patok lainnya. Ada berapa banyak kemungkinan kandang yang bisa dibangun oleh Pak Dengklek? Jawaban: ……………. {tuliskan jawaban dalam bentuk ANGKA saja} Jawab: 76 Kasus ini sama dengan mengitung banyaknya segitiga yang bisa dibentuk dari 9 titik. Banyaknya cara adalah 9C3. Tetapi, menggunakan cara ini akan juga membentuk 8 garis sejajar yang bukan segitiga, yaitu 3 horizontal, 3 vertikal, dan 2 diagonal. Berikut ilustrasinya:

Jadi, banyaknya kandang berbentuk segitiga yang bisa dibangun dari sembilan patok adalah 9𝐶3 − 3 − 3 − 2 =

9! − 8 = 84 − 8 = 76. 3! 6!

22. Pada suatu hari terjadi percakapan antara Kwek dan Kwok menggunakan bahasa bebek: • • • • •

“Waak wik wak” kata Kwek, yang artinya “hari ini belajar online”. “Waak wik wuk kwik” kata Kwok, yang artinya “kemarin juga belajar online”. “Nwuk wik wuk” kata Kwek meralat pernyataan Kwok, yang artinya “kemarin belajar tatap muka”. Kwok kemudian bertanya “mwuk?” yang artinya “besok?” Kwek membalas dengan yakin, “Nwuk wik mwuk kwik.”

Apa arti kalimat yang diucapkan Kwek pada akhir percakapan di atas? Jawaban: ……………. {tuliskan jawaban dalam bentuk HURUF KECIL saja}

Jawab: • •

Waak wik wak = hari ini belajar online Waak wik wuk kwik = kemarin juga belajar online

Pada kedua kalimat diatas, kata-kata yang sama adalah “belajar online”. Sehingga diperoleh: • • •

Waak wik = belajar online wak = hari ini wuk kwik = kemarin juga

Kemudian, perhatikan kembali tiga kalimat berikut: • •

wuk kwik = kemarin juga Nwuk wik wuk = kemarin belajar tatap muka

Kata yang sama adalah kemarin, yaitu wuk diperoleh • • •

wuk = kemarin kwik = juga Nwuk wik = belajar tatap muka

Dari soal juga diperoleh •

mwuk = besok

Sehingga kalimat “mwuk kwik” = “besok juga”. Jadi, kalimat “Nwuk wik mwuk kwik” memiliki arti “Besok juga belajar tatap muka”.

23. Pak Dengklek memiliki ladang berukuran N×M petak dimana setiap petaknya berisi satu buah kandang yang memiliki ketinggian tertentu. Kwak sangat suka bermain di ladang tersebut untuk berjalan-jalan di atas kandang. Karena Kwak takut akan ketinggian, dia hanya bisa berpindah dari satu kandang ke kandang lain secara horizontal, vertikal, diagonal jika selisih ketinggian kandangnya maksimal satu. Sebagai contoh misalnya ladang Pak Dengklek berukuran 3×4 petak dengan ketinggian masing-masing kandang sebagai berikut:

Jika Kwak berjalan mulai dari kandang di posisi paling kiri atas dan ingin menuju kandang di posisi paling kanan bawah, maka banyak kandang minimal yang harus dilalui adalah 7, yaitu melalui kandang dengan ketinggian berturut-turut 3, 4, 5, 6, 7,

8, dan 9. Jika diketahui ukuran kandang Pak Dengklek adalah 5×6 petak dengan ketinggian masing-masing kandang adalah sebagai berikut:

Berapa jumlah kandang minimal yang bisa dilalui oleh Kwak jika dia ingin berjalan dari kandang di posisi paling kiri bawah sampai ke kandang di posisi paling kanan atas? Jawaban: ……………. {tuliskan jawaban dalam bentuk ANGKA saja} Jawab: 8 Dari soal diperoleh Kwak bisa berpindah kandang yang memiliki ketinggian sama atau selisih ketinggian satu. Sehingga jumlah kandang minimal yang bisa dilalui oleh Kwak jika dia ingin berjalan dari kandang di posisi paling kiri bawah 5 sampai ke kandang di posisi paling kanan atas 7 adalah 8, yaitu 5 − 6 − 7 − 8 − 7 − 6 − 6 − 7.

24. Pak Dengklek memiliki ladang berukuran N×M petak dimana setiap petaknya berisi satu buah kandang yang memiliki ketinggian tertentu. Kwak sangat suka bermain di ladang tersebut untuk berjalan-jalan di atas kandang. Karena Kwak takut akan ketinggian, dia hanya bisa berpindah dari satu kandang ke kandang lain secara horizontal, vertikal, diagonal jika selisih ketinggian kandangnya maksimal satu. Sebagai contoh misalnya ladang Pak Dengklek berukuran 3×4 petak dengan ketinggian masing-masing kandang sebagai berikut:

Jika Kwak berjalan mulai dari kandang di posisi paling kiri atas dan ingin menuju kandang di posisi paling kanan bawah, maka banyak kandang minimal yang harus

dilalui adalah 7, yaitu melalui kandang dengan ketinggian berturut-turut 3, 4, 5, 6, 7, 8, dan 9. Jika diketahui ukuran kandang Pak Dengklek adalah 5×6 petak dengan ketinggian masing-masing kandang adalah sebagai berikut:

Jika Kwak bisa memulai dari posisi manapun dan menuju posisi manapun, berapa banyak kandang maksimal (satu kandang hanya boleh dikunjungi satu kali) yang dapat dilalui oleh Kwak adalah? Jawaban: ……………. {tuliskan jawaban dalam bentuk ANGKA saja} Jawab: 26 Total ada 5 × 6 = 30 petak kandang dimana satu kandang hanya boleh dikunjungi satu kali. Pertama, cari kandang yang tidak memiliki ketinggian sama dan selisih ketinggian tidak sama dengan satu dengan kandang lain di samping. Diperoleh 9 dan 3.

Tersisa 30-2=28 kandang. Kedua, perhatikan hanya terdapat satu buah kandang 8. Padahal terdapat empat buah kandang 9 yang berdekatan masing-masing dua. Karena satu kandang hanya boleh dikunjungi satu kali, maka ada dua kandang 9 yang tidak bisa dilalui oleh Kwak. Sehingga, tersisa 28-2=26 kandang. Berikut ilustrasinya:

atau Jadi, banyak kandang maksimal yang dapat dilalui oleh Kwak adalah 26.

25. Pak Dengklek menyusun sekumpulan kubus yang jika dilihat dari depan, atas dan

samping kiri adalah sebagai berikut:

Berapakah banyak kubus yang disusun oleh Pak Dengklek? Jawaban: ……………. {tuliskan jawaban dalam bentuk ANGKA saja} Jawab: 10 Dari Tampak Atas terlihat kubus hanya tersusun di sisi depan dan di samping kiri. Kemudian dari Tampak Depan diperoleh 7 buah kubus di sisi depan. Sedangkan dari Tampak Samping terdapat 6 buah kubus. Tetapi 3 buah kubus vertikal sudah dihitung di sisi depan. Sehingga diperoleh 6 − 3 = 3 buah kubus lain. Jadi, banyaknya kubus yang disusun oleh Pak Dengklek adalah 7 + 3 = 10 buah kubus.

Bagian B : Algoritmika 26. Perhatikan potongan program berikut! int main(){ int A, B, C; cin >> A >> B >> C; B = A - B; C = A - C; A = B + C; cout > B >> C >> D; if (A>=B){ if (A>=C){ if (A>=D){ cout