Olimpiade Sains Provinsi (OSP) 2022 - Komputer

Pada sebuah toko buah diketahui informasi sebagai berikut:

Pak Blangkon hanya memiliki uang Rp. 25.000, dan dia ingin membeli masing-masing buah maksimal sebanyak stok yang ada. Berapa jumlah maksimal kalori yang bisa didapatkan oleh Pak Blangkon? {tuliskan jawaban dalam bentuk ANGKA saja}

Kwak, Kwik, Kwuk, Kwek, Kwok ditugasi sebagai seorang diplomat. Kwak hanya dapat berbicara bahasa Inggris dan Jerman. Kwik hanya berbicara dalam bahasa Perancis, Jepang, dan Cina. Kwuk hanya dapat berbicara bahasa Jerman. Kwek hanya berbicara dalam bahasa Inggris, Jepang, dan Cina. Kwok hanya dapat berbicara dalam bahasa Perancis dan Jerman.

Ada berapa banyak pasangan diplomat yang harus menggunakan penterjemah dalam berkomunikasi? {tuliskan jawaban dalam bentuk ANGKA saja}

Kwak menuliskan kata "INFORMATIC" pada kertas berulang kali tanpa dipisahkan spasi. Huruf apa yang ditulis oleh Kwak pada urutan ke-2²⁰²² dan ke-3²⁰²³? {tuliskan jawaban dalam bentuk DUA HURUF KAPITAL tanpa spasi}

Pak Dengklek memiliki pekarangan yang berisi 8 kandang yang diberi label A, B, C, D, E, F, G dan H sebagai berikut:

Tanda panah antara dua kandang (X, Y) menandakan bahwa terdapat jalan setapak yang bisa dilalui dari kandang X ke kandang Y namun tidak sebaliknya. Jika saat ini posisi Pak Dengklek ada di kandang A, dan ingin menuju ke kandang H. Ada berapa rute yang bisa dilalui Pak Dengklek dari kandang A ke kandang H, di mana setiap kandang dapat dikunjungi maksimal satu kali? {tuliskan jawaban dalam bentuk ANGKA saja}

Bebek-bebek Pak Dengklek akan mengikuti Olimpiade Sains Nasional Bebek. Sebelum bertanding setiap bebek harus mengikuti 8 jenis latihan, yaitu F, G, H, J, K, L, M dan N. Setiap latihan harus diambil tepat satu kali secara berurutan setiap harinya. Jadwal latihan tersebut dibatasi oleh hal-hal berikut:

• Latihan N selalu diambil di hari pertama
• Latihan F selalu diambil tepat setelah latihan G diambil
• Latihan F hanya bisa diambil jika latihan H sudah diambil
• Latihan J dan M harus dipisahkan oleh dua hari yang berurutan.

Ada berapa banyak kemungkinan urutan latihan yang bisa diambil oleh bebek-bebek Pak Dengklek? {tuliskan jawaban dalam bentuk ANGKA saja}

Pak Dengklek berencana memasang tiang untuk bebek-bebeknya bermain pada lahan berbentuk persegi panjang. Panjang dan lebar lahan tersebut belum ditentukan, namun kelilingnya harus 100 m. Pada lahan tersebut nantinya akan dikelilingi tembok. Jarak antara tiang harus sebesar minimal 2 meter. Selain itu, jarak antar tiang dengan tembok juga harus sebesar minimal 2 meter. Jika dilihat dari atas, tiang akan seperti titik pada koordinat dua dimensi. Berapa banyak tiang maksimal yang bisa dibuat oleh Pak Dengklek pada lahan tersebut? {tuliskan jawaban dalam bentuk ANGKA saja}

