Pembahasan OSN-P (KSN-P) 2021 (Informatika)

Written by: 

• Christoffer Edbert Karuniawan (Chrisedyong)

• Jiriki Joeng (kizu)

Reviewed by: 

• Leonardo Dahendra (Drakozs)

*warna berdasarkan max rating Codeforces per Jul 2025

Akses soalnya di: https://osn.toki.id/data/KSNP2021.pdf 

Bagian A: Analitika & Logika 

A1. 67305

Angka x akan masuk ke dalam barisan jika dan hanya jika x mod 100 = 1 atau x mod 100 = 5 atau x mod 100 = 25. Oleh karena itu, buat mencari bilangan ke 2021, angka selain 2 digit terakhir dapat diperoleh dengan floor(2021/3) = 673. 2 digit terakhir dapat diperoleh dengan 2021 mod 3 yaitu bilangan ke 2 (05). Jadi bilangan ke 2021 adalah 67305.

A2. 15

IPA = 20

IPA saja = 5

IPS = 25

IPS saja = 6

Matematika = 30

Matematika saja = 7

Informatika = 35

Informatika saja = 8

IPA ∩ IPS = 0

Mengikuti 3 lomba sekaligus = 14

Apabila dibuat diagram Venn, berbentuk seperti ini

IPA = 20

a + b + c + 5 = 20

a + b + c = 15 ...(1)

IPS = 25

e + f + g + 6 = 25

e + f + g = 19 ...(2)

MATEMATIKA = 30

a + b + d + e + f + 7 = 30

a + b + d + e + f = 23 ...(3)

INFORMATIKA = 35

b + c + d + f + g + 8 = 35

b + c + d + f + g = 27 ...(4)

3 lomba sekaligus = 14

b + f = 14 ...(5)

Ditanya: b + d + f

Buat persamaan dari (3) + (4) - (1) - (2)

b + 2d + f = 16 ...(6)

Buat persamaan dari (6) - (5)

2d = 2

d = 1 ... (7)

Buat persamaan dari (5) + (7)

b + d + f = 15

A3. ABDE

Untuk mempermudah penulisan, anggap saja nilai 1 adalah jujur, nilai 0 adalah bohong.

A ≠ C

B = A

C = 3 orang di antara kami bohong

D = 4 orang di antara kami jujur

E ≠ F

F ≠ D

Jika A = 1:
C = 0 (karena pernyataan 1)

B = 1 (karena pernyataan 2)

Jika D = 1:

F = 0 (karena pernyataan 6)

E = 1 (karena pernyataan 5)

Pernyataan 3 bernilai benar karena C bohong

Pernyataan 4 juga bernilai benar karena D jujur

Maka jawaban adalah ABDE. Mari kita cek apakah mungkin soal ini memiliki lebih dari 1 jawaban.

Jika D = 0:

F = 1 (karena pernyataan 6)

E = 0 (karena pernyataan 5)

Pernyataan 3 bernilai salah karena C jujur (kontradiksi)

Jika A = 0:

C = 1 (karena pernyataan 1)

B = 0 (karena pernyataan 2)

Jika D = 1:

F = 0 (karena pernyataan 6)

E = 1 (karena pernyataan 5)

Pernyataan 3 bernilai benar karena C jujur

Pernyataan 4 bernilai salah karena D bohong (kontradiksi)

Jika D = 0:

F = 1 (karena pernyataan 6)

E = 0 (karena pernyataan 5)

Pernyataan 3 bernilai salah karena C bohong (kontradiksi)

Jadi setelah di cek, hanya ada 1 kemungkinan yaitu ABDE yang jujur.

A4. 14580

Untuk bola pertama ada 5 cara untuk mewarnai

Untuk bola kedua karena harus berbeda dengan bola pertama jadi ada 4 cara untuk mewarnai

Untuk bola ketiga hingga kedelapan ada 3 cara untuk mewarnai masing-masing bola karena masing-masing bola harus berbeda dengan 2 bola di sebelah kirinya.

Dengan aturan perkalian didapat, 5 * 4 * 3^6 = 14580

A5. 7

Jika tahun depan ada sebanyak 365 hari, maka hari di tanggal yang sama di tahun depan adalah ditambah sehari dari hari sekarang. Hal ini karena 365 mod 7 adalah 1. Sebagai contoh, 1 September 2021 adalah hari Rabu, maka 1 September 2022 adalah hari Kamis. Namun jika tahun depan ada sebanyak 366 hari, maka hari di tanggal yang sama di tahun depan adalah ditambah 2 hari dari hari sekarang.

Agar tahun kabisat tidak menjadi masalah, kita dapat mengelompokkan setiap 4 tahun saja. Jadi untuk 4 tahun kedepan, hari yang ada di tanggal yang sama dapat diperoleh dengan menambah 5 hari. Dari tahun 2021 menuju tahun 1921 tepat mundur 100 tahun. Untuk setiap 4 tahun selalu ada 1 tahun kabisat karena untuk tahun yang kelipatan 100 (tahun 2000) juga merupakan kelipatan 400. Jadi tepat mundur (100/4) * 5 hari = 125 hari. 125 mod 7 = 6. Jadi tanggal 1 September 1921 adalah hari Rabu dikurangi 6 hari, yaitu hari Kamis. Hari Rabu pertama pastinya dengan menambah 6 hari juga yaitu pada tanggal 7 September 1921.

A6. 11

