# Simulasi OSN-P • Pelatda DKI Jakarta Tahap 1 2023

## B1. Manipulasi Ukuran

### Deskripsi Cerita

Pak Bondol ingin membeli televisi baru untuk diletakkan di ruang tamu. Ruang tamu Pak Bondol dapat memuat televisi baru tersebut selama lebarnya tidak lebih dari $a$ dan tingginya tidak lebih dari $b$. Karena Pak Bondol sebelumnya memiliki televisi dengan layar berukuran lebar $x$ dan tinggi $y$, Pak Bondol ingin membeli televisi baru dengan rasio aspek yang sama dengan televisi sebelumnya (dengan kata lain, apabila televisi baru tersebut memiliki lebar $w$ dan tinggi $h$, maka $\frac{w}{h} = \frac{x}{y}$ harus terpenuhi).

Ternyata, toko televisi yang Pak Bondol kunjungi menjual televisi yang ukurannya dapat dipesan sesuai keinginan pembeli, selama memiliki lebar $w$ dan tinggi $h$ dengan $w$ dan $h$ merupakan bilangan bulat positif. Karena banyaknya pilihan televisi yang dapat dibuat, sekarang Pak Bondol penasaran, ada berapa banyak ukuran televisi berbeda yang memenuhi seluruh kriteria Pak Bondol.

Dengan kata lain, Pak Bondol ingin mencari banyaknya pasangan bilang bulat positif $w$ dan $h$ yang memenuhi syarat $(w \le a)$, $(h \le b)$, dan $\left( \frac{w}{h} = \frac{x}{y} \right)$. Bantu Pak Bondol!

### Pertanyaan Isian Singkat

1. Jika $a = 20, b = 23, x = 6,$ dan $y = 10$, tentukan luas terkecil dari ukuran televisi yang dapat Pak Bondol beli?
**Jawablah dengan angka saja.**
2. Jika $a = 20, b = 23, x = 6,$ dan $y = 10$, tentukan luas terbesar dari ukuran televisi yang dapat Pak Bondol beli?
**Jawablah dengan angka saja.**
3. Jika $a = 225, b = 276, x = 42,$ dan $y = 210$, berapa banyak ukuran televisi berbeda yang dapat Pak Bondol beli?
**Jawablah dengan angka saja.**

### Membuat Program

Buatlah sebuah program dalam bahasa C/C++ untuk mencari jawaban yang Pak Bondol cari sesuai dengan deskripsi pada cerita di atas!

#### Format Masukan

Satu baris yang terdiri atas empat bilangan bulat $a, b, x,$ dan $y$ yang dipisahkan spasi, yang berturut-turut menunjukkan batasan ukuran lebar dan tinggi televisi baru, serta lebar dan tinggi televisi sebelumnya.

#### Format Keluaran

Satu baris yang berisi sebuah bilangan bulat yang menyatakan jawaban yang diminta.

#### Contoh Masukan 1

8 4 6 4

#### Contoh Keluaran 1

2

#### Penjelasan Contoh 1

Pak Bondol dapat membeli televisi baru dengan ukuran $(3, 2)$ atau $(6, 4)$.

#### Contoh Masukan 2

3105 2023 3900 1200

#### Contoh Keluaran 2

238

#### Batasan

- $1 \le a, b, x, y \le 10^{18}$

#### Subsoal

1. (50\% poin) $a, b, x, y \le 1 \ 000$
2. (50\% poin) Tidak ada batasan tambahan.

## B2. Manipulasi Suhu

### Deskripsi Cerita

Di Provinsi DKI Jakarta, yang berbentuk suatu garis lurus, angin selalu bertiup dari laut ke arah darat. Garis lurus tersebut terdiri atas $N$ titik yang dinomori dari $1$ sampai $N$ dari kiri ke kanan. Titik ke-$i \ (0 \le i \le N)$ terletak $A_i$ meter di atas permukaan laut. Titik ke-$0$ merupakan laut, sedangkan titik ke-$N$ merupakan rumah Pak Bondol.

Pada awalnya, angin dari laut memiliki suhu $0$ derajat. Saat melalui suatu titik $i \ (1 \le i \le N-1)$, suhu angin tersebut dapat berubah sebagai berikut.

- Jika ketinggian titik $i+1$ lebih **tinggi** dari titik $i$, suhu angin **berkurang** $S$ derajat per meter.
- Jika ketinggian titik $i+1$ lebih **rendah** dari titik $i$, suhu angin **bertambah** $T$ derajat per meter.

