---
# System prepended metadata

title: Competitive Programming COIN 2020

---

# Competitive Programming COIN 2020


[TOC]

---

## Waktu COIN

**KODE PROBLEM**: `cointime`

**KATEGORI**: mudah

Okki adalah seorang wibu akut, setiap hari dia menghabiskan waktu dengan
menonton anime atau baca manga. Pada suatu hari, dia mendapatkan suatu hidayah
untuk belajar pemrograman. Untuk melatih skill pemrogramannya, Okki memutuskan
untuk mengikuti Competitive Programming COIN. Kompetisi tersebut akan dimulai
pada 2 Februari 2020 (02/02/2020). Waktu mulai pengerjaanya bebas, tapi peserta
hanya diberi waktu 3 Jam dari saat peserta mulai ngoding. Karena tanggalnya
cantik, Okki ingin memulai ngoding tepat pukul 20:20 pada 02/02/2020. 

Akan tetapi, karena dia seorang wibu, Okki sulit sekali untuk mengatur
waktunya. Karena itu dia ingin membuat sebuah program agar dia tidak melebihi
batas waktu kompetisinya.

Dengan diberikan tanggal dan waktu dia berhenti ngoding, hitunglah waktu yang
Okki gunakan untuk ngoding dalam kompetisi tersebut dalam menit.

---

**FORMAT INPUT**:

* Line 1:

  3 integer space-separated, $D\ H\ M$, yang merepresentasikan waktu dimana
  Okki berhenti ngoding.
  $D$ adalah tanggal dengan $2 \leq D \leq 6$; $H$ dan $M$ adalah jam dan menit
  dengan format waktu 24 Jam ($H=0$, $M=0$ sampai $H=23$, $M=59$).

**CONTOH INPUT**:

```
3 19 45
```

**DETAIL INPUT**:

Okki berhenti ngoding pada 3 Februari pukul 19:45.

---

**FORMAT OUTPUT**:

* Line 1:

  Total waktu yang dihabiskan Okki untuk ngoding dalam menit, atau
  `-1` jika waktu selesainya adalah sebelum kompetisi dimulai.

**CONTOH OUTPUT**:

```
1405
```

**DETAIL OUTPUT**:

Waktu yang dihabiskan Okki untuk ngoding adalah 1405 Menit.

---


## Digit yang Aneh

**KODE PROBLEM**: `digit`

**KATEGORI**: mudah

Epan baru saja belajar cara untuk mengkonversi bilangan ke basis-basis yang
berbeda dengan Pak Ino. Tapi dia selalu membuat kesalahan akibat tangannya yang selalu gemetar karena lelah.

Setiap Epan mengkonversi bilangan ke basis yang lain, dia selalu menulis salah
satu digitnya salah. Contohnya, apabila dia mengubah bilangan 14 ke biner
(basis 2), konversi yang benarnya adalah $1110$, tapi dia mungkin menulis $0110$
atau $1111$. Epan tidak pernah menghapus digit yang ada atau menambahkan digit
yang baru.

Dengan diberikan hasil konversi Epan dari suatu bilangan $N$ ke basis 2 dan
basis 3, carilah nilai bilangan original dari $N$ (dalam basis 10). Kamu dapat
berasumsi kalau nilai $N \leq 10^9$, dan ada solusi unik untuk $N$.

> Boleh melihat referensi mengenai bilangan basis 2 dan basis 3 dari internet.

---

**FORMAT INPUT**:

* Line 1:

  Representasi basis 2 dari $N$, dengan kesalahan pada satu digitnya

* Line 2:

  Representasi basis 3 dari $N$, dengan kesalahan pada satu digitnya

**CONTOH INPUT**:

```
1010
212
```

**DETAIL INPUT**:

Ketika Epan mengkonversi (dengan salah) $N$ ke basis 2, dia menuliskan $1010$.
Ketika Epan mengkonversi (dengan salah) $N$ ke basis 3, dia menuliskan $212$.

---

**FORMAT OUTPUT**:

* Line 1:

  Nilai $N$ original yang dikonversi oleh Epan.

**CONTOH OUTPUT**:

```
14
```

**DETAIL OUTPUT**:

Nilai $N$ yang benarnya adalah 14. Dalam basis 2 $1110$, dan basis 3 $112$.

---


## Fashion Kulit Sapi

**KODE PROBLEM**: `fashion`

**KATEGORI**: menengah

Setelah mendengar bahwa tren fashion terkini dari sapi adalah dua bintik pada
kulitnya, seorang peternak bernama Mamang Apit (MA) membeli segembala sapi
berbintik dua.

Tapi sayang sekali, karena tren berganti begitu cepat, sekarang sapi berbintik
satu menjadi tren yang paling populer.

MA ingin gembalanya lebih mengikuti fashion yang sedang tren dengan cara
menggabungkan dua bintik pada kulit sapinya menjadi satu bintik menggunakan cat.