Solusi paling mudah adalah dengan mencoba satu per satu.

A: FALSE, B: FALSE, C: FALSE, D: FALSE -> FALSE

A: FALSE, B: FALSE, C: FALSE, D: TRUE -> FALSE

A: FALSE, B: FALSE, C: TRUE, D: FALSE -> TRUE

A: FALSE, B: FALSE, C: TRUE, D: TRUE -> TRUE

A: FALSE, B: TRUE, C: FALSE, D: FALSE -> FALSE

A: FALSE, B: TRUE, C: FALSE, D: TRUE -> FALSE

A: FALSE, B: TRUE, C: TRUE, D: FALSE -> TRUE

A: FALSE, B: TRUE, C: TRUE, D: TRUE -> TRUE

A: TRUE, B: FALSE, C: FALSE, D: FALSE -> TRUE

A: TRUE, B: FALSE, C: FALSE, D: TRUE -> TRUE

A: TRUE, B: FALSE, C: TRUE, D: FALSE -> TRUE

A: TRUE, B: FALSE, C: TRUE, D: TRUE -> TRUE

A: TRUE, B: TRUE, C: FALSE, D: FALSE -> FALSE

A: TRUE, B: TRUE, C: FALSE, D: TRUE -> TRUE

A: TRUE, B: TRUE, C: TRUE, D: FALSE -> TRUE

A: TRUE, B: TRUE, C: TRUE, D: TRUE -> TRUE

Jadi ada 11 kombinasi A, B, C, D yang memenuhi logika TRUE

 A7. S

Gunakan strategi Dynamic Programming.

Definisikan DP(S, K) adalah panjang akhir string S setelah kita melakukan transformasi sebanyak K kali. 

Kita bisa menghitung DP("KSNP", 5) lalu melakukan backtracking untuk mencari karakter ke 2021.
Selain itu untuk suatu string kita bisa melakukan pemecahan untuk setiap karakter. Sebagai contoh, DP("KSNP", 5) bisa diubah menjadi DP("K", 5) + DP("S", 5) + DP("N", 5) + DP("P", 5).

Untuk transisi yang ada, kita dapat menggunakan sesuai definisi soal, yaitu sebagai berikut:

• DP("K", i) = DP("K", i-1) + DP("S", i-1) + DP("N", i-1) + DP("K", i-1)

• DP("S", i) = DP("K", i-1) + DP("S", i-1) + DP("N", i-1) + DP("S", i-1)

• DP("N", i) = DP("K", i-1) + DP("S", i-1) + DP("N", i-1)

• DP("P", i) = DP("K", i-1) + DP("S", i-1) + DP("N", i-1) + DP("P", i-1)

Base case dari DP ini adalah DP(S, 0) = 1

Mari kita hitung untuk masing-masing DP. Hasilnya bisa dilihat pada gambar di bawah ini

Untuk mendapatkan jawaban, yaitu karakter ke 2021, kita dapat melakukan backtracking.

Awalnya kita tinjau apakah karakter ke 2021 ada di group DP("K", 5). Ternyata bukan karena nilai dari DP("K", 5) hanya sebanyak 780 jadi kita bisa mengurangkan 2021 dengan 780 yaitu 1241 lalu mencari lagi pada group berikutnya.

Tinjau kembali apakah karakter ke 1241 ada di group DP("S", 5). Ternyata bukan karena nilai dari DP("S", 5) hanya ada sebanyak 780 jadi kita bisa mengurangkan 1241 dengan 780 yaitu 461.

Tinjau apakah karakter ke 461 ada di group DP("N", 5). Ternyata iya karena 461 ≤  DP("N", 5) yaitu 571. Jadi kita melakukan rekursi ke kedalaman berikutnya, yaitu dimulai dari DP("K", 4).

Tinjau apakah karakter ke 461 ada di group DP("K", 4). Ternyata bukan karena nilai dari DP("K", 4) hanya ada sebanyak 209 jadi kita bisa mengurangkan 461 dengan 209 yaitu 252.

Tinjau apakah karakter ke 252 ada di group DP("S", 4). Ternyata bukan karena nilai dari DP("S", 4) hanya ada sebanyak 209 jadi kita bisa mengurangkan 252 dengan 209 yaitu 43.

Tinjau apakah karakter ke 43 ada di group DP("N", 4). Ternyata iya karena 43 ≤ DP("N", 4) yaitu 153. Jadi kita melakukan rekursi ke kedalaman berikutnya, yaitu dimulai dari DP("K", 3).

Tinjau apakah karakter ke 43 ada di group DP("K", 3). Ternyata iya karena 43 ≤  DP("K", 3) yaitu 56. Jadi kita melakukan rekursi ke kedalaman berikutnya, yaitu dimulai dari DP("K", 2).

Tinjau apakah karakter ke 43 ada di group DP("K", 2). Ternyata bukan karena nilai dari DP("K", 2) hanya ada sebanyak 15 jadi kita bisa mengurangkan 43 dengan 15 yaitu 28.

Tinjau apakah karakter ke 28 ada di group DP("S", 2). Ternyata bukan karena nilai dari DP("S", 2) hanya ada sebanyak 15 jadi kita bisa mengurangkan 28 dengan 15 yaitu 13.

Tinjau apakah karakter ke 13 ada di group DP("N", 2). Ternyata bukan karena nilai dari DP("N", 2) hanya ada sebanyak 11 jadi kita bisa mengurangkan 13 dengan 11 yaitu 2.