Pak Bondol tidak puas dengan suhu yang ia rasakan di titik $N$. Oleh karena itu, ia akan memanipulasi tinggi titik-titik di DKI Jakarta sebanyak $Q$ kali. Pada hari ke-$j \ (1 \le j \le Q)$, Pak Bondol meninggikan titik $L_j$ sampai $R_j$ (inklusif) sebanyak $X_j$. (Jika $X_j$ negatif, berarti Pak Bondol merendahkan titik-titik tersebut). Pak Bondol ingin tahu berapa suhu yang ia rasakan di rumahnya setelah setiap manipulasi tersebut. (Catat bahwa hasil dari suatu manipulasi **tidak** dikembalikan ke asal sebelum hari berikutnya.) Bantu Pak Bondol!

### Pertanyaan Isian Singkat

1. Jika $N = 5, A = [0, 5, 2, -3, 4, -1], S = 5,$ dan $T = 2$, berapa suhu yang dirasakan Pak Bondol di rumahnya?
**Jawablah dengan angka saja.**
2. Jika $N = 5, A = [0, 2, 1, 8, 4, 3], T = 1$, dan suhu yang dirasakan Pak Bondol adalah $-30$ derajat, berapakah nilai $S$?
**Jawablah dengan angka saja.**
3. Jika $N = 4, A = [0, 3, 6, 1, -1], S = 3, T = 1,$ dan Pak Bondol meninggikan bangunan $1$ sampai $3$ sebanyak $2$ meter, berapa suhu yang dirasakan Pak Bondol di rumahnya?
**Jawablah dengan angka saja.**

### Membuat Program

Buatlah sebuah program dalam bahasa C/C++ untuk mencari jawaban yang Pak Bondol cari sesuai dengan deskripsi pada cerita di atas!

#### Format Masukan

Baris pertama berisi empat buah bilangan bulat $N, Q, S,$ dan $T$ yang dipisahkan spasi.

$N + 1$ baris berikutnya masing-masing berisi sebuah bilangan bulat $A_i \ (0 \le i \le N)$.

$Q$ baris berikutnya masing-masing berisi tiga buah bilangan bulat $L_j, R_j,$ dan $X_j \ (1 \le j \le Q)$ yang dipisahkan spasi.

#### Format Keluaran

Keluarkan $Q$ buah baris. Baris ke-$i \ (1 \le i \le Q)$ berisi sebuah bilangan bulat yang menandakan suhu di rumah Pak Bondol setelah manipulasi ke-$i$.

#### Contoh Masukan 1

3 5 1 2
0
4
1
8
1 2 2
1 1 -2
2 3 5
1 2 -1
1 3 5

#### Contoh Keluaran 1

-5
-7
-13
-13
-18

#### Penjelasan Contoh 1

Pada awalnya, ketinggian titik $0, 1, 2,$ dan $3$ berturut-turut adalah $0, 4, 1,$ dan $8$. Setelah manipulasi pada hari pertama, ketinggian titik-titik tersebut menjadi $0, 6, 3,$ dan $8$. Suhu yang dirasakan pada titik-titik tersebut berturut-turut adalah $0, -6, 0,$ dan $-5$.

#### Contoh Masukan 2

2 2 5 5
0
6
-1
1 1 4
1 2 8

#### Contoh Keluaran 2

5
-35

#### Batasan

- $1 \le N, Q \le 200 \ 000$
- $1 \le S, T \le 10^6$
- $A_0 = 0$
- $-10^6 \le A_i \le 10^6 \ (1 \le i \le N)$
- $1 \le L_j \le R_j \le N \ (1 \le j \le Q)$
- $-10^6 \le X_j \le 10^6 \ (1 \le j \le Q)$

#### Subsoal

1. (50\% poin) $N, Q \le 2 \ 000$
2. (50\% poin) Tidak ada batasan tambahan.

## B3. Manipulasi Array

### Deskripsi Cerita

Pak Bondol memiliki *array* $A$ sepanjang $N$, yang elemennya dinomori dari $1$ hingga $N$. Elemen $i$ dari *array* $A$ adalah $A_i$.

Pak Bondol diberikan kesempatan satu kali untuk memilih sebuah *subarray* dari $A$ (bisa saja kosong), kemudian mengalikan semua elemen dalam *subarray* tersebut dengan $X$.

Untuk semua *subarray* yang ada (bisa saja kosong), Pak Bondol ingin mencari jumlah maksimum dari elemen yang ada dalam *subarray* tersebut. Bantu Pak Bondol!

