Zafran P. W. Latihan Soal Informatika 18 2/6/2026
Latihan Soal Informatika
Zafran P. W. @zafranm2m February 6, 2026 18 0

[!example] Detail Latihan-latihan yang ditulis untuk persiapan tim Olimpiade Informatika MAN 2 Kota Pekanbaru menuju OSN Informatika 2026.

Latihan 1§

Soal 1–3. Permen Pak Dengklek

Pak Dengklek membawa sejumlah permen ke kelasnya. Ia ingin membagikan permen kepada $N$ siswa yang sedang berbaris. Setiap siswa punya permintaan jumlah permen yang berbeda-beda. Pak Dengklek ingin membagikan permen kepada siswa dari depan ke belakang. Jika permennya tidak cukup untuk memenuhi permintaan siswa berikutnya, maka ia akan melewatkan siswa tersebut dan lanjut ke siswa berikutnya. Proses berhenti jika semua siswa sudah diperiksa atau permen Pak Denglek sudah habis. Tentukan berapa banyak siswa yang berhasil menerima permen sesuai permintaannya.

Soal 1. Pak Dengklek membawa 30 permen. Permintaan dari 10 siswa berturut-turut adalah 4, 5, 10, 3, 6, 2, 1, 7, 2, 4. Berapa siswa yang mendapat permen?

Soal 2. Pak Dengklek membawa 25 permen. Permintaan 7 siswa adalah 3, 8, 5, 2, 11, 2, 1. Namun sekarang jika permen tidak cukup, siswa boleh meminta ulang dengan jumlah setengah permintaan awal dibulatkan ke atas, tapi hanya sekali. Berapa siswa yang berhasil diberi permen?

Soal 3. Diberikan daftar permintaan permen dari beberapa siswa, kita boleh mengatur ulang urutan mereka supaya sebanyak mungkin siswa bisa menerima permen, asalkan total permen yang dimiliki Pak Dengklek tidak berubah. Sekarang Pak denglek memiliki sejumlah 2025 permen, uniknya lagi dari 1000 siswa yang berbaris, permintaan mereka adalah 1000 bilangan pertama dengan semua penyusun angkanya tidak ada angka yang sama. Tentukan berapa banyak siswa yang mendapatkan permen!

Soal 4–6. Festival Lampion

Setiap tahun, Kota Binary mengadakan Festival Lampion. Warga kota menghias rumah dengan lampu berwarna merah ($\mathtt{R}$) atau biru ($\mathtt{B}$). Di setiap jalan, lampu-lampu dinyalakan dalam barisan dari kiri ke kanan.

Panitia festival memberikan beberapa aturan agar lampion terlihat indah:

Tidak boleh ada dua warna yang sama berdampingan lebih dari dua kali. Contoh yang tidak valid adalah $\mathtt{RRR}$ dan $\mathtt{BBB}$. Contoh yang valid adalah $\mathtt{RR}$, $\mathtt{BB}$, dan $\mathtt{BR}$. Setiap susunan lampu harus memiliki jumlah lampu genap. Warga boleh memilih sendiri urutan warnanya selama aturan dipatuhi.

Soal 4. Panitia sedang membuat sistem pengecekan otomatis. Mereka menyusun algoritma berikut: “Mulai dari indeks ke-$1$, periksa setiap tiga lampu berturut-turut sebelumnya. Jika ditemukan pola yang semuanya sama ($\mathtt{RRR}$ atau $\mathtt{BBB}$), tolak barisan lampu.”

Diberikan barisan 10 lampu,

$$ \mathtt{BBRRRBRBBR} $$

Apakah algoritma akan menolak barisan ini? Jika iya, di indeks ke berapa ditemukan pelanggaran pertama?

Soal 5. Seorang warga ingin menghias rumah dengan lampu sepanjang 8 unit. Ia ingin menghitung jumlah susunan berbeda yang mematuhi semua aturan festival. Berapa banyak kombinasi yang mungkin?

Soal 6. Kwak sekarang membantu warga menghias rumah secara otomatis. Tapi, ia hanya bisa menyimpan 3 warna terakhir di memorinya. Jika Kwak ingin memastikan bahwa setiap lampu yang ia tambahkan tidak membuat 3 warna yang sama berturut-turut, dan panjang target barisan adalah 12, berapa jumlah maksimum kombinasi valid yang Kwak bisa hasilkan dengan memorinya yang terbatas?

Soal 7–9. ZLR

Perhatikan kode berikut.

int Z(int l, int r) {
    if (l < r) {
        int mid = (l + r) / 2;
        return Z(l, mid - 1) + Z(mid + 1, r) + 1;
    } else if (l == r) {
        return 1;
    } else {
        return 0;
    }
}

Soal 7. Tentukan hasil dari pemanggilan Z(2, 8).

Soal 8. Tentukan nilai dari a terkecil sehingga Z(a, 2*a) lebih besar dari $2^{10}$.

Soal 9. BENAR atau SALAH: Pemanggilan program tersebut sama dengan pemanggilan program dibawah ini.

int Z(int l, int r) {
    if (l >= r) return 1;
    int mid = (l + r) / 2;
    return Z(l, mid) + Z(mid + 1, r);
}

Soal 10–11. >> <<

Perhatikan kode berikut.

int main() {
    int a, b, hasil = 0, temp = 1;
    cin >> a >> b;
    while (a > 0 || b > 0) {
        if ((a % 2) != (b % 2))
            hasil += temp;

        a = a >> 1;
        b = b >> 1;
        temp = temp << 1;
    }
    cout << hasil << endl;
    return 0;
}

Soal 10. Apabila program di atas diberi masukan 8 2, berapakah output yang dihasilkan oleh program tersebut?

Soal 11. Apabila program di atas diberi masukan 120 30, berapakah output yang dihasilkan oleh program tersebut?

Latihan 2§

Soal 1–3. Mbah Dukun Penyantet Angka

Ada mbah dukun yang saat ini memiliki sebuah barisan angka yang terletak pada brankas rahasia $A$. Ada $N$ buah bilangan dengan indeks terurut mulai dari $i = 1$ hingga $i = N$ pada brankas tersebut, atau

$$ A = [A_1, A_2, \dots, A_N]. $$

Mbah dukun ini berbeda dari biasanya, bukannya menyantet orang, malahan ia menyantet suatu angka tertentu menjadi penjumlahan angka tersebut dengan 2025, atau dengan kata lain mbah dukun tersebut dapat memilih satu index $i$​ dan mengubah nilainya menjadi $A_i + 2025$, atau secara formal ubah $A_i := A_i + 2025$.

Mbah dukun ingin memaksimalkan banyaknya subarray$^\dagger$ yang mengandung setidaknya satu bilangan genap. Untuk memaksimalkan banyak subarray tersebut, Mbah dukun dapat menyantet paling banyak satu angka di brankas $A$. Bantulah mbah dukun untuk mencari banyaknya subarray maksimal!