Akibatnya, karakter ke 2 dipastikan ada di group DP("K", 2). Fakta itu benar karena 2 ≤ DP("K", 2) yaitu 15. Jadi kita melakukan rekursi ke kedalaman berikutnya, yaitu dimulai dari DP("K", 1).

Tinjau apakah karakter ke 2 ada di group DP("K", 1). Ternyata iya karena nilai dari 2 ≤ DP("K", 1) yaitu 4. Jadi kita melakukan rekursi ke kedalam berikutnya, yaitu dimulai dari DP("K", 0).

Tinjau apakah karakter ke 2 ada di group DP("K", 0). Ternyata bukan karena nilai dari DP("K", 0) hanya ada sebanyak 1 jadi kita bisa mengurangkan 2 dengan 1 yaitu 1.

Tinjau apakah karakter ke 1 ada di group DP("S", 0). Ternyata iya yaitu S itu sendiri. Jadi karakter ke 2021 adalah karakter S.

A8. 3

1 warna jelas tidak mungkin karena ada 2 segi enam berimpitan

2 warna juga tidak mungkin karena ada 3 segi enam berimpitan satu sama lain.

Dengan menggunakan 3 warna dapat dibuat, salah satu konfigurasi sebagai berikut

A9. 65

Untuk persegi panjang yang sejajar dengan sumbu x dan sumbu y, dapat dihitung per baris:

Baris 1 dan Baris 2: Ada 3C2 = 3
Baris 1 dan Baris 3: Ada 5C2 = 10
Baris 1 dan Baris 4: Ada 3C2 = 3
Baris 1 dan Baris 5: Ada 5C2 = 10
Baris 2 dan Baris 3: Ada 3C2 = 3
Baris 2 dan Baris 4: Ada 3C2 = 3
Baris 2 dan Baris 5: Ada 3C2 = 3
Baris 3 dan Baris 4: Ada 3C2 = 3
Baris 3 dan Baris 5: Ada 5C2 = 10
Baris 4 dan Baris 5: Ada 3C2 = 3

Kemudian untuk persegi ukuran sqrt(2) yang dirotasi 45 derajat ada sebanyak 5

Persegi ukuran 2 sqrt(2) yang dirotasi 45 derajat ada sebanyak 1

Persegi ukuran sqrt(10) yang tidak sejajar sumbu x ada sebanyak 2

Persegi panjang ukuran 2 sqrt(2) kali sqrt(2) yang tidak sejajar sumbu x dan sumbu y ada sebanyak 4

Persegi panjang ukuran 3 sqrt(2) kali sqrt(2) yang tidak sejajar sumbu x dan sumbu y ada sebanyak 2

Total ada 65 persegi panjang

A10. 20801

Untuk setiap bilangan i yang merupakan kelipatan 100, maka i * i mod M adalah 0. Ada 1001 bilangan (dari 0 hingga 1000) dan ada 11 bilangan yang merupakan kelipatan 100.

Jadi setelah for bagian pertama, A[0] adalah 11 dan untuk semua elemen lain, A[1] + A[2] + ... + A[4999] adalah 1001 - 11 = 990.

Kemudian perhatikan bahwa untuk for di bagian bawah, nilai indeks yang ditambahkan selalu dimodulo dengan nilai i, hal ini menyebabkan indeks yang diperbarui tidak akan berkontribusi ulang untuk menyebabkan penambahan lagi. Perhatikan juga untuk for yang menggunakan variabel j, for ini selalu konstan dilakukan sebanyak 20 kali dari j = 1 hingga j = 2^19. Jadi untuk setiap A[i] dimana 1 ≤ i ≤ 4999, akan berkontribusi menambahkan lagi sebanyak 20 untuk masing-masing.

Hasil penjumlahan semua nilai dapat kita hitung dengan cara 11 + 21 * (1001 - 11) = 11 + 21 * 990 = 20801

Studi Kasus B1: Buah

B1.1. 3

Pak Dengklek membeli 100 apel merah dengan berat 5kg dan 100 apel hijau dengan berat 10kg.

Pak dengklek bisa mengambil 2 apel merah dan 1 apel hijau sehingga masing masing berat apel merah dan apel hijau adalah 10kg.

B1.2. 150

Perhatikan bahwa perbandingan berat antara apel merah dan hijau adalah 5:10 = 1:2.

Setiap 1 apel hijau yang diambil, kita harus mengambil 2 apel merah.

Definisikan x adalah jumlah apel hijau yang diambil, maka apel merah yang diambil adalah 2x.

• Hijau = x <= 100.

• Merah  = 2x <= 100.

Ambil x yang maksimum -> x = 50

Maka Pak Dengklek dapat mengambil 100 apel merah dan 50 apel hijau.

Total = 150

B1.3. 50

Jika kita mengambil x apel hijau, maka kita juga mengambil 2x apel hijau, maka tiap pasangannya adalah (2x, x).

Jumlah apel hijau terbanyak yang dapat diambil (x) adalah 50.

Kita dapat mengambil x = [1, 2, 3, ..., 50].

Jawaban = 50.

Soal Pemrograman

Definisikan

• x = Apel merah yang diambil.

• y = Apel hijau yang diambil.

Kita perlu mencari x + y  minimum yang memenuhi syarat syarat berikut:

• x >= 1 ("minimal harus mengambil satu dari masing-masing jenis apel").