**Catatan:** Sebuah *subarray* adalah bagian dari *array* yang indeksnya berurutan. Sebagai contoh, jika $A = [3, -5, 2, -3, 1]$, maka $[2, -3, 1]$, $[-5]$, $[3, -5, 2, -3, 1]$, dan $[]$ (subarray kosong) adalah subarray dari $A$.

### Pertanyaan Isian Singkat

1. Apabila $A = [3, -1, 2, 4, -9, 7, 2, -4]$ dan $X = 1$, maka tentukan jawaban yang Pak Bondol minta!
**Jawablah dengan angka saja.**
2. Apabila $A = [1, -1, 2, -2, 3, -3, \dots, 100, -100]$ dan $X = 0$, maka tentukan jawaban yang Pak Bondol minta!
**Jawablah dengan angka saja.**
3. Apabila $A = [-20, 21, -15, 10, -10, 20, 10]$ dan $X = -1$, maka tentukan jawaban yang Pak Bondol minta!
**Jawablah dengan angka saja.**

### Membuat Program

Buatlah sebuah program dalam bahasa C/C++ untuk mencari jawaban yang Pak Bondol cari sesuai dengan deskripsi pada cerita di atas!

#### Format Masukan

Baris pertama berisi dua buah bilangan bulat $N$ dan $X$.
Baris berikutnya berisi $N$ buah bilangan bulat $A_i \ (1 \le i \le N)$.

#### Format Keluaran

Satu baris yang berisi sebuah bilangan bulat yang menyatakan jawaban yang diminta.

#### Contoh Masukan 1

5 -2
3 -5 2 -3 1

#### Contoh Keluaran 1

16

#### Penjelasan 1

Pak Bondol dapat mengalikan subarray $[-5, 2, -3]$ dengan $X = -2$ sehingga array $A$ bernilai $[3, 10, -4, 6, 1]$. Subarray dari $A$ yang memiliki jumlah maksimum adalah $[3, 10, -4, 6, 1]$ dengan jumlah sebesar $3 + 10 + (-4) + 6 + 1 = 16$.

#### Contoh Masukan 2

5 10
-10 -10 10 -10 -10

#### Contoh Keluaran 2

100

#### Penjelasan 2

Pak Bondol dapat mengalikan subarray $[10]$ dengan $X = 10$ sehingga array $A$ bernilai $[-10, -10, 100, -10, -10]$. Subarray dari $A$ yang memiliki jumlah maksimum adalah $[100]$ dengan jumlah sebesar $100$.

#### Contoh Masukan 3

5 10
-10 -10 -10 -10 -10

#### Contoh Keluaran 3

0

#### Penjelasan 3

Untuk subarray apapun yang Pak Bondol pilih untuk dikalikan, subarray dari $A$ yang memiliki jumlah maksimum adalah $[]$ dengan jumlah sebesar $0$.

#### Batasan

- $1 \leq N \leq 100\,000$
- $-100 \leq X \leq 100$
- $-10^9 \leq A_i \leq 10^9$

#### Subsoal

1. (50\% poin) $X > 0$
2. (50\% poin) Tidak ada batasan tambahan.

## B4. Manipulasi Pengiriman

### Deskripsi Cerita

Pak Bondol memiliki $N$ buah batu yang dinomori dari $1$ sampai $N$. Setiap batu memiliki berat dan nilai keindahan. Batu ke-$i$ memiliki berat $W_i$ dan nilai keindahan $V_i$.

Pak Bondol ingin mengirim beberapa batu yang ia miliki menggunakan pesawat. Namun, biaya pengiriman udara yang digunakan Pak Bondol memiliki perhitungan yang unik. Definisikan $W_{max}$ sebagai berat batu terbesar dan $W_{min}$ sebagai berat batu terkecil dari batu-batu yang Pak Bondol akan kirim. Maka, Pak Bondol harus membayar biaya pengiriman sebesar $W_{max} - W_{min}$. Dengan kata lain, biaya pengiriman batu-batu yang dikirim Pak Bondol adalah sebesar selisih berat antara batu terberat dan batu teringan.

Namun, Pak Bondol juga ingin agar total nilai keindahan batu-batu yang ia kirim sebesar mungkin. Pada akhirnya, Pak Bondol memutuskan untuk mengirim batu-batu sehingga total nilai keindahan dikurangi dengan selisih berat batu terberat dan teringan adalah maksimum. Secara formal, definisikan $S$ sebagai total nilai keindahan dari batu-batu yang Pak Bondol kirim. Pak Bondol ingin memaksimalkan nilai $S - (W_{max} - W_{min})$.

### Pertanyaan Isian Singkat