$^\dagger$subarray adalah bagian bersebelahan/berturutan dari sebuah array. Misalkan array $M = [1, 2, 3, 4, 5]$. Maka $[1, 2]$, $[2, 3, 4]$, $[2, 3, 4, 5]$ adalah subarray dari $M$. Sedangkan $[1, 3, 5]$, $[2, 5]$ bukanlah subarray dari $M$.

Soal 1. Jika dalam brankas rahasia mbah dukun berisi sebanyak 6 buah bilangan yang semuanya genap, tentukan banyaknya subarray yang mengandung setidaknya satu bilangan genap.

Soal 2. Jika dalam brankas rahasia mbah dukun berisi sebanyak 6 buah bilangan terurut $A = [4, 3, 6, 1, 5, 10]$, tentukan banyaknya sub array yang mengandung setidaknya satu bilangan genap.

Soal 3. Jika dalam brankas rahasia mbah dukun berisi sebanyak 20 buah bilangan terurut

$$ A = [2, 1, 6, 1, 3, 1000, 3, 5, 7, 9, 13, 21, 1, 8, 6, 5, 3, 4, 2, 1], $$

tentukan banyaknya subarray yang mengandung setidaknya satu bilangan genap.

Soal 4–6. Sihir Penghalang Seorang Mbah Dukun Jahat

Di sebuah dunia magis, terdapat $N$ gua misterius yang diberi nomor dari $1$ hingga $N$. Awalnya, setiap pasang gua terhubung dengan jalur sihir, sehingga ada total $\frac{N(N-1)}{2}$ jalur sihir yang tersedia.

Namun, mbah dukun jahat datang dan menggunakan sihir penghalangnya! Ia dapat menghancurkan beberapa jalur sihir sehingga perjalanan antar gua menjadi semakin sulit.

Setiap gua ke-$i$ memiliki tingkat energi mistis yang dinyatakan dengan bilangan $G_i$. Jika mbah dukun memutus jalur sihir antara gua $i$ dan gua $j$, maka energi sihir yang diperlukan adalah $G_i + G_j$. Namun, mbah dukun hanya bisa menghancurkan jalur sihir dengan total energi maksimal tertentu.

Untungnya, petualang sakti tinggal diantara gua tersebut dan ingin tetap bisa menjelajahi sebanyak mungkin gua yang tersisa serta mbah dukun tidak mengetahui dimana posisi petualang sakti. Jika kamu petualangan sakti tersebut jawablah pertanyaan berikut dengan benar.

Soal 4. Jika hanya terdapat 3 buah goa dengan energi mistis $G = [200, 400, 500]$. Tentukan total energi mistis minimal yang harus dipunyai oleh seorang mbah dukun jahat agar petualang sakti tidak dapat berpindah dari goanya.

Soal 5. Jika terdapat 10 goa mistis dengan semua energi mistisnya sebesar 1. Tentukan jumlah minimum gua yang masih bisa dijangkau termasuk guamu saat ini setelah mbah dukun menghancurkan jalur sihir yang ada jika mbah dukun jahat tersebut memiliki sebanyak 50 buah energi mistis. Tentunya Mbah dukun adalah orang yang juga pintar.

Soal 6. Ternyata suatu hari ada seorang pahlawan super, agar mbah dukun jahat tersebut tidak terlalu banyak merusah energi sihir dengan kekuatan supernya ia jalur sihir yang semula mbah dukun bisa memutus dengan energi sihir $G_i + G_j$ diubah menjadi $G_i \times G_j$. Jika pada saat ini hanya tersisa 6 buah goa dengan masing-masing energinya $G = [35, 15, 10, 25, 10, 5]$, serta energi mistis yang dimiliki oleh mbah dukun jahat tersebut sudah sebesar $1300$ maka tentukanlah minimum gua yang masih bisa dijangkau termasuk goa saat ini jika petualang sakti saat ini berada di goa pertama.

Soal 7–9. Wow

Perhatikan kode berikut.

int Wow(int n) {
    int res = 1;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            res *= (cnt + 1);
        }
    }
    if (n > 1) res *= 2;
    return res;
}

Soal 7. Tentukan nilai dari Wow(31).

Soal 8. Tentukan nilai dari Wow(1000)

Soal 9. Jika nilai dari Wow(n) adalah 12, tentukan nilai dari $n$ terkecil.

Soal 10–11. Bunga

Perhatikan kode berikut.

int Bunga(int x) {
    if (x == 0) {
        return 1;
    } else {
        int Bungai = 0;
        for (int i = 0; i < x; i++) {
            Bungai += Bunga(i);
        }
        return Bungai;
    }
}

Soal 10. Tentukan nilai dari Bunga(4).

Soal 11. Tentukan nilai dari Bunga(22).

Latihan 3§

Soal 1–3. Laboratorium Geometri

Kamu sedang berada dalam sebuah laboratorium geometri yang mempelajari bangun beraturan. Di depanmu terdapat sebuah poligon beraturan yang memiliki $N$ sisi. Pada setiap sisi, para peneliti telah meletakkan beberapa titik khusus. Titik-titik ini berada di sepanjang sisi dan membagi sisi tersebut menjadi bagian-bagian yang sama panjang. Untuk setiap sisi ke-$i$, ada sebanyak $A_i$ titik khusus; dan sisi-sisi diurutkan secara searah jarum jam.

Tugas penelitianmu adalah membangun sebanyak mungkin segitiga yang tidak saling berpotongan. Setiap segitiga harus memakai 3 titik khusus yang berbeda, dan setiap titik hanya boleh dipakai 1 kali. Segitiga harus non-degenerate, artinya luasnya harus positif. Jadi, ketiga titiknya tidak boleh berada pada garis lurus yang sama.

Sebagai contoh jika $A = [3, 1, 4, 6]$ maka kita dapat membuat sebanyak 4 buah segitiga seperti pada gambar.

Ilustrasi

Soal 1. BENAR atau SALAH: Misalkan terdapat suatu poligon yang tidak diketahui ukurannya, namun diketahui terdapat sebanyak 18 titik khusus pada sisi-sisinya. Titik-titik di sekeliling poligon diberi nomor dari 1 sampai 18 secara berurutan searah jarum jam. Segitiga pertama memakai titik $[2, 7, 12]$. Segitiga kedua yang memakai titik $[3, 4, 5]$ pasti tidak memotong segitiga pertama.

Soal 2. Jika diberikan $A = [1, 6, 3, 6, 2]$ maka ada berapa banyak segitiga yang dapat dibuat?

Soal 3. Sebuah poligon memiliki total 31 titik khusus. Namun saat ini, pada masing-masing sisi tidak boleh dipakai lebih dari 4 titik secara total dalam semua segitiga. Jika pada salah satu sisi terdapat 11 titik, berapa banyak segitiga maksimum yang tetap bisa dibuat?

Soal 4–6. Kecantikan Kandang Bebek

Di sebuah peternakan besar, Pak Ganesh memelihara $n$ ekor bebek yang dinomori mulai dari $1$ hingga $n$, dan setiap bebek memiliki:

