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` ---