• y >= 1 ("minimal harus mengambil satu dari masing-masing jenis apel").

• Ax = By ("Total berat apel merah harus sama dengan total berat apel hijau").

Definisikan W = total berat optimal yang akan diambil masing-masing apel hijau dan merah.

W = Ax = By

• W merupakan kelipatan dari A

• W merupakan kelipatan dari B

Dapat disimpulkan bahwa W adalah LCM (KPK) dari A dan B.

Subsoal 1:

Karena A dan B relatif prima, maka KPK dari A dan B sudah pasti A * B.

Maka jawabannya adalah = A + B.

Kompleksitas waktu: 

O (1)

#include <bits/stdc++.h>

using namespace std;

int main () {

   int n, a, b;

   cin >> n >> a >> b;

   cout << a + b << '\n' ;

   return 0 ;

}

Solusi penuh:

Jika sudah dapat W, kita dapat dengan mudah mendapatkan x dan y.

W = Ax -> x = W / A

W = By -> y = W / B

x + y minimum = W / A + W / B, dimana W = KPK dari A dan B.

Kompleksitas waktu: O (log min (A, B))

#include <bits/stdc++.h>

using namespace std;

int main () {

   int n, a, b;

   cin >> n >> a >> b;

   long long W = lcm (a, b);

   int jawab = W / a + W / b;

   cout << jawab << '\n' ;

   return 0 ;

}

Studi Kasus B2. Kartu

B2.1. YA

Definisikan x sebagai nomor kartu pertama.

Diketahui x = 7.

Pertanyaan apakah mungkin menjadi {14, 35}.

Simulasikan saja:

• Ronde 1: {7, 0}

• Ronde 2: {7, 7}

• Ronde 3: {14, 7} -> Simpan 14 karena sudah sama dengan kartu yang diinginkan.

• Ronde 4: {14, 21}

• Ronde 5: {14, 35} -> Cocok

Jawaban: YA

B2.2. TIDAK

Definisikan x sebagai nomor kartu pertama.

Diketahui x = 5.

Pertanyaan apakah mungkin menjadi {20, 30}.

Simulasikan saja:

• Ronde 1: {5, 0}

• Ronde 2: {5, 5}

• Ronde 3: {5, 10}

• Ronde 4: {5, 15}

• Ronde 5: {20, 15} -> Simpan 20 karena sudah sama dengan kartu yang diinginkan.

• Ronde 6: {20, 35} -> Tidak cocok, dan karena kedua kartu sudah >= kartu tujuan, kartu tujuan tidak akan tercapai.

Jawaban: TIDAK

B2.3. 6

Definisikan x sebagai nomor kartu pertama.

Observasi: 

Pada setiap langkah mengambil kartu baru (yang merupakan jumlah dari dua kartu di tangan) dan membuang satu kartu, FPB dari semua kartu di tangan tidak akan berubah, dan akan tetap sama dengan nomor kartu pertama (x).

Proof:

1. Awal

Hanya ada satu kartu (x), maka gcd = x.

2. Mengambil kartu baru

Setelah mengambil kartu pertama, kartu ditangan adalah {x, 0}, sehingga kartu barunya adalah 0 + x = x

Sehingga saat ronde 2, kartu yang ditangan merupakan {x, x} dengan FPB (x, x) = x

Sekarang FPB dari kedua kartu kita merupakan x, yang berarti

FPB (a, b) = x.

Kartu baru yang akan diambil bernilai a + b, Gunakan identitas FPB (u, v) = FPB (u, u + v)

Maka 3 kartu yang kita miliki sebelum dibuang adalah a, b, a + b, dimana FPB (a, b, a + b) = FPB (a, b) = x

3. Membuang kartu

FPB (a, b, a + b) = x, jika kita membuang salah satu antara a atau b, hasilnya FPB nya akan tetap sama yaitu x.

Maka dapat disimpulkan bahwa kartu pertama yang dipegang oleh Pak Dengklek (x) adalah FPB dari kedua kartu yang sedang Pak Dengklek pegang sekarang.

Jawaban = FPB (60, 192) = 6

Soal Pemrograman

Solusi penuh:

Definisikan x sebagai nomor kartu pertama.

Observasi: 

Pada setiap langkah mengambil kartu baru (yang merupakan jumlah dari dua kartu di tangan) dan membuang satu kartu, FPB dari semua kartu di tangan tidak akan berubah, dan akan tetap sama dengan nomor kartu pertama (x).

Proof:

1. Awal

Hanya ada satu kartu (x), maka gcd = x.

2. Mengambil kartu baru

Setelah mengambil kartu pertama, kartu ditangan adalah {x, 0}, sehingga kartu barunya adalah 0 + x = x

Sehingga saat ronde 2, kartu yang ditangan merupakan {x, x} dengan FPB (x, x) = x

Sekarang FPB dari kedua kartu kita merupakan x, yang berarti

FPB (a, b) = x.

Kartu baru yang akan diambil bernilai a + b, Gunakan identitas FPB (u, v) = FPB (u, u + v)

Maka 3 kartu yang kita miliki sebelum dibuang adalah a, b, a + b, dimana FPB (a, b, a + b) = FPB (a, b) = x

3. Membuang kartu

FPB (a, b, a + b) = x, jika kita membuang salah satu antara a atau b, hasilnya FPB nya akan tetap sama yaitu x.