Untuk menilai seberapa “cantik” manajemen kandang pada hari itu, Pak Ganesh mendefinisikan Nilai Kecantikan Kandang sebagai

$$ \sum_{i=1}^{n} |K_i - P_i| = |K_1 - P_1| + |K_2 - P_2| + \cdots + |K_n - P_n|, $$

atau dengan kata lain, jumlah dari selisih-selisih antara pakan seharusnya dan sebenarnya.

Semakin besar Nilai Kecantikan Kandang, semakin “unik” pula kandang tersebut. Karena artinya, banyak selisih yang ekstrem antara kebutuhan dan pemberian pakan. Pak Ganesh ini kandangnya seunik mungkin.

Ternyata, pekerja kandang terkadang salah menaruh pakan di antara bebek. Oleh karena itu, Pak Ganesh boleh menukar pakan dua bebek maksimal satu kali, karena jika lebih dikhawatirkan para pekerja tersinggung jika Pak Ganesh banyak menukar pakan yang sudah dengan lelah mereka berikan kepada para bebek.

Dengan kata lain, pilih dua indeks $i$ dan $j$ $(i \neq j)$, kemudian tukar $P_i$ dan $P_j$.

Soal 4. Diberikan kebutuhan pakan bebek $K = [3, 5, 2]$, dan pakan sebenarnya $P = [4, 1, 2]$. Hitung Nilai Kecantikan Kandang maksimum.

Soal 5. Diberikan kebutuhan pakan bebek $K = [1, 5, 4, 20]$, dan pakan sebenarnya $P = [4, 2, 10, 7]$. Hitung Nilai Kecantikan Kandang maksimum.

Soal 6. BENAR atau SALAH: Jika kedua array sudah diurut menaik, maka pertukaran acak selalu membuat Nilai Kecantikan Kandang menurun.

Latihan 4§

Soal 1–3. Padepokan Tari Sekar Arum

Di sebuah desa di lereng Gunung Merapi, terdapat sebuah padepokan tari bernama Sekar Arum. Pimpinan padepokan, Mbakyu Ira, ingin menyiapkan sebuah pertunjukan khusus bernama Tari Golek Candra Kinasih. Untuk pertunjukan ini, ia harus memilih tepat $m$ penari dari $n$ murid. Para murid ini dinomori mulai dari 1 hingga $n$.

Murid ke-$i$ memiliki tingkat kematangan tari (level) yang dicatat sebagai angka $L_i$. Tarian ini sangat sakral, sehingga hanya formasi penari tertentu yang dianggap sempurna.

Sebuah formasi dinyatakan sempurna jika semua syarat berikut terpenuhi.

Soal 1. BENAR atau SALAH: Di padepokan, Mbakyu Ira akan memilih $3$ murid dari $10$ murid dengan tingkat kematangan tari $L = [2, 4, 5, 7, 8, 4, 1, 4, 7, 8]$. Tari Golek Candra Kinasih dapat dilakukan.

Soal 2. Saat ini di padepokan, Mbakyu Ira akan memilih $2$ murid saja dari $8$ murid dengan tingkat kematangan tari $L = [1, 5, 2, 2, 3, 1, 3, 3]$. Ada berapa banyak cara Mbakyu Ira akan memilih murid jika $m = 2$.

Soal 3. Dengan sering viralnya Tari Golek Candra Kinasih ini, pada saat ini padepokan Mbakyu Ira memiliki murid yang sangat banyak, lebih tepatnya murid dengan tingkat kematangan $i$ berjumlah banyaknya faktor positif dari $i$, dengan nilai $i$ mulai dari $4$ hingga $10$, jika Mbakyu Ira akan memilih penari dengan jumlah $m = 5$, ada berapa banyak cara Mbakyu Ira memilih murid tersebut?

Soal 4–6. Liga Fiktif Nusantara I

Di Liga Fiktif Nusantara I, kompetisi fiktif di Jawa, terdapat sebuah rumor bahwa beberapa pertandingan di fase playoff telah diatur sedemikian rupa sehingga jalur kemenangan beberapa klub terlihat “terlalu rapi”.

Panitia investigasi ingin melakukan simulasi komputasional untuk menilai apakah suatu skenario playoff tertentu mungkin tercapai secara natural atau mungkin mencurigakan. Anehnya Liga menggunakan format playoff eliminasi tunggal berisi $2^k$ klub. Klub diberi nomor kekuatan sebagai berikut.

Klub berperingkat lebih tinggi selalu menang jika pertandingan berjalan normal. Bracket playoff menggunakan sistem seeding:

Namun, sebagian posisi seed sudah “terisi” oleh klub tertentu, sebagian lagi kosong (belum diketahui). Kamu ingin menghitung berapa banyak cara penempatan seed yang masih tersisa sehingga hasil akhir playoff tepat mengikuti pola eliminasi tertentu (pola yang dicurigai sebagai ‘rekayasa’). Dalam artian

Soal 4. Apakah mungkin hasil akhir playoff sesuai dengan yang diharapkan untuk 4 tim jika tim 1 menempati seed 1, tim 2 menempati seed 2, tim 3 menempati seed 3, dan tim 4 menempati seed 4?

Soal 5. Ada berapa banyak penempatan seed yang mungkin memenuhi hasil akhir playoff, jika terdapat 4 tim yang bertanding dan seed 3 ditempati oleh tim 4.

Soal 6. Saat ini terdapat sebanyak 8 tim yang akan bertanding serta hanya terdapat 1 tim yang sudah mengisi seed, yakni tim 2 mengisi seed 5. Tentukan berapa banyak cara penempatan seed sehingga hasil akhir playoff sesuai dengan yang diharapkan.

Latihan 5§

Soal 1–3. Pak Dengklek dan Ujian Sekolah

Di sebuah SMA Negeri di Jawa Timur, ada seorang guru Matematika bernama Pak Dengklek. Selama satu tahun ajaran, sekolah mengadakan $n$ ujian. Setiap ujian ke-$i$ memiliki tingkat kesulitan $K_i$.

$$ K = [K_1, K_2, \dots, K_n] $$

Ada seorang siswa bernama Bima, yang sangat suka pola angka. Bima merasa tidak nyaman jika dua ujian yang berturutan memiliki tingkat kesulitan dengan FPB yang sangat kecil, dalam hal ini $\operatorname{FPB}(K_i, K_{i+1}) = 1$, Karena menurutnya, “dua ujian yang sulitnya tidak ada hubungannya pasti bikin pusing.” Banyak pasangan ujian berurutan dengan FPB-nya $1$ ini disebut sebagai Tingkat Kekacauan Soal.

Pak Dengklek boleh mengubah nilai kesulitan ujian tertentu menjadi $0$, karena $0$ mungkin dapat membuat FPB berubah. Tetapi untuk menjaga standar sekolah, ia hanya boleh melakukan ini maksimal $k$ kali.