Pak Dengklek akan membentuk sebuah tim yang akan bertanding pada Olimpiade Olahraga Bebek pada cabang Bola Voli. Tim yang dibentuk harus terdiri dari 3 ekor bebek jantan dan 3 ekor bebek betina, yang dipilih dari 6 ekor bebek jantan dengan berat berbeda dan 6 ekor bebek betina dengan berat yang berbeda juga. Dari pengalaman sebelumnya diketahui bahwa semakin berat seekor bebek, maka semakin kuat dalam bertanding. Oleh sebab itu dalam tim yang dibentuk tersebut, Pak Dengklek ingin memastikan bahwa tim hanya boleh mencakup paling banyak satu anggota dengan berat badan paling ringan dari kedua jenis kelamin bebek. Dengan kata lain, bebek jantan paling ringan dan bebek betina paling ringan tidak boleh dipilih sekaligus. Berapa banyak cara untuk menyusun tim tersebut? {tuliskan jawaban dalam bentuk ANGKA saja}

Pak Dengklek ditunjuk menjadi ketua panitia Konser Musik Bebek. Konser akan dilaksanakan pada sebuah gedung pertunjukan berbentuk sektor lingkaran yang terdiri dari 6 baris kursi penonton. Pada baris pertama (baris paling depan) terdiri dari 25 kursi penonton, baris kedua terdiri dari 35 kursi penonton, baris ketiga terdiri dari 50 kursi penonton, baris keempat terdiri dari 70 kursi penonton, baris kelima terdiri 95 kursi penonton, dan baris keenam terdiri dari 125 kursi penonton. Diketahui bahwa harga tiket pada kursi baris paling depan adalah paling mahal dan selisih harga tiket antara dua baris yang berdekatan adalah Rp. 10.000. Jika diasumsikan semua kursi penonton penuh dan Pak Dengklek menginginkan agar diperoleh pemasukan Rp. 22.500.000, berapakah harga tiket pada baris ketiga? {tuliskan jawaban dalam bentuk ANGKA saja, sebagai contoh jika jawaban anda adalah Rp. 30.000 maka cukup tulis jawaban 30000}

Kwok sangat menyukai permen dan menyimpan permennya di dalam kotak yang dia miliki. Diketahui bahwa setiap tiga hari sekali, dia pasti akan memakan sebanyak 3 permen atau sebanyak sisa permen yang ada jika jumlahnya kurang dari 3. Setiap satu minggu sekali Pak Dengklek akan membelikan Kwok sebanyak 5 permen baru. Pak Dengklek membelikan permen di pagi hari, dan Kwok selalu makan permen di malam hari sebelum tidur. Jika pada hari ke-1 jumlah permen Kwok ada sebanyak 100 buah, Kwok pertama kali makan permen pada hari ke-3 dan Pak Dengklek pertama kali membelikan permen untuk Kwok pada hari ke-7, pada hari ke berapa paling cepat permen Kwok akan habis? {tuliskan jawaban dalam bentuk ANGKA saja}

Kwak, Kwik, Kwuk, Kwek dan Kwok masing-masing tinggal di satu kandang berbeda. Kandang Kwuk ada di sebelah utara kandang Kwak. Kandang Kwik bersebelahan dengan kandang Kwak. Kandang kwok terletak paling selatan. Kandang Kwek ada di sebelah tenggara kandang Kwuk. Kandang siapa yang berada di tengah-tengah? {tuliskan jawaban dalam huruf kecil semua}

Jika diketahui P = 4, Q = 10, dan R = 12, apakah ketiga lampu akan menyala bersamaan pada detik ke 3000?

Jawaban: ............... {tuliskan jawaban dalam bentuk YA/TIDAK}

Jika diketahui P = 1, Q = 2, dan R = 3, kapankah waktu terdekat berikutnya dimana ketiga lampu akan menyala lagi secara bersamaan?

Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}

Jika diketahui P = 4, Q = 6, dan R = 9, kapankah waktu terdekat berikutnya dimana ketiga lampu akan menyala lagi secara bersamaan?

Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}

LAMPU HIAS