Maka dapat disimpulkan bahwa kartu pertama yang dipegang oleh Pak Dengklek (x) adalah FPB dari kedua kartu yang sedang Pak Dengklek pegang sekarang (A, B).

Jawaban = FPB (A, B).

Kompleksitas waktu:

O (log min (A, B))

#include <bits/stdc++.h>

using namespace std;

int main () {

   long long A, B;

   cin >> A >> B;

   cout << __gcd (A, B) << '\n';

   return 0;

}

Studi Kasus B3. Vitamin

B3.1. 34

Bruteforce semua kombinasi yang memungkinkan, yang optimal adalah:

Vitamin D + Vitamin E

Harga = 3 + 4 = 7

Kandungan = 15 + 19 = 34

Jawaban: 34

B3.2. 38

Bruteforce semua kombinasi yang memungkinkan, yang optimal adalah:

Ada 2 konfigurasi yang optimal:

• Vitamin E + Vitamin E

Harga = 4 + 4 = 8

Kandungan = 19 + 19 = 38

• Vitamin B + Vitamin D

Harga = 5 + 3 = 8

Kandungan = 25 + 13 = 38

Jawaban = 38

B3.3. 69

Langkah‑langkah:

1. Coba semua kemungkinan memilih vitamin C, D, E.

2. Untuk setiap kombinasi, hitung total harga dan total kandungan vitamin dosis tinggi. Jika total harga melebihi 15, abaikan kombinasi itu.

3. Dari sisa uang (15 minus total harga vitamin tinggi), beli vitamin A dan B sebanyak mungkin.

   • Karena A dan B dosis rendah, ini adalah masalah “unbounded knapsack” kecil dengan dua item. Kita bisa loop berapa banyak B yang dibeli (0 sampai sisa uang dibagi 5), sisanya diisi A sebanyak mungkin, lalu pilih kombinasi A/B yang memberi kandungan terbesar.

4. Jumlahkan kandungan dosis tinggi dan dosis rendah untuk mendapatkan total kandungan.

5. Pilih kombinasi (subset tinggi + jumlah A/B) yang menghasilkan total kandungan terbesar.

Hasil perhitungan:

• Tanpa vitamin tinggi sama sekali: beli 3 B (3×5=15) → kandungan = 3×23 = 69.

• Ada cara lain juga yang mencapai 69: pilih C dan E (harga 1 + 4 = 5, kandungan 4 + 19 = 23), sisa uang 10, beli 2 B (2 × 23 = 46), total 23 + 46 = 69.

Jawaban = 69

Soal Pemrograman

Subsoal 1:

Pada subsoal ini, dosis dari vitamin sudah pasti tinggi, problem ini sama seperti Dynamic Programming 0/1 Knapsack problem.

Definisi DP:

dp [x] = total kandungan maksimal yang bisa didapatkan dengan uang sebanyak x.

Approach:

Iterasi setiap vitamin

Transisi:

dp [j] = max (dp [j], dp [j - H [i]] + K [i]);

Kompleksitas waktu:

O (N * M)

#include <bits/stdc++.h>

using namespace std;

int main () {

   int N, M;

   cin >> N >> M;

   int H [N], K [N], D [N];

   for (int i = 0 ; i < N ; i ++) {

       cin >> H [i] >> K [i] >> D [i];

   }

   long long dp [M + 1];

   memset (dp, 0, sizeof dp);

   for (int i = 0 ; i < N ; i ++) {

       for (int j = M ; j >= H [i] ; j --) {

           dp [j] = max (dp [j], dp [j - H [i]] + K [i]);

       }

   }

   cout << *max_element (dp, dp + M + 1) << '\n';

   return 0;

}

Solusi penuh:

Problem ini merupakan DP (Dynamic Programming) mixed knapsack problem:

• 0/1 Knapsack untuk vitamin berdosis tinggi.

• Unbounded Knapsack untuk vitamin berdosis rendah.

Definisi DP:

dp [x] = total kandungan maksimal yang bisa didapatkan dengan uang sebanyak x.

Approach:

Iterasi setiap vitamin

Transisi:

dp [j] = max (dp [j], dp [j - H [i]] + K [i]);

Terdapat 2 kasus:

• Kasus 1 Dosis rendah (Di == 0):

Lakukan unbounded knapsack, iterasi j menaik dari H [i] ke M.

Karena transisi dp [j] memanggil dp [j - H [i]], lakukan iterasi menaik agar kita dapat melakukan pengambilan ulang pada j yang lebih besar.

• Kasus 2 Dosis tinggi (Di == 1):

Lakukan 0/1 knapsack, iterasi j menurun dari M ke H [i].

Jawaban terdapat di nilai maksimum dari dp [0 ... M].

Kompleksitas waktu:

O (N * M)

#include <bits/stdc++.h>

using namespace std;

int main () {

   int N, M;

   cin >> N >> M;

   int H [N], K [N], D [N];

   for (int i = 0 ; i < N ; i ++) {

       cin >> H [i] >> K [i] >> D [i];

   }

   long long dp [M + 1];

   memset (dp, 0, sizeof dp);

   for (int i = 0 ; i < N ; i ++) {

       if (D [i] == 0) {

           for (int j = H [i] ; j <= M ; j ++) {

               dp [j] = max (dp [j], dp [j - H [i]] + K [i]);

           }

       } else {

           for (int j = M ; j >= H [i] ; j --) {

               dp [j] = max (dp [j], dp [j - H [i]] + K [i]);

           }

       }

   }

   cout << *max_element (dp, dp + M + 1) << '\n';

   return 0;

}