Perlu diperhatikan bahwa $\operatorname{FPB}(0, a) = a$ untuk bilangan bulat positif $a$, dan $\operatorname{FPB}(0, 0) = 0$.

Soal 1. Diberikan tingkat kesulitan ujian $K = [6, 10, 7, 25, 12, 9]$. Jika Pak Denglek belum merubah sama sekali tingkat kesulitan soal, maka tentukanlah nilai dari Tingkat Kekacauan Soal.

Soal 2. Diberikan tingkat kesulitan ujian $K = [6, 10, 7, 25, 12, 9]$. Jika Pak Denglek boleh merubah maksimal satu ujian, maka tentukanlah nilai dari Tingkat Kekacauan Soal.

Soal 3. Di suatu semester yang cukup jenuh, terdapat $20$ ujian dengan tingkat kesulitan awal

$$ K = [1, 1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 9, 10, 1, 1, 1, 2, 3, 1, 1]. $$

Jika Pak Denglek dapat mengubah maksimal 7 ujian, maka tentukan Tingkat Kekacauan Soal pada semester tersebut.

Soal 4–6. Pak Lurah dan Tiga Hadiah Desa

Di sebuah desa di lereng pegunungan Jawa, ada tradisi tahunan bernama Sedekah Desa Tiga Warna. Dalam tradisi ini, Pak Lurah ingin membagikan tiga bingkisan hadiah kepada warga yang telah ditentukan sebelumnya.

Hadiah-hadiah ini harus memenuhi syarat sebagai berikut.

Terkadang total $n$ memungkinkan dibuat menjadi tiga hadiah seperti ini, terkadang tidak. Tugasmu sebagai panitia muda adalah menentukan apakah Pak Lurah bisa membuat tiga hadiah berbeda yang semuanya bukan kelipatan 3, dengan jumlah total $n$.

Soal 4. BENAR atau SALAH: Jika $n = 9$ maka Sedekah Desa Tiga Warna dapat dilakukan.

Soal 5. Jika $n = 11$, tentukan ada berapa banyak cara membagikan Sedekah Tiga Warna kepada 3 warga yang sudah ditentukan Pak Lurah?

Soal 6. Jika nilai $n = 30$, tentukan ada berapa banyak cara membagikan Sedekah Tiga Warna kepada 3 warga yang sudah ditentukan Pak Lurah?

Latihan 6§

Soal 1–3. Liga Faktor Nusantara

Di Indonesia, Liga Faktor Nusantara dikenal sebagai liga yang paling unik. Selain kekuatan pemain dan strategi pelatih, ada satu hal aneh yang selalu dilakukan oleh Komite Liga sebelum kompetisi dimulai, mereka menentukan Nomor Tanpa Buntut $N$. Nomor Tanpa Buntut inilah yang akan memengaruhi jadwal pertandingan, format grup, dan distribusi hadiah.

Tidak ada yang tahu pasti bagaimana Nomor Tanpa Buntut bekerja dalam sistem tanding, tapi rumor mengatakan, bahwa semakin banyak faktor dari angka tertentu, semakin besar kemungkinan grup itu mendapatkan jadwal yang menguntungkan.

Oleh Karena itu, Komite Liga boleh memilih sebuah angka $K$ yang merupakan pembagi dari $N$, dengan syarat sebagai berikut.

Alasan teknisnya hanya dipahami oleh matematikawan liga, tetapi para suporter percaya, semakin banyak faktor $M$, makin fleksibel jadwal pertandingan.

Soal 1. Jika diberikan $N = 12$ tentukan nilai $M$.

Soal 2. Jika diperbolehkan untuk memilih lebih dari satu nilai $M$, maka ada berapa banyak nilai $M$ yang memenuhi jika diberikan nilai $N = 210$?

Soal 3. Diberikan nilai $N = 10!$, tentukan banyaknya faktor dari $M$.

Soal 4–6. Pak Dengklek dan Papan Tulis Ajaib

Pada SMA Harapan Bangsa, ada seorang guru Matematika terkenal bernama Pak Dengklek. Pak Dengklek memiliki sebuah papan tulis ajaib yang bisa memanipulasi angka-angka yang tertulis padanya dengan cara yang tidak biasa.

Pada suatu hari, Pak Dengklek menuliskan $n$ bilangan positif di papan tulis

$$A = [A_1, A_2, \dots, A_n],$$

di mana setiap angka berada dalam rentang $1$ sampai $n$.

Pak Dengklek ingin membuat papan tulis itu memiliki tingkat keindahan setinggi mungkin. Tingkat keindahan adalah faktor persekutuan terbesar (FPB) yang dapat membagi semua angka yang tersisa di papan tulis.

Agar siswanya paham konsep FPB secara mendalam, Pak Dengklek memperbolehkan dua jenis operasi sebagai berikut.

  1. Operasi Hapus
    • Pak Dengklek memilih satu angka dari papan tulis dan menghapusnya.
    • Operasi ini hanya boleh dilakukan maksimal $k$ kali.
    • Jika ada angka kembar, menghapus satu angka hanya menghapus satu di antara mereka.
  2. Operasi Pecah
    • Jika ada angka $x$ $(x \geq 3)$ di papan tulis, Pak Dengklek dapat memecahnya menjadi tiga angka positif $a$, $b$, dan $c$, dengan syarat $a + b + c = x$ dan $1 \leq a \leq b \leq c$.
    • Angka $x$ dihapus dari papan tulis.
    • Hanya $a$ dan $c$ yang ditulis kembali.
    • Sementara $b$ dibuang.
    • Operasi ini boleh dilakukan sebanyak mungkin.

Sebagai siswa terbaik di kelas, kamu diminta oleh Pak Dengklek untuk membantu menentukan, Berapa nilai maksimum tingkat keindahan yang dapat dicapai dari angka-angka yang tersisa di papan tulis setelah melakukan paling banyak $k$ operasi hapus dan beberapa operasi pecah.

Soal 4. Jika dipapan tulis terdapat bilangan $A = [4, 9, 6, 8, 2, 6, 7, 8, 2]$, dan diberikan nilai $k = 1$, tentukan maksimum tingkat keindahan yang mungkin.

Soal 5. Jika dipapan tulis terdapat bilangan $A = [4, 9, 6, 8, 2, 6, 7, 8, 2, 7]$, dan diberikan nilai $k = 1$, tentukan maksimum tingkat keindahan yang mungkin.

Soal 6. Jika dipapan tulis terdapat bilangan

$$ A = [14, 12, 7, 12, 9, 9, 12, 4, 3, 1, 3, 6, 9, 13] $$

dan diberikan nilai $k = 3$, tentukan maksimum tingkat keindahan yang mungkin.

Latihan 7§

Soal 1–3. Pak Alam dan Masalah di Asrama PKU

Pak Alam adalah kepala asrama PKU di Sekolah Sains Amatir yang memiliki asrama dengan $n$ kamar. Setiap kamar ditempati oleh tepat satu siswa. Kumpulan kamar tersebut berbentuk pohon dan saling terhubung dengan kamar lainnya yang bersebelahan secara langsung.