Buatlah program menggunakan bahasa C/C++ sesuai deskripsi cerita di atas untuk menentukan minimal pengantaran dengan ketentuan sebagai berikut:

Format Masukan:
Baris pertama berisi sebuah tiga buah bilangan P, Q, R. Baris berikutnya berisi sebuah bilangan bulat positif N, menyatakan banyaknya pertanyaan Pak Dengklek. N buah baris berikutnya berisi masing-masing sebuah bilangan bulat positif T, menyatakan waktu dalam detik setelah ketiga lampu dinyalakan.

Format Keluaran:
N buah baris yang masing-masing berisi string berisi teks YA atau TIDAK (dalam huruf besar) yang menyatakan apakah pada waktu T tersebut, ketiga lampu menyala bersamaan atau tidak.

Contoh Masukan dan Keluaran:

4 6 9
4
10
36
90
100

TIDAK
YA
TIDAK
TIDAK

Penjelasan Contoh:
Pada kasus ini, lampu pertama akan menyala setiap 4 detik, lampu kedua setiap 6 detik, dan lampu ketiga setiap 9 detik. Pada awalnya (T=0) semua lampu menyala bersamaan. Pada detik ke-36, ketiga lampu akan menyala lagi secara bersamaan. Namun pada detik ke-10, ke-90 dan ke-100, ketiga lampu tidak semuanya menyala secara bersamaan.

Batasan:

Untuk semua kasus uji berlaku:

• 1 ≤ P, Q, R ≤ 10⁹
• 1 ≤ N ≤ 100 000
• 1 ≤ T ≤ 10¹⁸

Untuk 50% kasus uji berlaku:

• 1 ≤ N ≤ 100
• 1 ≤ P, Q, R ≤ 1000
• 1 ≤ T ≤ 10⁹

Jika Pak Dengklek akan mengangkut bebek-bebek dengan bobot B₁ = 2, B₂ = 2, dan B₃ = 3 pada kandang dengan biaya angkut C₁ = 5 rupiah per kg dan kapasitas P₁ = 4, berapakah biaya pengangkutan yang harus dikeluarkan Pak Dengklek untuk satu kandang tersebut?

Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}

Jika ada tiga kandang (K = 3) dengan kapasitas yang sama (P₁ = P₂ = P₃ = 3) sedangkan biaya angkut dari masing-masing kandang adalah C₁ = 5, C₂ = 2 dan C₃ = 3, sedangkan bebek Pak Dengklek ada 7 ekor (N = 7) dengan bobot yang kebetulan sama semua (B₁ = … = B₇ = 5), maka berapakah biaya terkecil yang perlu dibayarkan oleh Pak Dengklek untuk mengangkut semua bebek-bebeknya?

Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}

Diketahui ada 3 buah kandang (K = 3) dengan kapasitas P₁ = 6, P₂ = 3, dan P₃ = 4, dengan biaya angkut per kg berat bebek dari masing-masing kandang adalah C₁ = 2, C₂ = 1 dan C₃ = 3 rupiah per kg. Jika diketahui bahwa Pak Dengklek memiliki 9 ekor bebek (N = 9) dengan berat masing masing (B₁, …, B₉) adalah 3, 2, 2, 4, 5, 3, 6, 8, dan 7, maka berapakah biaya angkut terkecil yang diperlukan oleh Pak Dengklek?

Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}

MENGANGKUT BEBEK

Buatlah program menggunakan bahasa C/C++ untuk membantu menjawab pertanyaan Pak Dengklek di atas.

Format Masukan:
Baris pertama berisi sebuah bilangan K, menyatakan banyaknya bilangan. 2 baris berikutnya berisi masing-masing K buah bilangan bulat positif, menyatakan nilai kapasitas setiap kandang (P₁, …, P_K) serta biaya angkut untuk setiap kandang dalam satuan rupiah per kg berat bebek (C₁, …, C_K).