Studi Kasus B4. Paket

B4.1. 9

Paket yang bisa diantar bareng: Bi >= Bj, i > j

Nilai dari paket 8 = 5

Maka dari itu, cari x >= 5 di bagian kiri dari paket 8:

1. Paket 1 (Nilai = 5)

2. Paket 4 (Nilai = 8)

3. Paket 5 (Nilai = 5)

4. Paket 7 (Nilai = 5)

Kemudian, cari x <= 5 di bagian kanan dari paket 8:

5. Paket 12 (Nilai = 1)

6. Paket 13 (Nilai = 2)

7. Paket 14 (Nilai = 5)

8. Paket 15 (Nilai = 3)

9. Paket 16 (Nilai = 4)

Total = 9

B4.2. 5

Berdasarkan observasi,

"Jumlah non-increasing subsequence minimal = panjang Longest Strictly Increasing Seubsequence".

Kita dapat simulasikan saja dan lakukan greedy, dengan menghitung ada berapa iterasi paket berbeda, dengan cari menyimpan nilai paket terakhir dari setiap iterasi.

Untuk setiap paket baru, kita cari apakah ada iterasi paket yang dapat menampung paket sekarang ini.

• Kasus 1: tidak ada

Jika tidak ada, kita buat iterasi paket baru.

• Kasus 2: ada

Cari iterasi yang memiliki top >= nilai paket sekarang, dan cari top minimumnya, kemudian masukkan paket ke iterasi tersebut, dan nilai paket sekarang menjadi top dari iterasi tersebut.

• Index 1:

  • Nilai w = 5

  • Sebelum: iterasi = []

  • Buat iterasi baru dengan top = 5

  • Sesudah: iterasi = [5]

• Index 2:

  • Nilai w = 4

  • Sebelum: iterasi = [5]

  • Ganti top 5 menjadi 4

  • Sesudah: iterasi = [4]

• Index 3:

  • Nilai w = 2

  • Sebelum: iterasi = [4]

  • Ganti top 4 menjadi 2

  • Sesudah: iterasi = [2]

• Index 4:

  • Nilai w = 8

  • Sebelum: iterasi = [2]

  • Buat iterasi baru dengan top = 8

  • Sesudah: iterasi = [2, 8]

• Index 5:

  • Nilai w = 5

  • Sebelum: iterasi = [2, 8]

  • Ganti top 8 menjadi 5

  • Sesudah: iterasi = [2, 5]

• Index 6:

  • Nilai w = 3

  • Sebelum: iterasi = [2, 5]

  • Ganti top 5 menjadi 3

  • Sesudah: iterasi = [2, 3]

• Index 7:

  • Nilai w = 6

  • Sebelum: iterasi = [2, 3]

  • Buat iterasi baru dengan top = 6

  • Sesudah: iterasi = [2, 3, 6]

• Index 8:

  • Nilai w = 5

  • Sebelum: iterasi = [2, 3, 6]

  • Ganti top 6 menjadi 5

  • Sesudah: iterasi = [2, 3, 5]

• Index 9:

  • Nilai w = 8

  • Sebelum: iterasi = [2, 3, 5]

  • Buat iterasi baru dengan top = 8

  • Sesudah: iterasi = [2, 3, 5, 8]

• Index 10:

  • Nilai w = 9

  • Sebelum: iterasi = [2, 3, 5, 8]

  • Buat iterasi baru dengan top = 9

  • Sesudah: iterasi = [2, 3, 5, 8, 9]

• Index 11:

  • Nilai w = 7

  • Sebelum: iterasi = [2, 3, 5, 8, 9]

  • Ganti top 8 menjadi 7

  • Sesudah: iterasi = [2, 3, 5, 7, 9]

• Index 12:

  • Nilai w = 1

  • Sebelum: iterasi = [2, 3, 5, 7, 9]

  • Ganti top 2 menjadi 1

  • Sesudah: iterasi = [1, 3, 5, 7, 9]

• Index 13:

  • Nilai w = 2

  • Sebelum: iterasi = [1, 3, 5, 7, 9]

  • Ganti top 3 menjadi 2

  • Sesudah: iterasi = [1, 2, 5, 7, 9]

• Index 14:

  • Nilai w = 5

  • Sebelum: iterasi = [1, 2, 5, 7, 9]

  • Ganti top 5 menjadi 5 (tetap)

  • Sesudah: iterasi = [1, 2, 5, 7, 9]

• Index 15:

  • Nilai w = 3

  • Sebelum: iterasi = [1, 2, 5, 7, 9]

  • Ganti top 5 menjadi 3

  • Sesudah: iterasi = [1, 2, 3, 7, 9]

• Index 16:

  • Nilai w = 4

  • Sebelum: iterasi = [1, 2, 3, 7, 9]

  • Ganti top 7 menjadi 4

  • Sesudah: iterasi = [1, 2, 3, 4, 9]

Hasil Akhir: jumlah iterasi  = 5

Jawaban = 5

B4.3. 5

Kita tinggal mencari Longest Non Increasing Subsequence nya:

Salah satu konfigurasi yang valid:

Paket 4 (Nilai 8) -> Paket 9 (Nilai = 8) -> Paket 11 (Nilai = 7) -> Paket 14 (Nilai = 5) -> Paket 16 (Nilai = 4).