Malam ini, ada tiga tipe siswa di asrama, yaitu

Nantinya Anda akan diberikan string $S$ dengan $n$ karakter di mana $S_i$ melambangkan tipe siswa pada kamar ke-$i$ yang berupa karakter $\mathtt{P}$, $\mathtt{S}$, atau $\mathtt{C}$.

Awalnya, semua dinding antar kamar merupakan dinding tipis, sehingga suara musik melewati semua kamar. Jadi, jika ada siswa yang berpesta dan memutar musik, semua siswa di asrama bisa mendengarnya.

Namun, Pak Alam bisa memasang dinding tebal di antara beberapa kamar. Dinding tebal ini akan menghalangi suara musik melewati batas tersebut.

Anda akan diberikan larik $A$ dengan panjang $n - 1$ yakni $[A_2, A_3, A_4, \dots, A_n]$, di mana $A_i$ menunjukkan bahwa kamar ke-$i$ terhubung langsung dengan kamar $A_i$.

Sebagai contoh jika diberikan larik dengan panjang $2$: $A = [1, 1]$; artinya di sana terdapat 3 kamar dengan

Pak Alam ingin memasang jumlah minimum dinding tebal sehingga setiap siswa yang berpesta dapat memutar musiknya tanpa mengganggu siswa yang ingin tidur.

Soal 1. Jika diberikan $n = 3$, $S = \mathtt{CSP}$, dan $A = [1, 1]$. Tentukan banyaknya sekat minimum yang diperlukan agar yang memutar musik tidak mengganggu siswa lainnya.

Soal 2. Jika diberikan $n = 8$, $S = \mathtt{CSPSPSPC}$, dan $A = [1, 1, 2, 2, 4, 4, 4]$. Tentukan banyaknya sekat minimum yang diperlukan agar yang memutar musik tidak mengganggu siswa lainnya.

Soal 3. Jika diberikan $n = 15$, $S = \mathtt{CSPSPSPCSPPPPSC}$, dan

$$ A = [1, 1, 2, 2, 4, 4, 4, 3, 3, 3, 7, 10, 7, 10]. $$

Tentukan banyaknya sekat minimum yang diperlukan agar yang memutar musik tidak mengganggu siswa lainnya.

Soal 4–6. Membangun Candi

Di sebuah kerajaan kuno, para arsitek sedang membangun sebuah candi megah di atas tanah dengan luas yang tak terbatas. Mereka menggunakan cetakan batu berbentuk persegi berukuran $m \times m$ untuk menyusun struktur candi.

Awalnya, cetakan batu pertama diletakkan di sudut kiri bawah tanah pembangunan, yaitu sudut kiri bawah cetakan batu diletakkan di titik $(0, 0)$. Para arsitek telah merancang sebuah rencana pembangunan yang terdiri dari $n$ langkah. Rencana pembangunan ini akan direpresentasikan dalam sebuah larik $Q$ dengan panjang $n$.

Setiap langkah ke-$i$ dilakukan sebagai berikut.

Geser cetakan batu sejauh $x_i$ unit ke kanan dan $y_i$ unit ke atas dari titik sebelumnya. Tempelkan cetakan batu pada posisi saat ini, menambahkan bagian baru pada struktur candi.

Perlu diperhatikan bahwa semua perpindahan memiliki batasan khusus, yakni $1 \leq x_i, y_i \leq m - 1$. Hal ini agar candi tersebut dapat terhubung dengan baik.

Setelah semua langkah dilakukan, bentuk akhir dari candi yang terbentuk akan menjadi satu kesatuan yang terhubung.

Sebagai contoh jika diberikan $m = 3$, $n =4$, dan $Q = [(1, 1), (2, 2), (2, 1), (1, 2)]$, akan diperoleh struktur bangunan candi seperti gambar pada Soal 4.

Soal 4. Tentukan keliling dari kerangka candi pada gambar berikut.

Soal 4

Soal 5. Diberikan $m = 10$, $n = 4$, dan $Q = [(1,1), (2,2), (3,3), (4,4)]$. Tentukan keliling dari kerangka candi yang terbentuk.

Soal 6. Diberikan $m = 11$, $n = 10$, dan

$$ Q = [(1, 10), (2, 9), (3, 8), (4, 7), \dots, (10, 1)]. $$

Tentukan keliling dari kerangka candi yang terbentuk.

Soal 7–9. Rahasia

Perhatikan kode berikut.

#include 
using namespace std;

void rahasia(int angka, vector& hasil)
{
    if (angka < 0) {
        hasil.push_back('P');
        rahasia(-angka, hasil);
    } else if (angka > 1) {
        rahasia(angka / 2, hasil);
        hasil.push_back((angka % 2) ? 'O' : 'R');
    } else {
        hasil.push_back('N'); // perhatikan baris ini
    }
}

void tampil(const vector& hasil)
{
    for (char c : hasil) {
        cout << c;
    }
    
    cout << endl;
}

int main()
{
    int n;
    cin >> n;
    
    vector hasil;
    
    rahasia(n, hasil);
    tampil(hasil);
}

Soal 7. Apa yang akan dicetak jika diberikan masukan 10.

Soal 8. Jika hasil.push_back('N'); pada baris ke-13 diubah menjadi hasil.push_back('N' + angka);, tentukan apa yang dicetak jika diberikan masukan -21.

Soal 9. Tentukan bilangan bulat terkecil yang dapat jadikan masukan agar mengeluarkan tepat 10 buah karakter yang dicetak.

Latihan 8§

Soal 1–3. Wowogi dan Makan Siang Bergizi Gratis yang Rumit

Wowogi sedang mengadakan program makan siang bergizi gratis untuk anak-anak di sekolah. Ada $N$ siswa yang datang satu per satu ke kantin untuk mengambil makanan. Kita menomori siswa-siswa ini dari $1$ sampai $N$ berdasarkan urutan kedatangan mereka.

Di kantin, para siswa duduk berbaris di meja panjang tanpa ada celah kosong di antara mereka. Saat siswa ke-$i$ tiba, dia harus duduk tepat di sebelah kanan siswa bernomor $A_i$. Jika $A_i = 0$, berarti ia duduk di ujung paling kiri barisan.

Namun, ada masalah. Karena siswa harus duduk bersebelahan tanpa celah, ketika seorang siswa baru ingin duduk, harus ada tempat duduk yang dibuat. Ini bisa dilakukan dengan

Wowogi ingin tahu, berapa banyak pergeseran tempat duduk minimum yang dibutuhkan agar semua siswa bisa duduk dengan benar tanpa ada celah kosong.

Sebagai contoh jika ada 5 orang dan $A = [0, 1, 2, 1, 4]$.

Sehingga barisan kursi 5 orang ini diperoleh dengan 3 langkah minimum.

Soal 1. Jika terdapat sebanyak 5 orang dengan diberikan urutan $A = [0, 0, 0, 0, 0]$, tentukan berapa banyak pergeseran tempat duduk minimum yang dibutuhkan agar semua siswa bisa duduk.