Kemudian baris ketiga berisi sebuah bilangan bulat N, menyatakan banyaknya bebek Pak Dengklek. Baris keempat berisi N buah bilangan bulat positif, menyatakan berat bebek-bebek Pak Dengklek dalam satuan kilogram.

Format Keluaran:
Keluaran terdiri atas satu baris berisi sebuah bilangan bulat positif, menyatakan total biaya terkecil yang diperlukan oleh Pak Dengklek untuk mengangkut semua bebek-bebeknya menggunakan satu atau lebih kandang-kandang yang ada.

Contoh Masukan dan Keluaran:

2
3 4
5 2
6
4 1 5 2 3 2

43

Penjelasan Contoh:
Pak Dengklek dapat memasukkan bebek ke-2 dan 4 (dengan bobot 1 kg dan 2 kg) ke dalam kandang pertama (dengan kapasitas 3 dan biaya per kg = 5) sehingga biaya yang dibutuhkan untuk kandang pertama adalah (1 + 2) x 5 = 15. Kemudian Pak Dengklek memasukkan bebek sisanya (yaitu bebek ke-1, 3, 5, dan 6 (dengan bobot 4, 5, 3 dan 2 kg) ke kandang kedua (dengan kapasitas 4 dan biaya angkut 2 per kg) sehingga kandang kedua memerlukan biaya (4 + 5 + 3 + 2) x 2 = 28. Biaya total kedua kandang berarti adalah 15 + 28 = 43. Tidak ada cara pengangkutan bebek yang lain ke dalam kandang-kandang tersebut yang menyebabkan biaya angkut menjadi lebih kecil dari 43. Oleh karena itu, jawaban yang diinginkan adalah 43.

Batasan:

Untuk semua kasus uji berlaku:

• 1 ≤ K ≤ 1000
• 1 ≤ N ≤ 100 000
• Untuk setiap B_i berlaku 0 < B_i ≤ 10⁶
• Untuk setiap P_i berlaku 0 < P_i ≤ 100 000
• Untuk setiap C_i berlaku 0 ≤ C_i ≤ 10⁶

Untuk 50% kasus uji berlaku:

• B₁ = B₂ = … = B_N (semua bebek memiliki berat yang sama).

Diberikan tingkat ego bebek E = [1, 7, 4, 8, 10].

Apabila kandidat yang dipilih adalah bebek 2, 3, dan 4, berapa tingkat perpecahan yang terbentuk?

Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}

Diberikan tingkat ego bebek E = [1, 7, 4, 8, 10].

Apabila ingin membentuk dewan perwakilan bebek yang terdiri dari 3 bebek, berapa tingkat perpecahan minimal yang dapat dicapai?

Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}

Diberikan tingkat ego bebek E = [1, 7, 4, 8, 10].

Dengan P = 7, berapa banyak anggota dewan perwakilan bebek maksimal yang dapat dibentuk?

Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}

DEWAN PERWAKILAN BEBEK

Buatlah program menggunakan bahasa C/C++ untuk menghitung banyak anggota dewan perwakilan bebek maksimal dengan ketentuan sebagai berikut:

Format Masukan:
Baris pertama berisi dua buah bilangan N, P, dan Q. Baris kedua berisi N buah bilangan E_i yang menyatakan tingkat ego dari masing-masing bebek.
Q baris berikutnya berisi bilangan X.

Format Keluaran:
Q buah baris berisi jawaban dari pertanyaan Pak Dengklek.

Contoh Masukan dan Keluaran:

6 5 2
1 6 8 3 10 2
2
5

4
3

Penjelasan Contoh:
Pada pertanyaan pertama, Pak Dengklek memilih bebek 1, 2, 4, dan 6. Pada pertanyaan kedua, Pak Dengklek memilih bebek 2, 3, dan 5.

Batasan:

Untuk kasus uji berlaku:

• 1 ≤ Q ≤ N ≤ 100 000
• 0 ≤ P, E_i ≤ 10⁹
• 1 ≤ X ≤ N