1. Jika $N = 5$, berat batu atau $W = [12, 7, 15, 6, 17]$, dan nilai keindahan atau $V = [10, 4, 5, 1, 1]$, berapa nilai yang dicari Pak Bondol?
**Jawablah dengan angka saja.**
2. Jika $N = 100$, berat dari semua batu adalah $1$ ($W = [1, 1, 1,.., 1, 1, 1]$), dan nilai keindahan semua batu adalah $1$ ($V = [1, 1, 1,.., 1, 1, 1]$), berapa nilai yang dicari Pak Bondol?
**Jawablah dengan angka saja.**
3. Jika $N = 100$, berat dari batu ke-$i$ adalah $i^2$ ($W = [1, 4,.., 9801, 10000]$), dan nilai keindahan semua batu adalah $5$ ($V = [5, 5, 5,.., 5, 5, 5]$), berapa nilai yang dicari Pak Bondol?
**Jawablah dengan angka saja.**

### Membuat Program

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

#### Format Masukan

Baris pertama berisi sebuah bilangan bulat $N$ yang menyatakan banyak batu yang dimiliki Pak Bondol.
$N$ baris berikutnya masing-masing berisi dua bilangan bulat $W_i$ dan $V_i$ yang dipisahkan spasi, yang menyatakan berat dan nilai keindahan batu ke-$i \ (1 \le i \le N)$.

#### Format Keluaran

Keluarkan sebuah bilangan bulat yang menyatakan nilai $S - (W_{max} - W_{min})$ terbesar yang mungkin.

#### Contoh Masukan 1

3
1 3
5 1
3 2

#### Contoh Keluaran 1

3

#### Penjelasan Contoh 1

Pada contoh masukan ini, terdapat $3$ batu.
- Batu pertama memiliki berat $1$ dan nilai keindahan $3$.
- Batu kedua memiliki berat $5$ dan nilai keindahan $1$.
- Batu ketiga memiliki berat $3$ dan nilai keindahan $2$.

Kita dapat mengirim batu pertama dan ketiga, sehingga nilai $S - (W_{max} - W_{min}) = 3$. Perhatikan bahwa nilai ini merupakan nilai terbesar yang mungkin dibandingkan pemilihan batu lainnya.

#### Contoh Masukan 2

6
8 5
3 1
2 1
6 3
100 9
7 4

#### Contoh Keluaran 2

10

#### Contoh Masukan 3

15
1543361732 260774320
2089759661 257198921
1555665663 389548466
4133306295 296394520
2596448427 301103944
1701413087 274491541
2347488426 912791996
2133012079 444074242
2659886224 656957044
1345396764 259870638
2671164286 233246973
2791812672 585862344
2996614635 91065315
971304780 488995617
1523452673 988137562

#### Contoh Keluaran 3

4232545716

#### Batasan

- $1 \le N \le 500 \ 000$
- $1 \le W_i \le 10^{15}$
- $1 \le V_i \le 10^9$

#### Subsoal

1. (50\% poin) $N \le 5 \ 000$
2. (50\% poin) Tidak ada batasan tambahan.

## B5. Manipulasi Grid

### Deskripsi Cerita
Pak Bondol memberikan Anda sebuah *grid* 2 dimensi dengan $N$ baris (yang dinomori dari $1$ hingga $N$) dan $M$ kolom (yang dinomori dari $1$ hingga $M$). Setiap sel dapat berwarna hitam atau putih. Suatu sel $(x,y)$ yang terletak pada baris ke-$x$ dan kolom ke-$y$ bersinggungan dengan sel $(x+1, y)$, $(x, y+1)$, $(x-1, y)$, dan $(x, y-1)$. Untuk setiap pasang sel hitam $u$ dan $v$, terdapat paling banyak satu *path* yang dimulai dari $u$, hanya melalui sel hitam yang bersinggungan, dan diakhiri pada $v$ tanpa mengunjungi sel yang sama lebih dari satu kali.

Gambar di bawah ini menunjukkan salah satu konfigurasi *grid* yang valid. Terdapat paling banyak satu *path* di antara dua sel hitam yang berbeda pada *grid* tersebut.


Sementara itu, gambar di bawah ini merupakan contoh *grid* yang tidak valid, karena terdapat lebih dari satu *path* untuk beberapa pasang sel hitam yang berbeda, misalnya pasangan sel hitam yang ditandai dengan warna merah.