Soal 2. Jika terdapat sebanyak 8 orang dengan diberikan urutan $A = [0, 1, 2, 0, 1, 2, 0, 2]$, tentukan berapa banyak pergeseran tempat duduk minimum yang dibutuhkan agar semua siswa bisa duduk.

Soal 3. Jika terdapat sebanyak 10 orang dengan $A_1 = 0$ dan nilai $A_i$ adalah faktor positif terbesar $i$ yang bukan $i$. Tentukan berapa banyak pergeseran tempat duduk minimum yang dibutuhkan agar semua siswa bisa duduk.

Soal 4–6. Seekor Katak di Rawa

Di sebuah rawa yang luas, hiduplah seekor katak petualang bernama Takak. Takak bukanlah katak biasa, ia sangat mahir melompat dan menaklukkan berbagai rintangan di lingkungannya.

Suatu hari, Takak bertekad untuk mencapai permukaan daun tertinggi di rawa tersebut. Namun, ia tidak ingin menggunakan jalur biasa, melainkan ingin menguji kemampuannya dengan melompat langsung dari satu daun ke daun lainnya.

Takak menemukan sebuah batang terendam yang menjulang ke atas, membentuk struktur persegi panjang yang terdiri dari n tingkat horizontal. Setiap tingkat memiliki m segmen, yang beberapa di antaranya memiliki daun tempat Takak dapat mendarat. Daun-daun ini akan menjadi tempat beristirahatnya dalam perjalanan mendaki rawa.

Sebagai katak yang cerdas, Takak ingin menghitung jumlah rute yang dapat ia gunakan untuk mencapai daun tertinggi. Sebuah rute dianggap sah jika memenuhi syarat berikut.

Jarak antara dua daun bertitik $(i_1, j_1)$ dan $(i_2, j_2)$ diukur menggunakan rumus

$$ \sqrt{(i_1 - i_2 )^2 + (j_1 - j_2 )^2}. $$

Tugasmu adalah menghitung jumlah rute unik yang dapat diambil Takak untuk mencapai tujuan. Dua rute dianggap berbeda jika terdapat perbedaan dalam daftar daun yang digunakan atau urutan lompatan yang dilakukan.

Soal 4. Jika $\mathtt{O}$ adalah representasi daun dan $\mathtt{X}$ bukan daun, tentukan banyaknya kemungkinan jumlah daun yang mungkin dilompati Takak jika Takak memiliki kemampuan meloncat sejauh $d = 2$ dan diberikan rute daun berukuran $3 \times 4$ sebagai berikut.

$$ \begin{gather*} \mathtt{OXOX} \\ \mathtt{XOXO} \\ \mathtt {OXOX} \end{gather*} $$

Soal 5. Dengan berlatih, kemampuan meloncat Takak bisa bertambah, sekarang ia memiliki kemampuan meloncat sejauh $d = 5$. Jika diberikan rute seperti soal sebelumnya, maka berapa kemungkinan rute unik yang dapat diambil Takak untuk mencapai tujuan?

Saol 6. Dengan bertambahnya usia kemampuan Takak yang sebelumnya bisa meloncat sejauh 5, sekarang kemampuannya menjadi hanya sebesar 2 kembali. Tentukan berapa kemungkinan rute unik yang dapat diambil Takak untuk mencapai tujuan.

Soal 7–9: ZZ-ABC

#include 
using namespace std;

