# Draft Simulasi KSN-K Informatika 2022
## By Kokocoder Coach
### Bagian 1 - Pilihan Ganda
#### (15 soal analitika/logika/matematika)
### Deskripsi Soal 1 - 2
Pak Bonceng memiliki daya sebesar $X$. Ia ingin membagi daya tersebut ke beberapa baterai kecil (pembagian tidak harus sama besar). Kualitas suatu baterai dihitung berdasarkan banyaknya perangkat milik Pak Bonceng yang kompatibel dengan baterai tersebut. Suatu perangkat dikatakan kompatibel dengan suatu baterai apabila daya yang dibutuhkan dapat habis membagi daya yang dimiliki baterai tersebut.
Diketahui bahwa Pak Bonceng memiliki perangkat yang membutuhkan daya 1 hingga $X$ masing-masing satu buah. Carilah hasil jumlah dari seluruh kualitas baterai yang minimum setelah pembagian daya!
### Soal 1
#### Problemsetter : Faishol
**Deskripsi**
Jika $X=4$, maka hasil jumlah dari seluruh kualitas baterai yang minimum setelah pembagian daya adalah...
a. 0
b. 1
c. 2
d. 3
e. 4
**Jawaban**
3
**Pembahasan**
Perhatikan bahwa:
- Kualitas baterai berdaya 1 adalah 1. Hanya kompatibel dengan 1.
- Kualitas baterai berdaya 2 adalah 2. Kompatibel dengan 1 dan 2.
- Kualitas baterai berdaya 3 adalah 2. Kompatibel dengan 1 dan 3.
- Kualitas baterai berdaya 4 adalah 3. Kompatibel dengan 1, 2, dan 4.
Jika dibagi menjadi 4 baterai, masing-masing dayanya adalah 1, sehingga jumlah kualitasnya adalah $1 \times 4=4$.
Jika dibagi menjadi 3 baterai, akan didapatkan dua baterai berdaya 1 dan sebuah baterai berdaya 2. Maka hasil jumlah kualitasnya adalah $1 \times 2 + 2 = 4$.
Jika dibagi menjadi 2 baterai, akan ada dua kasus. Kasus pertama, sebuah baterai berdaya 1 dan 3, sehingga hasil jumlah seluruh kualitasnya adalah $1+2=3$. Kasus kedua, dua baterai berdaya 2, sehingga hasil jumlah seluruh kualitas baterai adalah $2\times 2=4$.
Jika dibagi ke satu baterai, maka hasil jumlah seluruh kualitas baterai adalah $3$.
Maka hasil jumlah seluruh kualitas baterai yang minimum adalah $3$.
---
### Soal 2
#### Problemsetter : Faishol
**Deskripsi**
Jika $X=1540$, maka hasil jumlah dari seluruh kualitas baterai yang minimum setelah pembagian daya adalah...
a. 2
b. 4
c. 6
d. 8
e. 10
**Jawaban**
4
**Pembahasan**
Kualitas baterai terendah adalah 1 yang dimiliki oleh baterai dengan daya 1. Namun ini tidak optimal karena kita akan memiliki $X$ baterai, sehingga hasil jumlah seluruh kualitas baterai sama dengan $X$.
Untuk $X > 5$, akan didapatkan hasil optimal apabila membagi daya yang dimiliki ke beberapa baterai dengan besaran suatu bilangan prima. Hal ini dikarenakan kualitas baterai berdaya prima adalah 2. Selain itu, jelas bahwa semakin sedikit baterai yang diisi, maka semakin rendah pula hasil jumlah seluruh kualitas baterai.
Berdasarkan Goldbach Conjecture, kita dapatkan bahwa banyak baterai yang perlu diisi hanyalah 2 buah saja. Sehingga hasil jumlah dari seluruh kualitas baterai adalah $2 \times 2 = 4$.
---
### Soal 3
#### Problemsetter : Valerian
**Deskripsi**
Hasil dari $(1^{101}+2^{101}+3^{101}+...+101^{101}) \bmod 101$ adalah ...
**Jawaban**
0
**Pembahasan**
Dengan teorema <b>Fermat's Little Theorem</b>, kita tahu bahwa $a^{p-1}\equiv 1\pmod p$ dengan $p$ bilangan prima. Maka soalnya dapat diganti menjadi $1+2+3+...+100+0\bmod101$. Dengan menjumlahkan $1$ dengan $100$, $2$ dengan $99$, $3$ dengan $98$, ..., $50$ dengan $51$, dapat dihitung secara cepat bahwa hasil akhirnya adalah $0$.
---
### Soal 4
#### Problemsetter : Faishol
**Deskripsi**
Tiga pasang suami istri ingin berfoto bersama dalam posisi berjajar. Banyaknya susunan sehingga **tidak ada** satupun pasangan suami istri yang bersebelahan adalah...
a. 60
b. 120
c. 144
d. 240
e. 480
**Jawaban**
240
**Pembahasan**
Banyak susunan agar seluruh pasangan bersebelahan adalah $3! \cdot 2^3 = 48$.
Untuk setiap dua pasangan, banyak cara agar hanya kedua pasangan tersebut yang bersebelahan adalah ${P}^{3}_{2} \cdot {P}^{2}_{2} \cdot 2^2 = 48$. Maka banyaknya susunan agar hanya terdapat dua pasangan yang bersebelahan adalah $C^{3}_{2} \cdot 48 = 144$.
Untuk sebuah pasangan, banyak susunan agar hanya mereka yang bersebelahan adalah
$$\begin{align}\text{Banyak cara} &= 5! \cdot 2 -(\text{pasangan bersebelahan} \ge 2 \text{ dan melibatkan pasangan tersebut}) \\
&= 5! \cdot 2 - (C^{2}_{1} \cdot 48 + 48) \\
&= 240 - 144\end{align}$$
Maka banyak susunan agar terdapat tepat sebuah pasangan yang bersebelahan adalah $3 \cdot 144 = 288$.
Total susunan yang tidak valid adalah $288 + 144 + 48 = 480$, sehingga banyak susunan yang valid adalah $6! - \text{invalid} = 6! - 480 = 240$.
---
### Soal 5
#### Problemsetter : Faishol
**Deskripsi**
Loko dan Loki sedang bermain game. Di setiap babak, seorang pemenang mendapatkan satu poin. Loki yang tidak suka kekalahan akan segera menghentikan permainan apabila poinnya lebih tinggi dari Loko. Berapa banyak kemungkinan bahwa Loki menghentikan permainan diakhir babak ke-11?
a. 14
b. 42
c. 102
d. 156
e. 252
**Jawaban**
42
**Pembahasan**
Jika setiap kemenangan Loko di suatu babak dinotasikan sebagai kurung buka atau '(', sedangkan setiap kemenangan Loki dinotasikan sebagai kurung tutup atau ')', maka persoalan berubah menjadi peluang tersusunnya _parentheses_ valid dengan panjang 10.
$$\begin{align}
\text{Banyak cara} = Cat_{\frac{10}{2}} &= Cat_5 \\
&= \frac{1}{5 + 1}\binom{2 \cdot 5}{5} \\
&= \frac{10!}{6 \cdot 5! \cdot 5!} \\
&= 42 \end{align}$$
---
### Soal 6
#### Problemsetter : Arnold
Inspirasi : https://codeforces.com/contest/1462/problem/E2
**Deskripsi** (reword faishol)
Terdapat sebuah kumpulan bilangan $S$ berisi $\{4, 9, 8, 8, 3, 12, 5, 7, 10, 9, 11, 4, 3, 3\}$. Anda diminta untuk memilih **tepat** $4$ buah bilangan dari $S$ sedemikian sehingga selisih minimum dan maksimum dari bilangan yang Anda pilih $\leq 4$. Banyak cara pemilihan yang valid adalah...
a. 73
b. 85
c. 93
d. 105
e. 113
**Jawaban**
113
**Pembahasan**
Kita dapat mengurutkan nilai pada $S$ terlebih dahulu dan mencari suatu range valid. Suatu range $[L, R]$ disebut range valid jika $|T[R] - T[L]| ≤ 4$
Jika kita memilih $L$ sebagai elemen dari dalam subset, maka untuk semua elemen dari $[L+1 .. R]$ juga dapat menjadi elemen dari subset kita. Sehingga untuk setiap $L$ yang mungkin, terdapat $C(R-L, \space 3)$ kemungkinan
Setelah kita mengurutkan $S$ maka diperoleh :
$\{3, 3, 3, 4, 4, 5, 7, 8, 8, 9, 9, 10, 11, 12\}$
Maka kita hitung jangkauan untuk setiap $L$ :
$\{[3, 3, 3, 4, 4, 5, 7], 8, 8, 9, 9, 10, 11, 12\}$
Pada jangkauan ini $L = 1$ dan terdapat $C(6, 3) = 20$ kemungkinan
$\{3, [3, 3, 4, 4, 5, 7], 8, 8, 9, 9, 10, 11, 12\}$
Pada jangkauan ini $L = 2$ dan terdapat $C(5, 3) = 10$ kemungkinan
$\{3, 3, [3, 4, 4, 5, 7], 8, 8, 9, 9, 10, 11, 12\}$
Pada jangkauan ini $L = 3$ dan terdapat $C(4, 3) = 4$ kemungkinan
$\{3, 3, 3, [4, 4, 5, 7, 8, 8], 9, 9, 10, 11, 12\}$
Pada jangkauan ini $L = 4$ dan terdapat $C(5, 3) = 10$ kemungkinan
$\{3, 3, 3, 4, [4, 5, 7, 8, 8], 9, 9, 10, 11, 12\}$
Pada jangkauan ini $L = 5$ dan terdapat $C(4, 3) = 4$ kemungkinan
$\{3, 3, 3, 4, 4, [5, 7, 8, 8, 9, 9], 10, 11, 12\}$
Pada jangkauan ini $L = 6$ dan terdapat $C(5, 3) = 10$ kemungkinan
$\{3, 3, 3, 4, 4, 5, [7, 8, 8, 9, 9, 10, 11], 12\}$
Pada jangkauan ini $L = 7$ dan terdapat $C(6, 3) = 20$ kemungkinan
$\{3, 3, 3, 4, 4, 5, 7, [8, 8, 9, 9, 10, 11, 12]\}$
Pada jangkauan ini $L = 8$ dan terdapat $C(6, 3) = 20$ kemungkinan
$\{3, 3, 3, 4, 4, 5, 7, 8, [8, 9, 9, 10, 11, 12]\}$
Pada jangkauan ini $L = 9$ dan terdapat $C(5, 3) = 10$ kemungkinan
$\{3, 3, 3, 4, 4, 5, 7, 8, 8, [9, 9, 10, 11, 12]\}$
Pada jangkauan ini $L = 9$ dan terdapat $C(4, 3) = 4$ kemungkinan
$\{3, 3, 3, 4, 4, 5, 7, 8, 8, 9, [9, 10, 11, 12]\}$
Pada jangkauan ini $L = 9$ dan terdapat $C(3, 3) = 1$ kemungkinan
Sehingga total semua kemungkinan adalah :
$20 + 10 + 4 + 10 + 4 + 10 + 20 + 20 + 10 + 4 + 1 = 113$
---
### Soal 7
#### Problemsetter : Valerian
**Deskripsi** (reword by @fonmagnus)
Vian didiagnosa dengan adiksi permen.
Diketahui terdapat 2 jenis permen : Permen $A$, dan $B$.
Permen $A$ memiliki 3 varian rasa yaitu : $A_1$, $A_2$, dan $A_3$
Sedangkan permen $B$ memiliki 2 varian rasa yaitu : $B_1$ dan $B_2$
Dokter melarang Vian untuk mengonsumsi permen jenis $A$ (apapun varian rasanya) dalam 2 hari berurutan. Sebagai contoh, konsumsi permen rasa $A_1$ lalu $B_1$ atau $B_1$ lalu $B_2$ diperbolehkan, namun tidak dengan konsumsi rasa $A_3$ lalu $A_2$ atau $A_1$ lalu $A_1$.
Jika Vian ingin mengonsumsi permen-permen tersebut selama 4 hari, ada berapa banyak kombinasi urutan cara memakan permen yang mungkin dibentuk?
a. 150
b. 173
c. 184
d. 220
e. 350
**Deskripsi**
~~Vian, seorang murid SD suatu sekolah anonim terkena suatu musibah. Dia didiagnosa dengan adiksi permen karena dia tidak semangat hidup jika dia tidak membeli permen setiap hari. Ternyata salah satu jenis permen yang dibeli Vian, yaitu jenis Kupiku, merupakan penyebab adiksinya. Kupiku sendiri meliputi 3 produk permen, yakni Alpineapple, Emenems, dan YupYupHore. Jenis lain yang dibeli Vian adalah Tosmen, yang meliputi 2 produk permen, PitPat dan Stickers. Dikarenakan adiksinya, dokter melarang Vian untuk membeli permen jenis Kupiku 2 hari berturut-turut. Maka berapa banyak kemungkinan kombinasi membeli permen setiap hari selama 4 hari?~~
**Jawaban**
220
**Pembahasan**
Mari definisikan suatu fungsi $func(n, t)$ = total kombinasi pembelian permen selama $n$ hari dengan jenis $t$ sebagai permen yang akan dibeli. Pada soal ini hanya terdapat 2 jenis permen, maka anggap $t=0$ sebagai jenis $A$, dan $t=1$ sebagai jenis $B$. Karena Vian tidak boleh membeli permen jenis $A$ 2 hari berturut-turut, maka jika Vian membeli jenis $A$ di hari ke-i, maka pada hari ke-(i+1), Vian hanya boleh membeli 2 permen jenis $B$. Jika Vian membeli jenis $B$ di hari ke-i, maka pada hari ke-(i+1), Vian dapat membeli semua produk permen.
Maka didapatkan rumus DP sebagai berikut :
$func(n, 0)$ = $3 * func(n-1, 1)$
$func(n, 1)$ = $2 * (func(n-1, 0) + func(n-1, 1))$
Sehingga pada hari ke-$n$, terdapat $func(n,0)+func(n,1)$ kombinasi pembelian permen.
Hari ke-1 (Base case) :
$func(1, 0) = 3$
$func(1, 1) = 2$
Hari ke-2 :
$func(2, 0) = 3 * func(1, 1) = 3 * 2 = 6$
$func(2, 1) = 2 * (func(1, 0) + func(1, 1)) = 2 * 5 = 10$
Hari ke-3 :
$func(3, 0) = 3 * func(2, 1) = 3 * 10 = 30$
$func(3, 1) = 2 * (func(2, 0) + func(2, 1)) = 2 * 16 = 32$
Hari ke-4 :
$func(4, 0) = 3 * func(3, 1) = 3 * 32 = 96$
$func(4, 1) = 2 * (func(3, 0) + func(3, 1)) = 2 * 62 = 124$
Maka total kombinasinya $func(4,0)+func(4,1)= 220$.
---
### Soal 8
#### Problemsetter : Arnold
Inspirasi : https://codeforces.com/problemset/problem/766/D
**Deskripsi**
Diketahui fakta fakta sebagai berikut :
- Anto berteman dengan Budi
- Coki bermusuhan dengan Della
- Della berteman dengan Anto
- Erik berteman dengan Coki
- Felicia bermusuhan dengan Anto
Jika berlaku : *teman dari temanku adalah temanku* dan *musuh dari musuhku adalah temanku*
Pernyataan manakah dibawah ini yang benar?
A. Anto dan Erik berteman
B. Budi memiliki 3 orang teman
C. Coki adalah teman dari Budi
D. Felicia memiliki 2 orang teman
E. Semua pernyataan diatas salah
**Jawaban**
D
**Pembahasan**
Diketahui Anto, Budi, dan Della berteman. Sedangkan Coki, Erik, dan Felicia berteman. Dari pernyataan yang diberikan, satu satunya pernyataan yang benar hanyalah pernyataan D
---
### Soal 9
#### Problemsetter : Abdul Rafi
**Deskripsi**
Pada hari yang indah ini pak Bonceng akan bermain dengan bilangan yang dia miliki. Pak Bonceng memiliki 15 bilangan yang merupakan bilangan dari $1$ sampai $15$. Pak Bonceng akan membuat subset yang berisi $5$ bilangan dari $15$ bilangan tersebut. berapakah banyak subset berbeda yang dapat dibuat pak Bonceng jika, subset yang ingin dibuat setidaknya harus memiliki $1$ pasangan bilangan yang berurutan ?
A.2541
B.792
C.1001
D.1632
E.3003
**Jawaban**
$2541$
**Pembahasan**
misalkan A adalah kumpulan subset yang berisi 5 bilangan. B adalah kumpulan subset yang berisi 5 bilangan dan tidak memiliki bilangan yang berurutan
Maka banyak element dari A = $\dbinom{15}{5}$
asumsikan $1 \le a_1 < a_2 < a_3 < a_4 < a_5 \le 15$. jika $a$ tidak memiliki bilangan yang berurutan maka $b_1=a_1$, $b_2=a_2-1$, $b_3=a_3-2$, $b_4=a_4-3$, $b_5=a_5-4$ merupakan bilangan unik dari 1 sampai 11.
Maka banyak element dari B = $\dbinom{11}{5}$
Maka jawaban dari soal ini adalah $\dbinom{15}{5}$ $-$ $\dbinom{11}{5}$ = $2541$
---
### Soal 10
#### Problemsetter : Faishol
**Deskripsi**
Pak Bonceng dan 99 muridnya pergi ke bioskop yang terdiri dari 100 kursi. Setiap murid masuk ke bioskop satu-persatu, sedangkan Pak Bonceng masuk terakhir. Diketahui salah satu muridnya nakal dan memilih tempat duduk yang ia mau. Murid lainnnya akan menduduki tempat duduk sesuai tiket mereka, kecuali jika sudah terisi, maka mereka akan memilih tempat duduk lain yang masih kosong. Probabilitas Pak Bonceng duduk di kursi yang sesuai tiket adalah...
a. $\frac{1}{2}$
b. $\frac{1}{8}$
c. $\frac{1}{50}$
d. $\frac{1}{99}$
e. $\frac{1}{100}$
**Jawaban**
$\frac{1}{2}$
**Pembahasan**
Orang terakhir hanya mungkin duduk di kursinya atau di kursi siswa yang nakal. Maka probabilitas Pak Bonceng duduk di kursi yang sesuai adalah $\frac{1}{2}$
---
### Deskripsi Soal 11 - 12
#### Problemsetter : Arnold
Inspiration : Codegoda Coding Competition 2021 by Agoda - Problem F
Pak Dengklek dan Pak Ganesh sedang bermain permainan bernama *fruit hunting*. Awalnya terdapat sejumlah pohon yang tersusun menjadi satu garis lurus. Terdapat 2 jenis pohon : Pohon apel dan pohon jeruk.
Pemain akan berjalan secara bergantian. **Pak Dengklek mendapatkan giliran pertama**, kemudian permainan berjalan seperti berikut :
- Pilih pohon terkiri **atau** pohon terkanan (tidak boleh keduanya) yang buahnya belum dipetik. Kemudian **ambil semua buah** pada pohon tersebut
Skor akhir dari pemain adalah banyak buah yang berhasil dikumpulkan di akhir permainan (yaitu setelah semua buah pada semua pohon telah dipetik)
Tujuan kedua pemain adalah memperoleh skor akhir setinggi-tingginya. Kedua pemain selalu bermain dengan strategi optimal.
Kamu akan diberikan susunan yang terdiri dari sejumlah pohon. Pohon yang diwarnai merah adalah pohon apel dan pohon jeruk diwarnai jingga. Angka yang tertera di bagian bawah pohon adalah banyak buah pada pohon tersebut.
### Soal 11
#### Problemsetter : Arnold
**Deskripsi**
Apabila susunan pohon adalah sebagai berikut :
Berapakah total buah maksimal yang bisa diperoleh Pak Dengklek?
a. 8
b. 3
c. 4
d. 7
e. 6
**Jawaban**
6
**Pembahasan**
Anggap pohon pohon dinomori dari 1 s.d. 4 dari kiri ke kanan, maka alur permainan optimal adalah sebagai berikut :
- Pak Dengklek memilih pohon ke-1
- Pak Ganesh memilih pohon ke-2
- Pak Dengklek memilih pohon ke-3
- Pak Ganesh memilih pohon ke-4
---
### Soal 12
#### Problemsetter : Arnold
**Deskripsi**
Jika ditambahkan aturan main sebagai berikut :
- Apabila pemain mengambil jenis buah yang sama dengan jenis buah yang diambil oleh pemain sebelumnya, maka skor yang akan ia dapatkan dari giliran ini akan dibagi dengan $2$ dan dibulatkan ke bawah (misal apabila pemain sebelumnya mengambil jeruk dan pemain saat ini mengambil 9 jeruk, maka ia akan mendapatkan $\lfloor\frac{9}{2}\rfloor = 4$ poin)
Maka apabila terdapat susunan seperti berikut :
Siapakah yang akan memenangkan permainan dan berapakah **selisih skor akhir** pemain pemenang dan pemain yang kalah?
a. Pak Ganesh, selisih 4 poin
b. Pak Dengklek, selisih 5 poin
c. Pak Ganesh, selisih 3 poin
d. Pak Dengklek, selisih 4 poin
e. Pak Ganesh, selisih 5 poin
**Jawaban**
Pak Ganesh, selisih 4 poin
**Pembahasan**
Kita dapat menggunakan DP
Sebut saja $dp(L, R, who, last)$ adalah selisih skor optimal apabila pohon berisi buah berada pada jangkauan $[L,R]$ (inklusif) dan saat ini adalah giliran pemain $who$ dan buah yang diambil pemain sebelumnya adalah $last$
Sudut pandangnya adalah sebagai berikut :
1. Skor yang didapatkan oleh Pak Dengklek akan **menambahkan** selisih skor akhir
2. Skor yang didapatkan oleh Pak Ganesh akan **mengurangi** selisih skor akhir
Kemudian transisi DP nya adalah seperti berikut :
1. Jika $who$ adalah Pak Dengklek, ia ingin membuat selisih skor akhir sebesar mungkin (karena semakin besar selisihnya, semakin tinggi skor Pak Dengklek)
2. Jika $who$ adalah Pak Ganesh, ia ingin membuat selisih skor akhir sekecil mungkin (karena semakin kecil selisihnya, semakin tinggi skor Pak Ganesh)
Maka dua opsi dari pemain manapun akan membuat transisi DP sebagai berikut :
1. Mengambil buah dari pohon terkiri :
$kiri = dp(L+1, R, \neg who, tipe_L) + banyakBuah_L$
2. Mengambil buah dari pohon terkanan :
$kanan = dp(L, R-1, \neg who, tipe_R) + banyakBuah_R$
Notasi :
- $banyakBuah$ adalah banyak buah pada suatu pohon. Nilainya akan positif jika Pak Dengklek adalah pemain yang berjalan, atau negatif jika Pak Ganesh adalah pemain yang berjalan
- $tipe$ adalah jenis buah pada pohon yang diambil
- $\neg who$ adalah tanda bahwa pemain yang berjalan diganti oleh pemain berikutnya
Dengan transisi DP diatas, maka kita bisa menyimpulkan bahwa nilai dari $dp(L, R)$ adalah :
- Jika $who$ adalah Pak Dengklek :
$max(kiri, kanan)$
- Jika $who$ adalah Pak Ganesh :
$min(kiri, kanan)$
Maka untuk soal ini, dengan membuat DP diatas, kita dapat menyimpulkan alur permainan optimal seperti berikut :
| Giliran | Mengambil dari Pohon nomor| Selisih skor akhir |
| -------- | -------- | -------- |
| Pak Dengklek | $1$ | $+5$ |
| Pak Ganesh | $2$ | $-8$ |
| Pak Dengklek | $3$ | $\lfloor\frac{+10}{2}\rfloor = +5$ |
| Pak Ganesh | $4$ | $-7$ |
| Pak Dengklek | $5$ | $+4$ |
| Pak Ganesh | $6$ | $-3$ |
Selisih skor akhir : $-4$
Artinya Pak Ganesh menang mengungguli Pak Ganesh dengan selisih $4$ poin.
---
### Soal 13
#### Problemsetter : Edbert
**Deskripsi**
Pak Dengklek memiliki sebuah array yang terdiri dari 10 buah angka. Karena dirasa array tersebut cukup panjang maka ia berencana untuk membagi array tersebut menjadi 2 buah array.
Sistem yang Pak Dengklek terapkan adalah sebagai berikut. Beliau akan memilih sebuah indeks $i$ dimana $1 \le i \le 9$ dan angka pertama sampai angka ke-$i$ akan menjadi array pertama sedangkan angka ke-$(i + 1)$ sampai dengan angka ke-$10$ akan menjadi array kedua.
Pak Dengklek akan senang jika total angka di array pertama sama dengan total angka di array kedua.
Jika array Pak Dengklek adalah sebagai berikut :
$[3, 2, -4, 3, -2, 1, -4, 3, 4, -2]$
Ada berapa kemungkinan $i$ sehingga Pak Dengklek akan senang?
A.1
B.2
C.3
D.4
E.5
**Jawaban**
B
**Pembahasan**
kita bisa membuat sebuah prefix sum yang akan menjadi seperti ini [3,5,1,4,2,3,-1,2,6,4]. Kita bisa melihat bahwa total semua angka di array awal kita itu 4,sehingga Pak Dengklek akan senang jika total angka pertama sampai ke-i adalah total/2 yaitu 2.(karena jika total angka pertama sampai angka ke-i adalah 2 maka total angka ke (i + 1) sampa angka ke 10 pun juga 2 yang mengakibatkan mereka memiliki total nilai yang sama)
Sehingga kita tinggal mencari berapa banyak kemunculan angka 2 di prefix sum kita dan ternyata banyaknya ada 2.
---
### Soal 14
#### Problemsetter : Arnold
Inspirasi : classical hat problem
**Deskripsi**
Terdapat $3$ buah topi biru dan $2$ buah topi merah. Anita, Bayu, dan Cika sedang berdiri di sebuah barisan. Awalnya, mereka diberikan topi secara acak pada kepalanya
Diketahui :
- Anita berdiri di paling depan, Bayu di tengah, dan Cika di paling belakang.
- Seseorang tidak bisa mengetahui warna topi yang dipakainya
- Seseorang bisa melihat semua warna topi dari orang yang ada di depannya
Kemudian percakapan berikut terjadi :
Anita : "Aku tidak tahu warna topiku"
Cika : "Aku juga tidak tahu warna topiku"
Bayu : "Aku juga tidak tahu warna topiku"
Setelah percakapan tersebut, siapakah yang bisa menebak warna topinya secara pasti? Dan apakah warna topinya? (Asumsikan setiap orang dapat membuat kesimpulan dari pernyataan orang yang lain)
a. Anita, topi merah
b. Anita, topi biru
c. Cika, topi merah
d. Cika, topi biru
e. Bayu, topi merah
**Jawaban**
Anita, topi biru
**Pembahasan**
Apabila Cika melihat Anita dan Bayu memakai topi merah, maka ia bisa menebak bahwa ia memakai topi biru. Namun faktanya tidaklah demikian. Sehingga **salah satu dari Anita / Bayu memakai topi biru (1)**
Bayu memiliki informasi (1). Maka dari itu, apabila ia melihat Anita memakai topi merah, ia bisa langsung menebak bahwa ia memakai topi biru. Namun faktanya, Bayu tidak mengetahui warna topinya
Maka dari itu Anita lah yang bisa memastikan ia memakai topi biru
---
### Soal 15
#### Problemsetter : Abdul Rafi
**Deskripsi**
Pada hari yang indah ini pak Bonceng akan mengikuti sebuah contest. Pak Bonceng akan mengikuti 10 buah contest. Probabilitas pak Bonceng memenangkan contest adalah $\dfrac{2}{3}$ jika pak Bonceng memenangkan contest sebelumnya dan $\dfrac{1}{3}$ jika pak Bonceng kalah pada contest sebelumnya. Jika pak Bonceng memenangkan pertandingan pertamanya, probabilitas pak Bonceng memenangkan tepat 9 dari 10 contest adalah $\dfrac{m}{n}$ dimana m dan n relatif prima. Berapakah nilai $m + n$ ?
A.6104
B.568
C.99186
D.20963
E.7876
**Jawaban**
$20963$
**Pembahasan**
Untuk soal ini kita dapat membagi permasalahan menjadi 2 kasus.
kasus pertama : pak Bonceng kalah bukan pada contest terakhir
Probabilitas pak Bonceng kalah pada sebuah contest adalah $\dfrac{1}{3}$ dan probabilitas untuk menang setelah kalah adalah $\dfrac{1}{3}$. Untuk sisa pertandingan pak dengklek dapat memenangkan pertandingan dengan probabilitas $\dfrac{2}{3}$.
probabilitas untuk kasus pertama = $\left(\dfrac{1}{3}\right)^2 * \left(\dfrac{2}{3}\right)^7$
untuk kasus pertama terdapat 8 cara berbeda sehingga
total probabilitas untuk kasus pertama = $8 * \left(\dfrac{1}{3}\right)^2 * \left(\dfrac{2}{3}\right)^7$
Kasus kedua : pak Bonceng kalah pada contest terakhir
Probabilitas pak Bonceng kalah pada sebuah contest adalah $\dfrac{1}{3}$. Untuk sisa pertandingan pak dengklek dapat memenangkan pertandingan dengan probabilitas $\dfrac{2}{3}$.
probabilitas untuk kasus pertama = $\left(\dfrac{1}{3}\right) * \left(\dfrac{2}{3}\right)^8$
probabilitas dari semua kasus = $8 * \left(\dfrac{1}{3}\right)^2 * \left(\dfrac{2}{3}\right)^7$ + $\left(\dfrac{1}{3}\right) * \left(\dfrac{2}{3}\right)^8$ = $\dfrac{1280}{19683}$
$m + n = 1280 + 19683 = 20963$
---
### Bagian 2 - Isian Singkat
#### (10 soal analitika/logika/matematika, 10 soal algoritmika)
---
### Soal 16
#### Problemsetter : Arnold
Inspirasi : OSP Kom 2014 no 50
**Deskripsi**
Toni mempunyai tongkat kayu sepanjang $100$ cm dan ia hendak memotong motong kayu tersebut. Ia ingin membentuk potongan sebanyak-banyaknya yang memenuhi syarat berikut :
- Tidak boleh ada 3 potongan kayu yang bisa membentuk segitiga
- Panjang potongan kayu harus berupa bilangan bulat
Berapa banyak potongan kayu maksimal yang dapat dibentuk Toni?
**Jawaban**
9
**Pembahasan**
Tiga potongan kayu dengan panjang $x, y, z$ dimana $(x ≤ y ≤ z)$ bisa membentuk segitiga apabila $x + y > z$
Maka potongan kayu yang bisa dibentuk Toni masing-masing akan memiliki panjang
$1, 1, 2, 3, 5, 8, 13, 21, 46$
---
### Soal 17
#### Problemsetter : Abdul Rafi
**Deskripsi**
Pada hari yang indah ini pak Bonceng akan mewarnai lantainya. Lantai pak Bonceng berukuran $8 \times 1$ meter. Pak bonceng ingin dapat mewarnai lantainya dengan ubin berwarna merah, biru, atau hijau. Tiap ubin bisa berukuran $n \times 1$ meter $(1 \le n \le 7)$. Pak Bonceng sangat menyukai warna merah, biru, dan hijau maka, ia ingin ubinnya memiliki ketiga warna tersebut. Berapa susunan ubin berbeda yang bisa pak Bonceng lakukan ?
Note : pewarnaan $1 \times 4$ meter ubin merah diikuti dengan $1 \times 2$ meter ubin biru diikuti dengan $1 * 1$ meter ubin hijau akan berbeda dengan $1 \times 4$ meter ubin merah diikuti dengan $1 \times 1$ meter ubin biru diikuti dengan $1 \times 1$ meter ubin biru diikuti dengan $1 \times 1$ meter ubin hijau.
**Jawaban**
$36414$
**Pembahasan**
Kita bagi menjadi soal ini menjadi dua permasalahan. pertama, ada berapa cara membagi lantai menjadi ubin. kedua, ada berapa cara memilih warna dari susunan ubin yang sudah dipilih
Permasalahan pertama dapat diselesaikan mengunakan stars and bars
Bagi lantai menjadi 3 bagian ubin = $\dbinom{7}{2}$ = 21
Bagi lantai menjadi 4 bagian ubin = $\dbinom{7}{3}$ = 35
Bagi lantai menjadi 5 bagian ubin = $\dbinom{7}{4}$ = 35
Bagi lantai menjadi 6 bagian ubin = $\dbinom{7}{5}$ = 21
Bagi lantai menjadi 7 bagian ubin = $\dbinom{7}{6}$ = 7
Bagi lantai menjadi 8 bagian ubin = $\dbinom{7}{7}$ = 1
Permsalahan kedua dapat diselesaikan dengan inklusi eksklusi
Mewarnai lantai yang dibagi menjadi 3 bagian = $3^3 - 3 * 2^3 + 3$ = 6
Mewarnai lantai yang dibagi menjadi 4 bagian = $3^4 - 3 * 2^4 + 3$ = 36
Mewarnai lantai yang dibagi menjadi 5 bagian = $3^5 - 3 * 2^5 + 3$ = 150
Mewarnai lantai yang dibagi menjadi 6 bagian = $3^6 - 3 * 2^6 + 3$ = 540
Mewarnai lantai yang dibagi menjadi 7 bagian = $3^7 - 3 * 2^7 + 3$ = 1806
Mewarnai lantai yang dibagi menjadi 8 bagian = $3^8 - 3 * 2^8 + 3$ = 5796
terkahri kita harus mengabungkan kedua cara tersebut
$21 * 6 + 35 * 36 + 35 * 150 + 21 * 540 + 7 * 1806 + 1 * 5796 = 36414$
---
### Soal 18
#### Problemsetter : Arnold
Inspirasi : Pas lagi boker
**Deskripsi**
Diberikan sebuah grid berukuran $4 \times 4$ seperti di bawah ini
Sebuah *path* disebut sebuah *path* valid jika :
- Melewati **setidaknya** sebuah petak pada grid
- Apabila kita berada di sebuah petak, kita boleh bergerak ke kiri, kanan, atas, ataupun bawah dari petak sekarang apabila petak tersebut memiliki nomor **lebih besar** daripada nomor petak sekarang (lihat ilustrasi untuk lebih jelasnya)
Berikut contoh path yang valid :
Berikut contoh path yang tidak valid :
(Petak yang diberi gradasi berwarna lebih gelap adalah petak awal *path*)
Ada berapa banyak *path* valid?
**Jawaban**
76
**Pembahasan**
Kita dapat menggunakan pendekatan *dynamic programming*. Awalnya kita akan membentuk tabel DP dimana $dp(i, j)$ adalah berapa banyak path valid yang memiliki petak akhir pada petak $(i, j)$
Maka :
$dp(i, j) = dp(i-1, j) + dp(i, j-1) + dp(i, j+1) + dp(i+1, j) + 1$
atau $dp(i, j) = 0$ jika $(i, j)$ berada di luar petak
Dengan aturan tambahan : kita harus mengisi tabel DP dari petak bernomor terkecil hingga terbesar. Maka akan diperoleh tabel DP sbb :
```
2 7 1 6
1 3 11 4
3 1 2 3
4 6 9 13
```
Kemudian kita tinggal menjumlahkan semua *value*nya saja
---
### Soal 19
#### Problemsetter : Faishol
**Deskripsi**
Bilangan oktal adalah bilangan yang digitnya tersusun atas digit 0 hingga 7. Apabila $N={2019}^{{2021}^{2023}}$ dinotasikan dalam bilangan oktal, maka dua digit terakhirnya dari kanan adalah ...
**Jawaban**
63
**Pembahasan**
$$\begin{align}
{2019}^{{2021}^{2023}} \bmod{8^2} &={(2019 \bmod{8^2})}^{{2021}^{2023}} \bmod{8^2} \\
&= {35}^{{2021}^{2023}} \bmod{8^2} \\
&= {35}^{({2021}^{2023} \bmod \phi(8^2))} \bmod{8^2} \\
&= {35}^{({2021}^{2023} \bmod 32)} \bmod{8^2} \\
&= {35}^{({5}^{2023}\bmod 32)} \bmod{8^2} & (a)\\
\end{align}$$
Perhatikan bahwa pada bagian pangkat, didapatkan:
$$\begin{align}
{5}^{2023} \bmod 32 &= {5}^{2023 \bmod \phi(32)} \bmod 32 \\
&= {5}^{2023 \bmod 16} \bmod 32 \\
&= {5}^{7} \bmod 32 \\
&= 13
\end{align}$$
Substitusikan ke $(a)$ didapatkan:
$$\begin{align}
{35}^{({5}^{2023}\bmod 32)} \bmod{8^2} &= {35}^{13} \bmod{8^2} \\
&= ({9}^{6} \cdot 35) \bmod{8^2} \\
&= ({17}^{3} \cdot 35) \bmod{8^2} \\
&= ({17}^{3} \cdot 35) \bmod{8^2} \\
&= (49 \cdot 35) \bmod{8^2} \\
&= 51\end{align}$$
Mengingat bahwa yang diminta dalam bentuk oktal, maka jawabannya $(51)_{10} = {63}_8$.
\end{align}$$
---
### Deskripsi Soal 20 - 22
#### Problemsetter : Arnold
Inspirasi : https://codeforces.com/contest/1627/problem/B
**Deskripsi**
Simp (seorang laki-laki) memiliki perasaan terpendam pada Kimi dan senang sekali *membucin*. Sayangnya, Kimi tahu mengenai hal ini dan tidak memiliki perasaan yang sama (*ouch* 💔)
Kelas mereka tersusun dari kolom yang dinomori 1 hingga 5 dari kiri ke kanan dan baris yang dinomori 1 hingga 5 dari atas ke bawah. Suatu ketika mereka ingin duduk di kelas dengan denah tempat duduk seperti berikut:
Simp ingin duduk **sedekat mungkin** dari Kimi, sedangkan Kimi ingin duduk **sejauh mungkin** dari Simp. Disini, jarak dari dua bangku yang terletak pada petak $(b_1, k_1)$ dan bangku pada petak $(b_2, k_2)$ adalah $|b_1 - b_2| + |k_1 - k_2|$
- Awalnya Kimi akan meminta **sejumlah** orang temannya untuk masing-masing mengisi satu bangku yang masih kosong
- Simp kemudian akan memilih satu bangku yang masih kosong untuk ia duduki
- Kimi kemudian akan menempati satu bangku kosong untuk ia duduki
### Soal 20
Apabila Kimi tidak memiliki teman (*hiks*), pada petak berapakah Simp harus duduk agar ia bisa duduk sedekat mungkin dengan Kimi? (Tuliskan nomor baris dan kolom dalam format `b k`)
**Jawaban**
3 3
**Pembahasan**
Jika Simp duduk di petak (3,3), maka Kimi akan memilih salah satu bangku di paling ujung agar jarak antara Simp dan Kimi adalah $4$
### Soal 21
Apabila Kimi memiliki $8$ orang teman, berapakah jarak bangku tempat Kimi duduk ke bangku tempat Simp duduk pada akhirnya?
**Jawaban**
$6$
**Pembahasan**
Teman-teman Kimi dapat menempati bangku-bangku berikut. Angka yang tertera pada petak adalah **jarak terjauh** Simp dari Kimi pada akhirnya. Karena Kimi dan Simp ingin melakukan *strategi optimal*, maka sebisa mungkin Kimi menempatkan teman-temannya pada bangku-bangku yang memberikan jarak terakhir *sekecil* mungkin
Kemudian setelah Kimi menempatkan teman-temannya, Simp dapat menempati salah satu bangku yang memberikan jarak $6$ dan Kimi akan memilih bangku yang berjarak $6$ setelahnya
### Soal 22
Apabila Kimi memiliki $8$ orang teman, berapa banyak cara peletakkan teman berbeda yang membuat jarak akhir antara Kimi dan Simp sejauh mungkin ?
**Jawaban**
612
**Pembahasan**
Perhatikan bahwa Kimi ingin jarak terakhir sejauh mungkin. Dari observasi yang didapatkan pada soal no 21, kita dapat memperoleh bahwa jarak maksimal adalah $6$. Sehingga Kimi akan menempatkan teman-temannya sedemikian sehingga jarak akhir dari titik Simp ke Kimi adalah 6. Strateginya adalah menempatkan $5$ orang temannya terlebih dahulu pada petak petak berikut :
Kemudian, ia akan memilih ketiga bangku sisanya dari bangku-bangku yang belum diduduki
Dari 20 bangku yang belum diduduki, terdapat beberapa observasi tambahan :
1. Apabila teman Kimi TIDAK duduk di bangku pada titik ujung (*corner*), maka dimanapun Simp duduk, Kimi dapat memilih titik ujung terjauh dari tempat Simp duduk dan memperoleh jarak sebesar 6. Sehingga dalam kasus ini terdapat $C(16, 3) = 560$ kemungkinan
2. Apabila **tepat** 1 orang teman Kimi duduk di bangku paling ujung, maka terdapat **tepat** 2 konfigutasi lain yang membuat jarak Simp ke Kimi berjarak 6. Sehingga Kimi harus menempatkan 2 teman nya di tempat tersebut. Sehingga untuk setiap titik *corner*, terdapat $2 \times 4 = 8$ kemungkinan
3. Apabila 2 atau 3 orang teman Kimi duduk di *corner*, maka Simp bisa memilih suatu bangku sedemikian sehingga jarak antara Simp dan Kimi $< 6$ sehingga tidak ada kemungkinan
Maka total semuanya terdapat $568$ kemungkinan
---
### Soal 23
#### Problemsetter : Valerian
**Deskripsi**
Urutan permutasi ABC dari 1 sampai 6 adalah ABC, ACB, BAC, BCA, CAB, CBA. Pada permutasi ABCDE, permutasi pada urutan ke 100 adalah ...
**Jawaban**
$EACDB$
**Pembahasan**
Tentukan terlebih dahulu karakter pada posisi paling signifikan (paling kiri). Untuk menentukannya, kita tahu bahwa permutasi dari 4 karakter lainnya adalah $4! = 24$, maka secara berurutan terdapat $24$ permutasi yang diawali $A$, $24$ permutasi yang diawali $B$, $24$ permutasi yang diawali $C$ dan seterusnya.
Sehingga pada urutan ke 100, permutasinya diawali oleh karakter ke $\lceil\frac{100}{24}\rceil=5$ yaitu $E$.
Sekarang kita hanya perlu mencari permutasi ke $100 \bmod 24 = 4$ dari 4 karakter tersisa yaitu $ABCD$ dengan cara yang sama, yaitu $\lceil\frac{4}{3!}\rceil=1$ sehingga karakter ke 2 adalah $A$.
Setelah itu kita cari permutasi ke $4\bmod6=4$ dari 3 karakter yang tersisa yaitu $BCD$, yaitu $\lceil\frac{4}{2!}\rceil=2$ sehingga karakter ke 3 adalah $C$.
Lalu kita cari permutasi ke $4\bmod2=0$ dari 2 karakter tersisa yaitu $BD$, perhatikan jika kita mencari permutasi ke $0$, maka kita mencari permutasi terakhirnya, maka jawaban akhirnya adalah $EACDB$
---
### Soal 24
#### Problemsetter : Abdul Rafi
**Deskripsi**
Pada hari yang indah ini pak Bonceng bermain dengan bilangan. Bilangan favorit pak Bonceng untuk saat ini adalah $100!$ (100 faktorial). Pak Boceng tahu bahwa bilangan favoritnya memiliki sangat banyak faktor. Pak Bonceng sekarang ingin memilih angka random dari semua faktor bilangan favoritnya. Pak Bonceng bertanya, berapa probabilitas bilangan yang didapatkan adalah bilangan genap?
**Jawaban**
$\dfrac{97}{98}$
**Pembahasan**
Kita dapat menyelesaikan soal ini dengan mencari pangkat 2 dari faktorisasi prima $100!$
$\lfloor \frac{100}{2} \rfloor + \lfloor \frac{100}{4} \rfloor + \lfloor \frac{100}{8} \rfloor + \lfloor \frac{100}{16} \rfloor + \lfloor \frac{100}{32} \rfloor + \lfloor \frac{100}{64} \rfloor = 97$
kita tahu bahwa terdapat $2^{97}$ merupakan salah satu faktor prima dari 100!. agar bilangan yang dihasilkan bilangan genap maka perlu setidaknya satu faktor dari bilangan 2. sehingga dari 98 kemungkinan terdapat 97 cara untuk memilih pangkat dari 2
probabilitas terbentuk bilangan genap adalah $\dfrac{97}{98}$
---
### Soal 25
#### Problemsetter : Ester
**Deskripsi**
Kamu hendak mengirimkan cokelat surprise menggunakan robot ke rumah Ayang, tapi lupa alamatnya. Untungnya kamu punya foto rumah Ayang, dan robotmu pintar sehingga bisa mengenali rumah Ayang ketika menemukannya.
Kompleks tempat kamu dan Ayang tinggal berbentuk graf, setiap node adalah rumah sesuai dengan nomornya, dan edge adalah jalan dua arah yang menghubungkan 2 rumah. Angka pada setiap jalan menunjukkan panjang jalan dalam meter.
Kamu tinggal di rumah nomor 1. Kamu bisa menyuruh robotmu pergi ke salah satu rumah. Jika rumah itu bukanlah rumah Ayang, robotmu akan kembali ke rumahmu dan kamu bisa memilih rumah lain untuk dikunjungi. Jika rumah itu adalah rumah Ayang makan robotmu akan langsung memberikan cokelat itu pada Ayang.
Contohnya, jika kamu memilih rumah nomor 2, robotmu bisa pergi dari rumah nomor 1 (rumahmu) ke rumah nomor 8 sejauh 11 meter, lalu dari rumah nomor 8 ke rumah nomor 2 sejauh 10 meter. Jika rumah Ayang bukanlah nomor 2, maka robot akan kembali (melalui rute yang sama) sehingga total jarak yang dia tempuh adalah 11 + 10 + 10 + 11 = 42 meter. Jika rumah Ayang adalah nomor 2, total jarak yang dia tempuh adalah 11 + 10 = 21 meter.
Robotmu bisa juga langsung pergi dari rumah nomor 1 (rumahmu) ke rumah nomor 2 sejauh 14 meter. Jika rumah Ayang bukanlah nomor 2, total jarak yang dia tempuh adalah 14 + 14 = 28 meter. Jika rumah Ayang adalah nomor 2, total jarak yang dia tempuh adalah 14 meter.
Berapa jarak tempuh minimum yang dibutuhkan robot agar cokelat dipastikan sampai ke rumah Ayang?
**Jawaban**
$367$
**Pembahasan**
Agar cokelat pasti sampai ke rumah Ayang, kita perlu mengunjungi semua rumah satu kali. Maka, kita perlu mencari jarak terdekat ke semua rumah.
Kemungkinan terburuknya adalah rumah Ayang berada di rumah terjauh (rumah nomor 10). Supaya optimal, kita akan mengunjungi rumah terjauh terakhir. Dengan begitu, untuk pergi ke rumah terakhir hanya perlu dihitung jarak sekali jalan.
Jadi $2*(11 + 12 + 13 + 14 + 16 + 18 + 19 + 20 + 23 + 24) + 27 = 367$
### Soal 26
#### Problemsetter : Abdul Rafi
**Deskripsi**
Perhatikan porongan program berikut!
Nilai kembalian dari pemanggilan fungsi `raiden(1225)` adalah
**Jawaban**
2047
**Pembahasan**
Hasilnya adalah bilangan $2^n-1$ terkecil yang lebih besar atau sama dengan x
### Soal 27
#### Problemsetter : Abdul Rafi
Nilai kembalian dari pemanggilan fungsi `raiden(346541234)` adalah
**Jawaban**
$536870911$
### Soal 28
#### Problemsetter : Arnold
**Deskripsi**
Perhatikan potongan kode berikut
```cpp
int get(int a, int b){
int res = 0;
for(int i=9; i>=0; i--){
res <<= 1;
res |= ((a>>i)&1) ^ ((b>>i)&1);
}
return res;
}
```
Jika diketahui a = 25 dan b = 18, berapakah nilai dari `get(a,b)`?
**Jawaban**
11
**Pembahasan**
Kita cukup melakukan operasi $a \oplus b = 25_{10} \oplus 18_{10} = 11001_2 \oplus 10010_2 = 01011_2 = 11_{10}$
---
### Soal 29
#### Problemsetter : Arnold
**Deskripsi**
Perhatikan potongan kode dibawah berikut :
```cpp
int go(int l, int r){
if(l > r) return 0;
return 1 + play(l, r-1) + play(l+1, r);
}
int play(int l, int r){
if(l > r) return 1;
return 1 + go(l, r-1) + go(l+1, r);
}
```
Berapakah nilai dari `play(3,7)`?
**Jawaban**
31
**Pembahasan**
Kita bisa melihat bahwa yang mempengaruhi nilai fungsi `go` dan `play` hanyalah selisih dari `l` dan `r` nya saja. Dimana :
`go(l, r) = go(r-l)` dan
`play(l, r) = play(r-l)`
maka :
`go(n) = 1 + 2 * play(n-1)`
`play(n) = 1 + 2 * go(n-1)`
dimana `go(-1) = 0` dan `play(-1) = 1`
---
### Soal 30
#### Problemsetter : Faishol
**Deskripsi**
```cpp
int satu(int x) {
return (x + 1) % (1 << 1);
}
int dua(int x, int y) {
if (x == 0 && y == 0) return 0;
else {
int a = (x % 2) & satu(y % 2);
int b = (y & 1) & satu(x & 1);
return (dua(x / 2, y / 2) << 1) | (a | b);
}
}
int tiga(int x[]) {
int ret = 0;
int y[5];
for (int i = 1; i <= 5; i++) {
ret = dua(ret, x[i % 5]);
y[i % 5] = dua(x[i - 1], x[i % 5]);
}
return ret;
}
```
Hasil dari pemanggilan `dua(16, 15)` adalah...
**Jawaban**
31
**Pembahasan**
`dua(x,y)`$= x \oplus y$
---
### Soal 31
#### Problemsetter : Faishol
**Deskripsi**
```cpp
int satu(int x) {
return (x + 1) % (1 << 1);
}
int dua(int x, int y) {
if (x == 0 && y == 0) return 0;
else {
int a = (x % 2) & satu(y % 2);
int b = (y & 1) & satu(x & 1);
return (dua(x / 2, y / 2) << 1) | (a | b);
}
}
int tiga(int x[]) {
int ret = 0;
for (int i = 1; i <= 5; i++) {
ret = dua(ret, x[i % 5]);
cout << dua(x[i - 1], x[i % 5]) << " ";
}
return ret;
}
```
Apabila hasil dari pemanggilan `tiga(a)` adalah 76, serta menghasillkan keluaran `74 22 18 26 84`, tentukan nilai dari `a`!
**Jawaban**
[64, 10, 28, 14, 20]
**Pembahasan**
Kembalian dari `tiga(a)` adalah hasil xor dari seluruh elemen di a. Jadi kita bisa dapatkan nilai elemen terakhir dari a dengan meng-xor nilai kembalian dengan keluaran ke-1 dan ke-3. Lalu kita tinggal meng-xor satu persatu sisanya untuk mendapat setiap elemen.
---
### Soal 32
#### Problemsetter : Faishol
**Deskripsi**
```cpp
int main() {
int x[2023];
for (int i = 0; i < 2023; i++)
x[i] = i;
for (int i = 2; i < 2023; i++) {
for (int j = i; j < 2023; j += i)
x[j]--;
}
cout << x[1005] << " " << x[2022];
}
```
Keluaran dari program di atas adalah...
**Jawaban**
998 2015
**Pembahasan**
x[i] akan bernilai $i - (\tau(i) - 1)$.
x[1005] = 1005 - 7 = 998
x[2022] = 2022 - 7 = 2015
---
### Soal 33
#### Problemsetter : Faishol
**Deskripsi**
```cpp
int main() {
int x;
int sum = 0;
cin >> x;
for (int i = x + 6; i > x; i--) {
sum += i;
}
cout << (sum % 6) % 3;
}
```
Apabila input diasumsikan 32-bit signed integer, tentukan semua kemungkinan keluaran dari program di atas... (Tuliskan terurut menaik dipisahkan koma)
**Jawaban**
0
**Pembahasan**
`(sum % 6)` hanya memiliki 1 kemungkinan nilai, yakni 3. Maka `(sum % 6) % 3` = 0.
---
### Soal 34
#### Problemsetter : Faishol
**Deskripsi**
```cpp
int uwu(int a, int b) {
if (a > b) return a;
return b;
}
int main() {
int x[] = {21, 17, 21, 9, 18, 10, 4, 25, 12, 17};
int sum = 0;
for (int i = 0; i < 10; i++) {
for (int j = i + 1; j < 10; j++) {
for (int k = j + 1; k < 10; k++) {
sum += uwu(uwu(x[i], x[k]), x[j]);
}
}
}
cout << sum;
}
```
Keluaran dari program di atas adalah...
**Jawaban**
2517
**Pembahasan**
Inti soalnya untuk setiap kemungkinan 3 bilangan, cari maxnya lalu jumlahkan. Array x setelah disort 4, 9, 10, 12, 17, 17, 18, 21, 21, 25.
$$\begin{align}
\text{Jawaban} &=\sum\limits_{i=3}^{10}x_{sort}[i] \times \binom{i-1}{2} \\
&= 10 \times \binom{2}{2} + 12 \times \binom{3}{2} + \cdots + 25 \times \binom{9}{2} \\
&= 2517
\end{align}$$
---
### Soal 35
#### Problemsetter : Faishol
**Deskripsi**
```cpp
int koder(int x, int y, int z) {
int a = abs(x - y);
int b = abs(x + y - 2*z - a);
return (x + y + 2*z - a - b) / 4;
}
```
Agar saat dilakukan pemanggilan `koder(2345,s,9876)` mengembalikan 2022, maka nilai `s` adalah ...
**Jawaban**
2022
**Pembahasan**
`koder(x, y, z)` akan mengembalikan nilai minimum diantara x, y, dan z.
---
### Cadangan
### Soal 9
---
### Soal 11
#### Problemsetter : Faishol
**Deskripsi**
Untuk dapat lulus dari ujian, Loko harus menjawab $>80\%$ soal dengan benar. Diketahui bahwa berkas ujian terdiri dari 20 buah soal, dimana pada setiap soal hanya terdapat 1 dari 5 jawaban yang benar. Asumsikan Loko tidak memahami satu pertanyaanpun, maka probabilitas Loko dapat lulus ujian dapat dinyatakan sebagai $\frac{a}{b}$ dimana $a$ dan $b$ relatif prima. Hasil penjumlahan semua faktor prima dari $a$ dan $b$ adalah...
**Jawaban**
76088
**Pembahasan**
Peluang benar = $\frac{1}{5}$
Peluang salah = $\frac{4}{5}$
Jika $X$ adalah peristiwa agar Loko mendapat jawaban benar sebanyak $X$, maka berdasarkan _binomial random variable_, peluang Loko lulus dapat dihitung sebagai:
$$P(X \ge 17) = \sum \limits_{i=17}^{20} \binom{20}{i}\frac{4^{20-i}}{5^{20}} = \frac{76081}{50^{20}}$$
Jadi, hasil penjumlahan semua faktor dari $a$ dan $b$ adalah $76081 + 5 + 2 = 76088$
---
### Soal 23
> [name=Arnold Ardianto] Soalnya kepanjangan kayaknya bagus kalo ada deskripsi terus kasih beberapa soal
#### Problemsetter : Arnold
Inspiration : Ads Mobile Game
**Deskripsi**
Kamu sedang ingin bermain permainan memburu naga. Diketahui terdapat peta berikut :
- Pada mulanya tokoh utama berada pada petak yang diberi huruf S
- Kamu diberikan 2 buah panah atas, 1 buah panah kanan, 1 buah panah bawah, dan 1 buah panah kiri
- Untuk bergerak, letakkan panah yang kamu miliki pada suatu petak. Kemudian tokoh utama akan mengubah arah menghadap sesuai dengan arah panahnya. Kemudian, Tokoh utama akan terus berjalan lurus mengikuti arah panah yang kamu gunakan. Apabila tokoh utama berada di "tepi" peta, maka ia akan berhenti
Diketahui :
- Apabila tokoh utama berdiri di petak berisi sebuah daging, ia akan memakan daging dan mendapatkan energi sebesar 1 unit dan daging di petak tersebut akan hilang
- Apabila tokoh utama berdiri di petak berisi sebuah naga, ada dua kemungkinan :
1. Jika energi tokoh utama < energi naga, maka tokoh utama akan mati (total poin yang sudah dikumpulkan tidak berubah)
2. Jika energi tokoh utama ≥ energi naga, maka energi tokoh utama akan berkurang sebanyak energi naga, lalu total poin bertambah sebesar energi naga tersebut, kemudian naga tersebut akan hilang
(Energi masing masing naga tertera pada gambar diatas)
Berapakah total poin maksimal yang bisa kamu peroleh ?
**Jawaban**
4
**Pembahasan**
Kita dapat meletakkan arah panah sebagai berikut :
---
#### Problemsetter : Faishol
**Deskripsi**
Sebuah kalkulator hanya dapat menampilkan angka 0 hingga 2026 (inklusif), sehingga untuk angka lebih dari itu akan kembali dihitung dari 0. Sebagai contoh, 54321 menjadi 1619 dan 12345 menjadi 183.
Awalnya Pak Bonceng memasukkan sebuah angka ke kalkulator tersebut. Kemudian muncul angka $m$. Lalu ia mengalikannya dengan angka tersebut dengan $m$ juga sebanyak 1350 kali. Jika pada akhirnya angka yang tertera pada kalkulator adalah 128, maka hasil penjumlahan setiap digit dari $m$ adalah...
a. 5
b. 7
c. 13
d. 16
e. 19
**Jawaban**
5
**Pembahasan**
Inti dari persoalan adalah mencari nilai $m$ yang memenuhi $m^{1351} \equiv 128 \pmod{2027}$.
Perhatikan bahwa:
$$\begin{align*}
\left( m^{1351} \right)^{y} \bmod{2027} &= m^{1351y} \bmod{2027} \\
&= m^{1351y \mod{\phi(2027)}} \bmod{2027} \\
&= m^{1351y \mod{2026}} \bmod{2027} \\
\end{align*}$$
Dari persamaan di atas, kita perlu mencari $y$ sehingga $1351y \equiv 1 \pmod{2026}$. Dengan extended euclid, akan didapatkan $y=3$. Maka
$$m={128}^{3} \bmod 2027 = 2097152 \bmod 2027 = 2021$$
Jadi hasil penjumlahan setiap digit dari $m$ adalah $2+0+2+1=5$.
Sign in with Wallet
Connect another wallet