Jawaban = 5

Soal Pemrograman

Berdasarkan observasi,

"Jumlah non-increasing subsequence minimal = panjang Longest Strictly Increasing Seubsequence".

Dengan kata lain, problem ini sama saja seperti kita mencari longest strictly increasing subsequence.

Subsoal 1:

Kita dapat mencari Longest Strictly Increasing Subsequence menggunakan dynamic programming.

Definisi DP:

dp [i] = Longest Strictly Increasing Subsequence pada index i.

Transisi:

Untuk setiap pasangan index j < i, jika B [j] < B [i], artinya kita bisa menambahkan B [i] dibelakang subsequence yang berakhir di j), maka:

dp [i] = max (dp [i], dp [j] + 1);

Jawaban akhir terdapat pada nilai maksimum pada array dp.

Kompleksitas waktu:

O (N^2)

#include <bits/stdc++.h>

using namespace std;

int main() {

   int N;

   cin >> N;

   int B [N];

   for (int i = 0 ; i < N ; i ++) {

       cin >> B [i];

   }

   int dp [N];

   for (int i = 0 ; i < N ; i ++) {

       dp [i] = 1;

   }

   for (int i = 0 ; i < N ; i ++) {

       for (int j = 0 ; j < i ; j ++) {

           if (B [j] < B [i]) {

               dp [i] = max (dp [i], dp [j] + 1);

           }

       }

   }

   cout << *max_element (dp, dp + N) << '\n';

   return 0;

}

Solusi penuh:

Kita dapat simulasikan saja dan lakukan greedy, dengan menghitung ada berapa iterasi paket berbeda, dengan cari menyimpan nilai paket terakhir dari setiap iterasi.

Untuk setiap paket baru, kita cari apakah ada iterasi paket yang dapat menampung paket sekarang ini.

Untuk menyimpan nilai top dari setiap iterasi yang ada sekarang, kita dapat gunakan vector atau set.

• Kasus 1: tidak ada

Jika tidak ada, kita buat iterasi paket baru. -> vector.push_back (w);

• Kasus 2: ada

Cari iterasi yang memiliki top >= nilai paket sekarang, dan cari top minimumnya, kemudian masukkan paket ke iterasi tersebut, dan nilai paket sekarang menjadi top dari iterasi tersebut.

Untuk mencari top tersebut, kita dapat gunakan binary search.

Jawaban akhirnya adalah total iterasinya, sama seperti size dari vector / set pada akhirnya.

Kompleksitas waktu: 

O (N log N)

#include <bits/stdc++.h>

using namespace std;

int main() {

   int N;

   cin >> N;

   int B [N];

   for (int i = 0 ; i < N ; i ++) {

       cin >> B [i];

   }

   vector <int> S;

   for (int i = 0 ; i < N ; i ++) {

       auto it = lower_bound (S.begin (), S.end (), B [i]);

       if (it == S.end ()) {

           S.push_back (B [i]);

       } else {

           *it = B [i];

       }

   }

   cout << S.size() << '\n' ;

   return 0 ;

}

Studi Kasus B5. Suhu

B5.1. 7/2

(B + j) / (A + i)

i <= 4

j <= 5

i mengecilkan value, j memaksimalkan value, maka ambil i yang paling kecil dan j yang paling besar.

maka ambil i = 1, j = 5

(B + 5) / (A + 1) = 7/2

B5.2. 5

1. (4, 1) -> 3/5 -> 3/5

2. (3, 1) -> 3/4 -> 3/4

3. (4, 2) -> 4/5 -> 4/5

4. (2, 1) -> 3/3 -> 1/1

5. (3, 2) -> 4/4 -> 1/1

6. (4, 3) -> 5/5 -> 1/1

7. (1, 1) -> 3/2 -> 3/2

8. (2, 2) -> 4/3 -> 4/3

9. (3, 3) -> 5/4 -> 5/4

10. (4, 4) -> 6/5 -> 6/5

11. (1, 2) -> 4/2 -> 2/1

12. (2, 3) -> 5/3 -> 5/3

13. (3, 4) -> 6/4 -> 3/2

14. (4, 5) -> 7/5 -> 7/5

15. (1, 3) -> 5/2 -> 5/2

16. (2, 4) -> 6/3 -> 2/1

17. (3, 5) -> 7/4 -> 7/4

18. (1, 4) -> 6/2 -> 3/1

19. (2, 5) -> 7/3 -> 7/3

20. (1, 5) -> 7/2 -> 7/2

Banyaknya:

• 3/5 -> 1

• 3/4 -> 1

• 4/5 -> 1

• 1/1 -> 3

• 3/2 -> 2

• 4/3 -> 1

• 5/4 -> 1

• 6/5 -> 1

• 2/1 -> 2

• 5/3 -> 1

• 7/5 -> 1

• 5/2 -> 1

• 7/4 -> 1

• 3/1 -> 1

• 7/3 -> 1

• 7/2 -> 1

Kontribusi:

3 Pengunjung 1/1 -> 3

2 Pengunjung 3/2 -> 1

2 Pengunjung 2/1 -> 1

Total = 5

B5.3. 7/5

Urutan dari paling kecil ke paling besar.

1.  (4, 1) -> 3/5   -> 3/5

2.  (3, 1) -> 3/4   -> 3/4

3.  (4, 2) -> 4/5   -> 4/5

4.  (2, 1) -> 3/3   -> 1/1