Kulit sapinya direpresentasikan dengan suatu grid $N \times M$ ($N \geq 1, M \leq 50$)
seperti berikut:

```
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....
```

Setiap `X` menunjukan bagian dari suatu bintik. Dua `X` dapat dikatakan bagian
dari satu bintik yang sama jika berdampingan satu sama lain secara horizontal
atau vertikal (Berdampingan secara digonal tidak termasuk). Semua sapi yang
dimiliki oleh MA tepat mempunyai dua bintik.

MA ingin cat yang digunakan seminimal mungkin untuk menggabukan dua bintik
tersebut menjadi satu. Pada contoh diatas, dia dapat melakukannya dengan hanya
menambahkan tiga `X` baru. 
(Agar mudah dibedakan, pada contoh `X` yang baru diganti simbol `*`).

```
................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
........XXXXX...
.........XXX....
```

Bantu MA untuk menentukan jumlah minimum dari `X` yang harus dia cat agar
dua bintik pada sapinya bergabung menjadi satu.

---

**FORMAT INPUT**:

* Line 1:

  2 integer space-separated, $N$ dan $M$.

* Line 2 sampai $1 + N$:

  Setiap baris berisi string sepanjang M dengan karakter `X` dan `.`
  yang menandakan satu baris dari pola kulit sapi.

**CONTOH INPUT**:

```
6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....
```

**DETAIL INPUT**:

Pola pada input menunjukan kulit sapi dengan dua bintik, jika kita beri label
pada dua bintik tersebut dengan "1" dan "2", maka:

```
................
..1111....222...
...1111....22...
.1111......222..
........22222...
.........222....
```

---

**FORMAT OUTPUT**:

* Line 1:

  Jumlah `X` minimum yang harus ditambahkan pada pola dari input agar menjadi
  satu bintik.

**CONTOH OUTPUT**:

```
3
```

**DETAIL OUTPUT**:

Tiga `X` sudah cukup untuk menggabungkan dua bintik tadi menjadi satu.

```
................
..1111....222...
...1111X...22...
.1111..XX..222..
........22222...
.........222....
```

---


## Ubin yang Salah

**KODE PROBLEM**: `ubin`

**KATEGORI**: menengah

Mamang Agas (MA) ingin mempercantik lantai ruang tamu rumahnya dengan ubin yang
baru dia beli dari toko Kota'mart (toko nya hanya menjual barang-barang kotak
atau persegi saja). Akan tetapi, karena dia ceroboh, MA salah dalam mengukur
ruang tamunya. Jadi sekarang dia mesti menukarkan sebagian ubin yang sudah dia
beli dengan ukuran yang berbeda.

MA ingin menukarkan sebagian ubinnya dengan ubin baru sehingga jumlah luas seluruh
ubin yang dia punya adalah $M$. Kebetulan Kota'mart sedang ada promo dimana:
ubin dengan panjang sisi $A_i$ dapat ditukarkan dengan ubin baru dengan panjang
$B_i$ hanya dengan harga $\mathopen| A_i - B_i \mathclose| \cdot \mathopen| A_i- B_i \mathclose|$
rupiah. Akan tetapi, promo ini hanya berlaku jika ubin yang ditukarkan adalah
ubin hasil pembelian bukan penukaran -- MA tidak boleh menukarkan lagi ubin yang
sudah ditukarkan (misal ubin ukuran-3 tidak boleh ditukarkan ke ubin ukuran-2
kemudian ditukarkan lagi ke ukuran-1).

Carilah biaya minimum yang harus dibayar oleh MA agar total luas dari ubinnya
menjadi $M$. Ouputkan `-1` jika tidak mungkin untuk mendapatkan luas $M$.

---

**FORMAT INPUT**:

* Line 1:

  2 integer space-separated, $N$ $(1 \leq N \leq 10)$ dan $M$ ($1 \leq M \leq 10^4$). $N$ adalah jumlah ubin. $M$ adalah luas yang diinginkan.

* Line 2 sampai $1 + N$:

  Setiap baris berisi integer $A_1$ sampai $A_N$ berupa panjang sisi dari ubin
  ($1 \leq A_i \leq 100$).

**CONTOH INPUT**:

```
3 6
3
3
1
```

**DETAIL INPUT**:

Ada 3 ubin. 2 ubin memiliki panjang 3, dan 1 ubin memiliki panjang 1.
Kita ingin membuat luas totalnya menjadi 6.

---

**FORMAT OUTPUT**:

* Line 1:

  Biaya minimum dari penukaran ubin-ubin agar mendapat total luas $M$.
  Atau jika tidak mungkin, output `-1`.

**CONTOH OUTPUT**:

```
5
```

**DETAIL OUTPUT**:

Tukar salah satu dari ubin bersisi-3 ke bersisi-2, kemudian tukarkan ubin
bersisi-3 lain menjadi ubin bersisi-1. Jadi ubin yang ada adalah sisi-2, sisi-1,
dan sisi-1. Dengan penukaran itu didapat total luas $4 + 1 + 1 = 6$ dengan
biaya $4 + 1 = 5$.