char D[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
const int SIZE = 7;

void swap(int a, int b)
{
    char tmp = D[a];
    D[a] = D[b];
    D[b] = tmp;
}

void printArray()
{
    for (int i = 0; i < SIZE; i++) {
        cout << D[i];
    }
    
    cout << endl;
}

void ZZ(int m)
{
    if (m <= 0) {
        printArray();
    } else {
        ZZ(m - 1);
        
        for (int i = m - 2; i >= 0; i--) {
            swap(i, m - 1);
            ZZ(m - 1);
            swap(i, m - 1);
        }
    }
}

Soal 7. Pada pemanggilan ZZ(3), berapa kali fungsi printArray() akan dipanggil?

Soal 8. Pada pemanggilan ZZ(3), apakah yang akan tercetak pada baris ketiga dari pemanggilan tersebut?

Soal 9. Misalkan ZZ(7) dijalankan di suatu komputer yang sudah cukup sepuh selama 1 detik, kira-kira berapa lama ZZ(10) dijalankan?

Latihan 9§

Soal 1–3. Revolusi Angka Volodya

Di sebuah kerajaan angka yang jauh di ujung bilangan, tinggallah seorang pemuda bernama Volodya. Volodya bukan orang biasa. Ia dikenal sebagai pemikir nyeleneh, seorang nonkonformis. Ia merasa dunia telah terlalu lama hidup di bawah aturan kuno. Urutan bilangan asli!

“Kenapa harus 1, 2, 3, 4, 5, …?” gerutu Volodya suatu pagi sambil memandangi barisan bilangan di buku aritmatikanya.

“Kenapa harus genap dan ganjil bercampur seperti itu? Ini tidak estetik! Tidak berjiwa!”

Dengan semangat revolusi, Volodya mengumumkan sebuah reformasi besar-besaran.

“Mulai hari ini, aku akan menyusun ulang urutan bilangan asli! Dunia harus tahu bahwa keadilan numerik dimulai dari estetika!” Dan dimulailah revolusi angka Volodya.

Volodya mengeluarkan aturan penyusunan baru.

Sebagai contoh, jika $n = 10$, maka barisannya menjadi

$$ 1, 3, 5, 7, 9, 2, 4, 6, 8, 10. $$

Keren? Volodya merasa ini adalah mahakaryanya.

Namun, dunia tidak hanya butuh keindahan, dunia butuh jawaban.

Rakyat mulai bertanya kepada Velodya terkait dengan bilangan yang ia gunakan. Volodya memikirkan ini dengan serius. Sebagai orang jenius, bantulah Velodya menjawab pertanyaan rakyat!

Soal 1. BENAR atau SALAH: Dalam aturan Velodya, terdapat barisan bilangan sebagai berikut.

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

Soal 2. Jika terdapat sebanyak 100 buah bilangan, bilangan berapakah yang tertulis dalam barisan Velodya pada urutan ke-78?

Soal 3. Jika terdapat sebanyak 100 buah bilangan pada barisan Velodya, maka tentukan total selisih pada masing masing urutan yang ditulis oleh Velodya dengan bilangan asli yang sudah kita kenal.

Soal 4–6. Bineron Galaxy

Di galaksi jauh, terdapat planet Bineron yang dihuni oleh makhluk-makhluk digital. Setiap tahun, mereka mengadakan seleksi untuk memilih Pemimpin Kode, sosok yang diyakini mampu membaca pola biner dan mengambil keputusan dalam sekejap.

Untuk itu, para kandidat harus menjalani ujian dari Oracle Binaris, sistem kecerdasan kuno yang menguji melalui papan biner rahasia. Papan ini awalnya diisi oleh kode utama, yaitu sebuah string biner$^\dagger$ $s$ sepanjang $n$.

Lalu, Oracle membuat $n$ versi modifikasi dari kode tersebut: masing-masing dibuat dengan membalik tepat satu bit dari posisi yang berbeda, satu per baris. Setiap modifikasi akan menguji kemampuan kandidat dalam mengenali pola perubahan dan menganalisis efek dari satu perubahan kecil. Setiap modifikasi akan disimpan pada larik $A$.

Contohnya jika $s = \mathtt{101}$, maka $A = [\mathtt{001}, \mathtt{111}, \mathtt{100}]$.

$^\dagger$string biner adalah string yang hanya berisi $\mathtt{1}$ atau $\mathtt{0}$.

Soal 4. Jika diberikan $s = \mathtt{0011}$, tentukan banyaknya $\mathtt{1}$ yang muncul pada larik $A$.

Soal 5. Jika diberikan $s = \mathtt{10101010}$, tentukan banyaknya $\mathtt{1}$ yang muncul pada larik $A$.

Soal 5. Jika diberikan $s$ adalah digit biner dari angka $2025$, tentukan banyaknya angka $\mathtt{1}$ yang muncul pada larik $A$.

Soal 7–9. Proses

Perhatikan potongan program di bawah.

int proses(int a) {
    int b = 4;

    while (a > 0) {
        b += a % 10;
        a /= 10;
    }

    return a + b;
}

Soal 7. Tentukan hasil dari pemanggilan proses(142).

Soal 8. Manakah dari masukan berikut yang menghasilkan keluaran dapat dibagi oleh $9$?

Soal 9. Tentukan bilangan terkecil yang lebih besar dari $2025$ sehingga hasilnya adalah bilangan paling kecil yang mungkin.

Latihan 16§

Soal 1–3. Kalender Suku Ayam

Di sebuah daerah pegunungan, hiduplah Suku Ayam, sebuah suku yang memiliki sistem penanggalan unik. Mereka menggunakan Kalender Suku Ayam yang berputar setiap 1024 hari. Setiap hari diberi nomor dari $0$ sampai $1023$.

Hari bernomor $0$ disebut Hari Istirahat Ayam, yaitu hari libur besar di mana seluruh ayam tidak boleh bekerja, selain itu juga ada beberapa hari libur besar hanya saja sebagian saja yang mungkin mengetahuinya.

Hari dengan nomor lain adalah hari biasa.

Suatu hari, batu kalender suku ini bergeser dan beberapa hari menunjukkan angka yang keliru.

Tetua Suku Ayam meminta bantuan untuk menjadikan beberapa hari tersebut menjadi Hari Istirahat Ayam yaitu mengubahnya menjadi $0$.

Namun, batu kalender hanya bisa diubah dengan dua ritual khusus. Misal saat ini kalender menunjukkan angka $k$.

Semua perhitungan selalu dilakukan modulo 1024 karena kalender pada suku ayam ini hanya memiliki angka mulai dari $0$ hingga $1023$.

Soal 1. Jika sebuah tanggal menunjukkan angka $15$, berapa kali ritual khusus minimal yang diperlukan agar tanggal tersebut menjadi Hari Istirahat Ayam?

Soal 2. Diberikan beberapa tanggal berikut, tentukan manakah tanggal yang paling sedikit memerlukan ritual sehingga tanggal yang diberikan menjadi Hari Istirahat Ayam!

Soal 3. Jika $x$ adalah nilai terbesar dari semua angka yang memerlukan jumlah langkah paling sedikit untuk mencapai Hari Istirahat Ayam, maka berapakah nilai $x$?

Soal 4–6. Lampu Gedung Kota

Aan tinggal di sebuah kota kecil yang hanya memiliki satu jalan utama yang sangat panjang.

Di sepanjang jalan itu terdapat gedung yang berdiri berjajar dari kiri ke kanan. Setiap gedung memiliki lampu hias di atapnya. Tinggi gedung menentukan seberapa terang lampu terlihat dari kejauhan.

Aan mendapat tugas dari wali kota untuk membuat kota tampak lebih indah saat malam hari. Sebuah gedung disebut gedung sorotan utama jika

Gedung seperti ini terlihat menonjol di antara dua tetangganya dan membuat jalan kota tampak hidup. Aan boleh menaikkan tinggi lampu di beberapa gedung dengan cara menambahkan lantai di beberapa gedung. Menambah tinggi Gedung tentunya memerlukan biaya, jadi Aan tidak ingin berlebihan. Membuat jumlah gedung sorotan utama sebanyak mungkin, namun wali kota menginginkan banyak Gedung sorotan utama banyaknya semaksimal mungkin yang bisa.

Soal 4. Jika terdapat 100 gedung maka maksimal akan ada berapa banyak Gedung sorotan utama yang dapat dibuat.

Soal 5. Berapa jumlah minimum total banyaknya lantai yang harus ditambahkan agar jumlah gedung sorotan utama menjadi maksimal pada rangkaian 8 gedung dengan ketinggian berturut-turut $[4, 2, 1, 3, 5, 3, 6, 1]$.

Soal 6. Berapa jumlah minimum total banyaknya lantai yang harus ditambahkan agar jumlah gedung sorotan utama menjadi maksimal pada rangkaian 32 gedung dengan ketinggian berturut-turut

$$ [3, 5, 2, 3, 4, 5, 8, 3, 6, 2, 1, 4, 6, 7, 3, 6, 7, 9, 3, 7, 3, 5, 3, 1, 4, 5, 1, 3, 1, 4, 2, 2]. $$

Soal 7–9. Mencari $N$

Perhatikan kode berikut.

int mencari(int N) {
    int hasil = 0;
    
    for (int i = 1; i <= N; i++) {
        int j = 1, z = 0;
        
        while (j <= i) {
            if (i % j == 0)
                z++;
            
            j++;
        }
        
        if (z % 2 != 0)
            hasil++;
    }
    
    return hasil;
}

Soal 7. Berapakah nilai yang dihasilkan dari pemanggilan $\mathtt{mencari}(10)$?

Soal 8. Berapakah nilai yang dihasilkan dari pemanggilan $\mathtt{mencari}(2026)$?

Soal 9. Jika hasil dari pemanggilan $\mathtt{mencari}(N) - \mathtt{mencari}(M) = 2026$ dan $1 \leq M \leq 10$, tentukan nilai $N - M$ terbesar yang mungkin.

Latihan 17§

Soal 1–3. Jaringan Folder Rahasia

Di sebuah komputer milik lembaga riset, terdapat sistem folder rahasia. Struktur folder ini berbentuk pohon (tree).

Setiap folder hanya punya satu folder induk (kecuali folder utama yang tidak memiliki folder induk). Tidak ada folder yang terhubung membentuk siklus.

Seorang teknisi keamanan bernama Bebras ingin memetakan seluruh folder untuk keperluan audit sandi. Namun, sistem komputer ini memiliki keterbatasan unik. Bebras memiliki daftar koneksi folder (misalnya: folder $A$ terhubung langsung ke folder $B$). Daftar ini disimpan dalam urutan tertentu.

Sistem bekerja seperti berikut.

Setiap kali sistem memindai seluruh daftar koneksi dari awal sampai akhir, itu disebut satu kali pemindaian.

Soal 1. Berapa kali sistem memindai 3 koneksi folder berikut?

Soal 2. Berapa kali sistem memindai 5 koneksi folder berikut?

Soal 3. Berapa kali sistem memindai 20 koneksi folder berikut? Tuliskan $-1$ jika tidak mungkin.

Soal 4–6. Kibor Sempurna

Polycarp ingin membuat keyboard satu baris yang berisi semua huruf ‘a’ sampai ‘z’ tepat sekali masing-masing. Ia juga punya sebuah kata sandi $s$ yang selalu ia gunakan. Agar mengetik kata sandi itu mudah, setiap dua huruf yang bersebelahan dalam $s$ harus bersebelahan juga pada keyboard yang dibuat. Tidak ada dua huruf sama yang bersebelahan di $s$.

Contoh, jika $s = \mathtt{abacaba}$, maka keyboard

$$ \mathtt{c a b d e f g h i j k l m n o p q r s t u v w x y z} $$

valid karena

Soal 4. BENAR atau SALAH: Ada suatu keyboard yang memudahkan sandi $s = \mathtt{abcda}$.

Soal 5. BENAR atau SALAH: Ada suatu keyboard yang memudahkan sandi $s = \mathtt{adadapururtekismsikekism}$.

Soal 6. Berapa banyak keyboard yang memudahkan sandi $s = \mathtt{adadabcefghijklmnop}$ dan string $\mathtt{rstuvw}$.

Soal 7–9. Peternakan

Perhatikan potongan kode berikut.

int hitungKandang(int ayam, int bebek) {
    int kambing = 1, sapi = ayam;
    
    while (sapi > bebek) {
        kambing *= sapi;
        --sapi;
    }
    
    int kuda = ayam - bebek;
    
    while (kuda > 1) {
        kambing /= kuda;
        --kuda;
    }
    
    return kambing;
}
 
int hitungBanyakKandang(int ayam, int bebek, int itik) {
    int totalDomba = 0;
    int domba = bebek;
    
    while (domba <= itik) {
        totalDomba += hitungKandang(ayam, domba);
        ++domba;
    }
    
    return totalDomba;
}

Soal 7. Tentukan hasil dari pemanggilan $\mathtt{hitungKandang}(10, 2)$.

Soal 8. Tentukan hasil dari pemanggilan $\mathtt{hitungBanyakKandang}(6, 2, 4)$.

Soal 8. Tentukan hasil dari pemanggilan $\mathtt{hitungBanyakKandang}(11, 2, 9)$.

Latihan 18§

Soal 1–3. Formasi Energi di Dunia Kultivasi

Di dunia kultivasi, Tianxuan, terdapat $N$ kultivator yang sedang mengikuti Ujian Formasi Energi. Setiap kultivator berdiri di atas pilar qi, dan tiap pilar memiliki tingkat energi tertentu. Semakin tinggi angkanya, semakin kuat energi qi-nya.

Para kultivator ingin membentuk ikatan qi antar sesama untuk memperkuat formasi. Namun, Ketua Sekte memberi peringatan keras yaitu tidak boleh ada tiga kultivator berbeda $A$, $B$, dan $C$ dengan tingkat energi $A \leq B \leq C$, sehingga $A$ terikat qi dengan $B$ dan $B$ terikat qi dengan $C$. Menurut kitab kuno, susunan seperti itu akan menciptakan “Aliran Qi Bertingkat” yang membuat formasi meledak.

Soal 1. Jika terdapat 4 kultivator dengan tingkat energi 2, 3, 1, dan 2, maka maksimal hanya akan terdapat sebanyak 3 ikatan qi yang mungkin. Tentukan ada berapa banyak formasi yang dapat dibentuk.

Soal 2. Jika terdapat 12 kultivator dengan tingkat energi 7, 2, 4, 9, 1, 4, 6, 3, 7, 4, 2, dan 3, tentukan banyaknya ikatan qi maksimal yang mungkin dibentuk.

Soal 3. Tentukan banyaknya kultivator minimal agar minimal terdapat sebanyak 2026 ikatan qi yang terbentuk!

Soal 4–6. Legenda Pohon Hitam Kerajaan Daiyu

Di Kerajaan Daiyu, terdapat sebuah pohon suci, Namun karena kutukan kuno, semua desa yang terletak di simpul pada pohon itu awalnya berwarna hitam. Para Ketua Sekte ingin memurnikan pohon tersebut, sehingga seluruh desa berubah menjadi putih kembali.

Untuk melakukan pemurnian, Ketua hanya mengizinkan satu jenis ritual khusus. Dalam satu ritual, kamu boleh:

Jarak antara dua desa adalah jumlah jalan terpendek di antara keduanya. Desa yang sudah putih tetap putih jika terkena ritual lagi. Tugasmu adadalam menentukan Banyaknya ritual sesedikit mungkin agar seluruh desa di pohon berubah menjadi putih.

Soal 4. Pohon Suci tersebut berada di desa 1. Desa-desa terhubung dengan keterangan berikut.

Tentukan banyaknya ritual minimal agar semua desa menjadi berwarna putih.

Soal 5. Ada 7 desa dengan keterhubungan sebagai berikut.

Tentukan ritual minimal yang diperlukan agar semua desa menjadi desa putih.

Soal 6. Jika terdapat 20 desa dengan keterhubungan sebagai berikut.

Untuk baris ke-$i$ pada tabel di bawah menyatakan bahwa $a_i$ terhubung dengan $b_i$.

$a_i$ $b_i$
8 14
1 4
10 15
6 12
4 8
2 6
1 3
9 16
5 11
4 5
12 18
3 7
7 13
6 10
10 17
11 19
2 20
1 2
14 16

Tentukan berapa banyak ritual khusus yang diperlukan untuk membuat semua desa menjadi desa putih!

Soal 7–8. Makan Ayam Goreng

Perhatikan potongan kode berikut.

int ayam = 0;

void Makan(int n, int m) {
    ayam++;
    
    int goreng;
    
    if (n < m) {
        cout << "Enak" << endl;
        
        goreng = (m + n) / 2;
        
        Makan(n, goreng);
        Makan(goreng + 1, m);
    } else {
        cout << "Enak" << endl;
    }
}

int kecap(int zzz){
    for (int i = 0; i <= zzz; i++)
        Makan (1, i);
    
    return ayam;
}

Soal 7. Jika dipanggil $\mathtt{Makan}(1, 10)$, maka akan ada berapa buah baris yang tercetak?

Soal 8. Tentukan nilai $n$ terkecil agar $\mathtt{kecap}(n) > 1000$.