5.  (3, 2) -> 4/4   -> 1/1

6.  (4, 3) -> 5/5   -> 1/1

7.  (4, 4) -> 6/5   -> 6/5

8.  (3, 3) -> 4/5   -> 5/4

9.  (2, 2) -> 4/3   -> 4/3

10. (4, 5) -> 7/5   -> 7/5

11. (1, 1) -> 3/2   -> 3/2

12. (3, 4) -> 6/4   -> 3/2

13. (2, 3) -> 5/3   -> 5/3

14. (3, 5) -> 7/4   -> 7/4

15. (1, 2) -> 4/2   -> 2/1

16. (2, 4) -> 6/3   -> 2/1

17. (2, 5) -> 7/3   -> 7/3

18. (1, 3) -> 5/2   -> 5/2

19. (1, 4) -> 6/2   -> 3/1

20. (1, 5) -> 7/2   -> 7/2

Urutan ke-10 = 7/5

Soal Pemrograman

Subsoal 1:

Kita dapat membuat semua nilai (B + j) / (A + i) yang mungkin, kemudian simpan dalam vector, kemudian lakukan sorting.

Untuk sortingnya, buat custom sort untuk membandingkan kedua pecahan..

Kita dapat membandingkan pecahan p1/q1 dengan p2/q2 dengan cara memindahkan ruas:

p1/q1 <=> p2/q2 -> p1q2 <=> p2q1

Dengan begitu, maka tiap query, kita sudah bisa langsung mengakses jawabannya, jangan lupa dibagi gcd sehingga kedua angka relatif prima.

Kompleksitas waktu:

O (N * M log (N * M) + Q * log (min(B + j, A + i)))

#include <bits/stdc++.h>

using namespace std;

int main () {

   int N, M, A, B, Q;

   cin >> N >> M >> A >> B >> Q;

   vector <pair <int, int>> X;

   for (int i = 1 ; i <= N ; i ++) {

       for (int j = 1 ; j <= M ; j ++) {

           X.push_back (make_pair (B + j, A + i));

       }

   }

   sort (X.begin (), X.end (),

       [&] (pair <int, int> &a, pair <int, int> &b) {

           return a.first * b.second < b.first * a.second;

       }

   );

   while (Q --) {

       int k;

       cin >> k;  

       int gcd = __gcd (X [k - 1].first, X [k - 1].second);

       cout << X [k - 1].first / gcd << '/' << X [k - 1].second / gcd << '\n';

   }

   return 0;

}

Ide utama: binary search

Kita ingin mencari angka real X sekecil mungkin sehingga ada setidaknya k pengunjung yang memenuhi <= X. Setelah X ditemukan, value ke-k akan berada di antara L dan R yang kita dapatkan dari binary search.

Range: L = 0, R = 1e9

Lakukan iterasi sebanyak sekitar 100 kali agar mendapatkan presisi yang baik.

Pada tiap iterasi, untuk setiap mid yang kita dapatkan kita hitung berapa banyak (i,j) sehingga (B+j)/(A+i) <=mid. 

Karena untuk baris i nilai (B+j)/(A+i) meningkat seiring j, kita cukup menentukan j maksimal t di baris itu yang masih memenuhi (B+t)/(A+i) <= mid dengan t = floor(mid * (A+i) - B), kemudian membatasi t antara 0 dan M. Total pengunjung dengan suhu <= mid adalah jumlah t dari 1 sampai N.

Setelah melakukan semua iterasi, ambil nilai R sebagai batas suhu ke-k. Dengan begitu, kita sudah dapat mencari elemen terkecil ke-k.

Pada titik R, kita sudah mengetahui ada k kursi yang memiliki suhu <= R, kita tinggal mencari maksimum dari suhu yang memenuhi <= R.

Kita dapat membandingkan pecahan p1/q1 dengan p2/q2 dengan cara memindahkan ruas:

p1/q1 <=> p2/q2 -> p1q2 <=> p2q1

Maka jawaban akhirnya adalah pecahan terbesar yang memenuhi <= R.

Jangan lupa untuk sederhanakan pecahan.

Definisikan g = gcd (p, q)

Maka jawaban akhir adalah (p/g)/(q/g).

Kompleksitas Waktu:

O (100 * Q * N)

#include <bits/stdc++.h>

using namespace std;

int main () {

   long long N, M, A, B, Q;

   cin >> N >> M >> A >> B >> Q;

   while (Q --) {

       long long k;

       cin >> k;

       long double l = 0, r = 1e9;

       for (int itr = 0 ; itr < 100 ; itr ++) {

           long double mid = (l + r) / 2 ;

           long long count = 0;

           for (int i = 1 ; i <= N ; i ++) {

               long long t = floor (mid * (A + i) - B);

               count += max (0LL, min (t, (long long) M));

           }

           if (count >= k) r = mid;

           else l = mid;

       }

       pair <long long, long long> jawab = {0, 1};

       for (int i = 1 ; i <= N ; i ++) {

           long long t = floor (r * (A + i) - B);

           if (t <= 0) continue;

           if (t > M) t = M;

           pair <long long, long long> cur = {B + t, A + i};

           if (jawab.first * cur.second < jawab.second * cur.first) {

               jawab = cur;

           }

       }

       long long gcd = __gcd (jawab.first, jawab.second);

       cout << jawab.first / gcd << '/' << jawab.second / gcd << '\n';

   }

   return 0;

}