Pak Bondol memberikan Anda $Q$ pertanyaan. Pada pertanyaan ke-$i$, Anda diminta untuk menentukan ada berapa banyak *connected component* yang terdapat pada *subgrid* yang terbentuk dari baris $X_{i,1}$ hingga baris $X_{i,2}$ dan dari kolom $Y_{i,1}$ hingga kolom $Y_{i,2}$. Dua buah sel hitam $u$ dan $v$ berada dalam *connected component* yang sama jika terdapat sebuah *simple path* dari $u$ ke $v$.

### Pertanyaan Isian Singkat
1. Jika $N = 10$, $M = 10$, $Q = 1$, $X_{1,1} = 6$, $X_{1,2} = 9$, $Y_{1,1} = 3$, $Y_{1,2} = 10$, dan sel $(r, c)$ berwarna hitam jika dan hanya jika $r + c$ bernilai genap, berapa nilai yang dicari Pak Bondol?
**Jawablah dengan angka saja.**
2. Jika $N = 5$, $M = 6$, $Q = 1$, $X_{1,1} = 2$, $X_{1,2} = 5$, $Y_{1,1} = 3$, $Y_{1,2} = 5$, dan sel $(r, c)$ berwarna putih jika dan hanya jika $r + c$ habis dibagi 3, berapa nilai yang dicari Pak Bondol?
**Jawablah dengan angka saja.**
3. Jika $N = 1$, $M = 20$, $Q = 210$, sel $(r, c)$ berwarna hitam jika dan hanya jika $r + c$ bernilai genap, $X_{i,1} = X_{i,2} = 1$, dan $(Y_{i,1}, Y_{i,2}) = [(1,1), (1,2), (1,3), …, (1, 20), (2, 2), (2, 3), …, (2, 20), …(20, 20)]$, berapa hasil penjumlahan nilai dari semua pertanyaan Pak Bondol?
**Jawablah dengan angka saja.**

### Membuat Program

Buatlah sebuah program dalam bahasa C/C++ untuk mencari jawaban yang Pak Bondol cari sesuai dengan deskripsi pada cerita di atas!

#### Format Masukan

Baris pertama terdiri atas tiga buah bilangan bulat $N$, $M$ dan $Q$ yang dipisahkan spasi, yang berturut-turut menunjukkan banyak baris, banyak kolom, dan banyak pertanyaan.
$N$ baris berikutnya terdiri atas $M$ karakter. Karakter ke-$j$ pada baris ke-$i \ (1 \le i \le N, 1 \le j \le M)$ menunjukkan warna dari sel $(i, j)$. Sel berwarna putih direpresentasikan dengan karakter `0` dan sel berwarna hitam direpresentasikan dengan karakter `1`.
$Q$ baris berikutnya terdiri atas empat buah bilangan bulat $X_{i,1}$, $Y_{i,1}$, $X_{i,2}$, dan $Y_{i,2}$ yang dipisahkan spasi, yang merepresentasikan sudut kiri atas dan sudut kanan bawah dari *subgrid* pada pertanyaan ke-$i \ (1 \le i \le Q)$.

#### Format Keluaran

Untuk setiap pertanyaan, keluarkan sebuah bilangan bulat $c$, yaitu banyaknya *connected component* yang berada pada *subgrid* yang ditanyakan.

#### Contoh Masukan 1

3 4 4
1101
0110
1101
1 1 3 4
1 1 3 1
2 2 3 4
1 2 2 4

#### Contoh Keluaran 1

3
2
2
2

#### Penjelasan Contoh 1

Pada pertanyaan pertama, *subgrid* yang ditanyakan adalah seluruh *grid*. Banyaknya *connected component* yang berada pada *grid* adalah $3$.

Pada pertanyaan ketiga, *subgrid* yang ditanyakan dibatasi dengan warna merah. Pada *subgrid* tersebut, terdapat $2$ *connected component* yang berbeda.

#### Contoh Masukan 2

5 5 6
11010
01110
10101
11101
01010
1 1 5 5
1 2 4 5
2 3 3 4
3 3 3 3
3 1 3 5
1 1 3 4

#### Contoh Keluaran 2

3
2
1
1
3
2

#### Batasan
- $1 \leq N, M \leq 2 \ 000$
- $1 \leq Q \leq 200 \ 000$
- Tiap sel pada *grid* direpresentasikan dengan `0` atau `1`.
- Struktur *grid* memenuhi ketentuan yang dijelaskan pada deskripsi soal.
- $1 \leq X_{i,1} \leq X_{i,2} \leq N \ (1 \leq i \leq Q)$
- $1 \leq Y_{i,1} \leq Y_{i,2} \leq M \ (1 \leq i \leq Q)$

#### Subsoal

1. (50\% poin) $1 \leq Q \leq 10$
2. (50\% poin) Tidak ada batasan tambahan.