---


## Mengecat Kandang Ternak

**KODE PROBLEM**: `catkandang`

**KATEGORI**: sulit

Setelah diabaikan bertahun-tahun, Mamang Aman (MA) memutuskan untuk mengecat
peternakannya. Perternakan MA berisi $N$ kandang berpagar ($1 \leq N \leq 5 \cdot 10^4$),
setiap kandang dapat dibayangkan sebagai persegi panjang pada bidang datar dengan
sisinya paralel terhadap sumbu x dan sumbu y. Kandang dapat berada didalam
kandang lain, akan tetapi tidak boleh ada pagar yang saling momotong. Jadi, bila
ada dua kandang yang mencakup daerah yang sama, salah satu kandangnya harus
berada didalam (terkurung) didalam kandang yang satunya lagi.

MA berfikir kalau misal kandang yang berada didalam kandang lain itu tidak akan
terlihat dari luar, maka ia memutuskan untuk hanya mengecat kandang yang tidak
terkurung oleh kandang lain.

Bantu MA untuk menentukan jumlah kandang yang harus dia cat.

---

**FORMAT INPUT**:

* Line 1:

  Jumlah kandang, $N$.

* Line 2 sampai $1 + N$:

  Setiap baris berisi 4 integer space-separated, $x_1$, $x_2$, $y_1$, dan $y_2$,
  dimana $(x_1, y_1)$ adalah sudut kiri-bawah dari kandang dan $(x_2, y_2)$
  adalah sudut kanan-atas. Semua koordinat memiliki range $1$ sampai $10^6$ 

**CONTOH INPUT**:

```
3
2 0 8 9
10 2 11 3
4 2 6 5
```

**DETAIL INPUT**:

Ada 3 kandang, yang pertama memiliki sudut pada $(2, 0)$ dan $(8, 9)$, dan
seterusnya.

---

**FORMAT OUTPUT**:

* Line 1:

  Jumlah kandang yang tidak terkurung kandang lain.

**CONTOH OUTPUT**:

```
2
```

**DETAIL OUTPUT**:

Kandang ketiga terkurung oleh kandang pertama, jadi dua kandang lain tidak
terkurung oleh kandang lainnya.

---

## Kombo Game

**KODE PROBLEM**: `kombo`

**KATEGORI**: sulit

Kang Budi Garut (BG) adalah seorang gamer. Pada suatu hari, dia sedang bermain
sebuah game, pada game tersebut tombol yang bisa digunakan hanya ada tiga, `A`, `B`, dan `C`.
BG dapat menekan tombol tersebut dalam urutan apa saja; tapi, dalam game hanya
ada $N$ kombo yang unik ($1 \leq N \leq 20$). Kombo $i$ direpresentasikan sebagai
sebuah string $S_i$ dengan panjang diantara 1 sampai 15 (inklusif) dan hanya
terdiri dari tiga huruf `A`, `B`, dan `C`.

Ketika BG menekan kombinasi huruf yang cocok dengan sebuah kombo, dia
mendapatkan satu poin untuk kombonya. Setiap kombo dapat bertumpang tindih
satu sama lain dan juga dapat selesai bersamaan. Contoh, jika $N = 3$ dan kombo
yang ada adalah `ABA`, `CB`, dan `ABACB`, kemudian BG menekan `ABACB`, maka
ia akan mendapat 3 poin. BG bisa mendapatkan poin beberapa kali dari kombo
yang sama.

Tentu saja BG ingin mendapatkan kombo sebanyak-banyaknya dalam waktu yang
sesingkat-singkatnya. Jika dia menekan tepat $K$ tombol ($1 \leq K \leq 10^3$),
berapa poin maksimum yang dapat BG raih?

---

**FORMAT INPUT**:

* Line 1:

  2 integer space-separated, $N$ dan $K$. $N$ adalah jumlah kombo yang unik dan
  $K$ adalah jumlah tombol yang ditekan.

* Line 2 sampai $1 + N$:

  Baris $i + 1$ berisi representasi string $S_i$ dari kombo $i$

**CONTOH INPUT**:

```
3 7
ABA
CB
ABACB
```

**DETAIL INPUT**:

Ada 3 kombo dan BG menekan tombolnya tepat 7 kali. Kombo pertama direpresentasikan
sebagai $S_1$ yaitu `ABA`, dan seterusnya.

---

**FORMAT OUTPUT**:

* Line 1:

  1 integer. Poin maksimum yang dapat BG raih.

**CONTOH OUTPUT**:

```
4
```

**DETAIL OUTPUT**:

Deret tombol yang optimal disini adalah `ABACBCB` yang menghasilkan 4 poin --
1 dari `ABA`, 1 dari `ABACB`, dan 2 dari `CB`

---