Untuk 50% kasus uji berlaku:

• Q = 1

Jika N = 2, M = 5 dan hanya boleh menggunakan karpet jenis 1, berapa banyak cara menutup jembatan?

Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}

Jika N = 1, M = 5, berapa banyak cara menutup jembatan?

Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}

Jika N = 2, M = 3, berapa banyak cara menutup jembatan?

Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}

MEMASANG KARPET

Buatlah program menggunakan bahasa C/C++ untuk menentukan nomor kartu pertama Pak Dengklek dengan ketentuan sebagai berikut:

Format Masukan:
Sebuah baris berisi dua buah bilangan N dan M yang menyatakan lebar dan panjang jembatan.

Format Keluaran:
Sebuah baris berisi sebuah bilangan yang menyatakan banyak cara memasang karpet dalam modulo 1 000 000 007.

Contoh Masukan dan Keluaran:

2 4

8568

1 2

6

Penjelasan Contoh:
Pada contoh kedua, jika Pak Dengklek tidak menggunakan karpet jenis 2 maka terdapat 4 cara. Jika Pak Dengklek menggunakan karpet jenis 2 maka terdapat 2 cara. Dengan demikian, totalnya terdapat 6 cara.

Batasan:

Untuk kasus uji berlaku:

• 1 ≤ N ≤ 2
• 1 ≤ M ≤ 100 000

Untuk 50% kasus uji berlaku:

• N = 1

Diketahui petak berukuran 3 x 4 dengan isi sebagai berikut:

Dapatkah Pak Dengklek bergerak dari petak (2, 4) ke petak (1, 2)?

Jawaban: ............... {tuliskan jawaban dalam bentuk YA/TIDAK}

Diketahui petak berukuran 3 x 4 dengan isi sebagai berikut:

Dapatkah Pak Dengklek bergerak dari petak (1, 2) ke petak (3, 4)?

Jawaban: ............... {tuliskan jawaban dalam bentuk YA/TIDAK}

Diketahui petak berukuran 3 x 4 dengan isi sebagai berikut:

Ada berapa banyak cara bagi Pak Dengklek untuk bergerak dari (1,1) ke (3, 4)?

Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}

MELOMPATI LAPANGAN

Buatlah sebuah program dalam Bahasa C/C++ untuk menjawab pertanyaan Pak Dengklek sesuai dengan deskripsi pada cerita di atas!

Format Masukan:
Baris pertama berisi dua buah bilangan N dan M yang menyatakan ukuran petak yang dimiliki pak Dengklek (N = banyaknya baris, M = banyaknya kolom). N buah baris berikutnya masing-masing berisi M buah bilangan bulat non-negatif yang masing-masing terpisahkan dengan sebuah spasi. Setiap bilangan pada baris ke-i dan kolom ke-j menyatakan nilai A[i][j] (untuk semua 1 ≤ i ≤ N, 1 ≤ j ≤ M).

Format Keluaran:
Sebuah baris yang berisi sebuah bilangan K yang menyatakan banyaknya cara Pak Dengklek bergerak dari petak (1,1) ke petak (N, M) sesuai dengan aturan di atas, modulo 1 000 000 007.

Contoh Masukan dan Keluaran:

2 3
2 0 1
1 1 3

4

Penjelasan Contoh:
Ada 4 urutan lompatan berbeda untuk bergerak dari (1, 1) ke (2, 3) pada contoh petak di atas, yaitu:

• (1, 1) → (1, 3) → (2, 3)
• (1, 1) → (2, 1) → (2, 2) → (2, 3)
• (1, 1) → (2, 2) → (2, 3)
• (1, 1) → (2, 3)

Batasan:

Untuk semua kasus uji berlaku:

• 1 ≤ N, M ≤ 2000
• 0 ≤ A[i][j] ≤ 2000

Untuk 50% kasus uji berlaku:

• 1 ≤ N, M ≤ 100