Hology CP 2018

hology_comb.md

Soal 2

Description

Di sebuah perusahaan bernama Coconut.Inc, seorang pekerja dimintai bossnya untuk menciptakan sebuah aplikasi generator key yang dapat merahasiakan pesan yang akan disampaikan. Bantu dia untuk menyelesaikan pekerjaannya!

Input Format

Baris pertama merupakan input user yang berisikan dictonary (key dan value) dari secret key yang akan digenerate.

Baris kedua merupakan inputan user yang berisikan kalimat yang akan dijadikan pesan rahasia.

Output Format

Seluruh huruf inputan user diubah sesuai huruf penggantinya

Sample Input

a,z l,m m,q b,q w,e s,o d,r r,v
alam bawah sadar

Sample Output

zmzq qzezh ozrzv

Soal 3

Description

Mr.Hacienda ialah seorang dosen FILKOM yang sangat taat aturan. Di setiap kelasnya ia membuat peraturan "Jika ada kurang dari K mahasiswa datang tepat waktu, kelas dibatalkan."

Jika sebuah kelas terdiri dari N mahasiswa dan diberikan waktu kedatangan tiap-tiap mahasiswa, tentukan apakah kelas dibatalkan atau tidak.

Input Format

Baris pertama T menyatakan jumlah test case.

Tiap test case terdiri dari dua baris:

Baris pertama dari tiap test case berisi dua buah integer yang dipisahkan oleh spasi, N (banyakanya mahasiswa dalam sebuah kelas) dan K (batas minimal mahasiswa datang tepat waktu). Baris kedua dari tiap test case berisi N buah integer yang dipisahkan dengan spasi, masing-masing menyatakan waktu kedatangan mahasiswa (a1,a2,...,aN). Note:

Jika ai bernilai negatif (ai≤0), berarti mahasiswa-i datang tepat waktu / sebelum kelas dimulai. Jika ai bernilai positif (ai>0), berarti mahasiswa-i datang terlambat.

T
N K
a1, a2, ..., aN
.
.
.
N K
a1, a2, ..., aN

Output Format

Untuk tiap test case, cetak YES jika kelas dibatalkan dan NO jika tidak.

Sample Input

2
4 3
-1 -3 4 2
4 2
0 -1 2 1

Sample Output

YES
NO

Explanation

Untuk test case pertama, K=3. Mr.Hacienda mengharapkan setidaknya 3 mahasiswa datang tepat waktu, namun hanya ada 2 mahasiswa yang tepat waktu (−3 dan −1) sehingga kelas dibatalkan

Untuk test case kedua, K=2. Mr.Hacienda menginginkan setidaknya 2 mahasiswa datang tepat waktu dan ada tepat 2 mahasiswa yang datang tepat waktu (0 dan −1) sehingga kelas dilanjutkan.

Constraints

• 1≤T≤10
• 1≤N≤1000
• 1≤K≤N
• −100≤ai≤100, dimana i∈[1,N]

Soal 4

Description

Carbon Exclusive Clothes. Suatu event Carbon untuk mendapat kaos Exclusive Carbon. Panitia Carbon Exclusive Clothes akan memberikan satu set kartu, S yang terdiri dari n buah kartu. Dalam masing-masing kartu tesebut terdapat bilangan integer mi yang berbeda-beda. Tugas peserta adalah memilih beberapa kartu (subset kartu, S') dengan syarat jika 2 bilangan kombinasi kartu dijumlahkan, tidak dapat habis dibagi oleh k. Setelah memilih beberapa kombinasi yang memenuhi syarat, carilah subset kartu, S' yang memiliki jumlah kartu terbanyak.

Pak Bos ingin sekali mendapatkan kaos Exclusive Carbon tersebut. Bantulah Pak Bos dengan memberitahu jumlah kartu terbanyak dari kombinasi kartu S' yang memenuhi syarat.

Input Format

n k
m1 m2 m3 ... mn
n: length kartu 
k: bilangan pembagi 
m1, m2, m3, ..., mn: bilangan integer kartu S

Output Format

Jumlah kartu terbanyak dari kombinasi kartu S' yang memenuhi syarat. Sample Input 1

4 3
1 7 2 4

Sample Output 1

3

Explanation

Kombinasi dengan jumlah kartu terbesar yang mungkin adalah {1, 7, 4}. Karena tidak ada jumlah 2 bilangan yang dapat dibagi habis oleh k = 3.

• 1 + 7 = 8, 8 tidak dapat dibagi habis oleh 3

• 4 + 7 = 11, 11 tidak dapat dibagi habis oleh 3

• 1 + 4 = 5, 5 tidak dapat dibagi habis oleh 3 Bilangan 2 tidak dapat dimasukkan dalam set kartu karena akan membuat terdapatnya jumlah 2 bilangan yang dapat dibagi habis oleh k = 3.

• 1 + 2 = 3, 3 dapat dibagi habis oleh 3

• 7 + 2 = 9, 9 dapat dibagi habis oleh 3

• 4 + 2 = 6, 6 dapat dibagi habis oleh 3 Karena jumlah kartu dari subset {1, 7, 4} adalah sebanyak 3, berilah output 3.

Constraints

• 1 ≤ n ≤ 105
• 1 ≤ k ≤ 100
• 1 ≤ mi ≤ 109

hology_penyisihan.md

No. 1: The secret of stone cave

Description

Suatu hari, Dani menyusuri sebuah goa. Dia melihat N buah batu yang sangat indah. Dia tak henti-hentinya terpukau dengan batu yang ada di sana. Ia pun mulai berpikir untuk membawa pulang batu-batu tersebut dan menjualnya. Namun, ia tidak tahu berapa harga jual di pasaran dari batu-batu tersebut.

Kemudian ia keluar dari goa untuk mencari informasi mengenai batu-batu tersebut. Setelah ia berkeliling untuk mencari tahu dan juga mencarinya di internet, ternyata batu-batu tersebut mempunyai nilai keindahan yang jika semakin tinggi, semakin mahal. Nilai keindahan semua batu yang ia temui dia catat dalam list X dengan nilai keindahan masing-masing Xi berupa integer. Karena ia tidak memiliki cukup tempat penyimpanan untuk membawa itu semua, asumsukan semua beratnya masing-masing 1 Kg, ia hanya bisa membawa pulang K Kg batu.

Beberapa saat kemudian, ada sebuah insiden yang terjadi. goa tersebut mulai runtuh dan menutup pintu masuk ke goa tersebut. Untungnya, ada satu pintu lagi yang bisa ia gunakan untuk keluar. Namun, karena goa tersebut akan rata dengan tanah, dia perlu secepat mungkin menghitungnya. Berapa jumlah nilai keindahan maksimumn yang bisa ia bawa pulang ?

Input Format

Baris pertama berisi N. Baris selanjutnya berisi N buah batu dengan nilai Xi. Baris terakhir merupakan K.

Output Format

jumlah nilai keindahan yang bisa ia bawa pulang.

Sample Input

5
1 2 3 4 5
3

Sample Output

12

Constraints

• 1 ≤ K ≤ 100000
• 1 ≤ N ≤ 100000
• 0 ≤ Xi ≤ 100

No. 2: The Power of Friend's Bonds

Description

Suatu hari, Nanta pergi ke suatu kota untuk berjalan-jalan. Ia amat menikmati perjalanan tersebut. Namun, di tengah perjalanan, ia secara tidak sengaja menabrak mobil orang. Untunglah tidak ada korban jiwa dalam peristiwa tersebut. Namun, mobil tersebut mengalami rusak parah sehingga sang pemilik mobil menuntut ganti rugi kepada Nanta. Ia pun bingung bagaimana ia bisa mendapatkan uang tersebut.

Kemudian Nanta pergi ke kosan temennya yang amat sangat kaya, si Eka. Karena ia sangat dermawan, Eka memberikannya N buah kantong uang yang isinya sama semua dan menyusunnya dari kiri ke kanan, dan juga ia menomorinya dengan beberapa bilangan. Bisa saja beberapa kantong tersebut dinomori dengan angka yang sama dengan kantong lainnya.

Nanta bisa membawa beberapa kantong jika dan hanya jika kantong-kantong yang diambil tersebut membentuk list terurut berdasarkan posisi awal kantong tersebut sebelum diambil dan bilangan dari kantong yang telah diurut tersebut juga terurut naik. Tentukan berapa banyak kantong uang yang bisa dibawa pulang olehnya untuk mengganti rugi kecelakaan tersebut.

Input Format

Baris pertama berisi N. Baris kedua berisi nomor dari N buah kantong.

Output Format

Jumlah maksimum kantong yang bisa dibawa pulang.

Sample Input

5
1 2 1 4 5

Sample Output

4

Explanation

Terlihat bahwa kantong-kantong yang bisa dibawa oleh Nanta adalah 1,2,4,5 dengan kantong nomor 1 adalah kantong yang paling kiri.

Constraints

• 1 ≤ N ≤ 1000
• 1 ≤ nomor kantong < 100

No. 3: What You Type isn't What You Get

Description

Pak Eko adalah seorang Administrator Server. Suatu ketika Server terkena hack. Semua teks pada servernya nya berubah. Pak Eko ingin mengembalikan teksnya kembali akan tetapi dia tidak mengetahui caranya. Kebetulan dia mendapatkan beberapa contoh dari teks yang terenkripsi dan teks aslinya.

Ubah String inputan berikut. String inputan dijamin hanya terdiri dari sebuah bilangan dan karakter a-z lowercase dan string output hanya berisi a-z lowercase.

Input Format

Sebuah String, sebut saja S dengan ukuran S 2 hingga 400

Output Format

String hasil ubah

Sample Input 1

1abc

Sample Output 1

yza

Sample Input 2

fg2h

Sample Output 2

bcd

No. 4: Lagu Apa ini?

Description

Seperti biasa, Kegiatan Okza ketika sedang gabut di kosan adalah scroll timeline Line. Pada suatu hari ketika ia sedang scroll timeline ia menemukan sebuah potongan video musik. Okza langsung mencari judul dari lagunya, Sayang sekali Ia tidak mendapatkannya.

Akan tetapi, dia tidak kehabisan akal. Kebetulan dia mempunyai sebuah aplikasi yang dapat mengubah suara tersebut menjadi tangga nada diatonik. Tangga nada diatonik adalah tangga nada yang berisi 12 semitone. Tangga nada tersebut direpresentasikan menjadi angka sebagai berikut.

C	C#	D	D#	E	F	F#	G	G#	A	A#	B	C'	C#'
1	2	3	4	5	6	7	8	9	10	11	12	13	14

Range nada yang tersedia pada kasus ini adalah 5 oktaf (1 oktaf = 12 semitone). dari C1 sampai B5

Setelah melakukan browsing dia mendapatkan N buah lagu yang sudah diubah menjadi tangga nada. Okza terlalu malas untuk mencari satu satu sehingga menyuruh anda untuk membuat program untuk mencari lagu yang cocok Si dengan potongan lagu P pada data tersebut. Selain itu anda juga diminta untuk menampilkan kapan P muncul di S

P dianggap cocok dengan Si apabila P adalah sublist dari Si (semua element P dengan berada pada S dengan urutan yang sama)

Sebuah lagu yang sama belum tentu memiliki nada dasar yang sama pula

C	D	F	E
E	F#	A	G#

adalah potongan nada yang sama walaupun berbeda nada dasar

Input Format

Pada baris pertama terdapat 1 buah integer A diikuti dengan A buah bilangan bulat yang menjadi elemen dari P (P1,P2,...,Pa)

baris kedua berisi bilangan bulat N

N baris berikutnya berisi 1 integer B kemudian diikuti dengan B buah bilangan bulat yang menjadi elemen dari (S1, S2, ..., Sb)

Output Format

Terdapat N baris

Keluarkan Index dimana Potongan lagu P ditemukan pada Lagu S

Jika tidak ditemukan keluarkan Not Found

Sample Input 1

4 5 10 9 7
3
12 16 19 1 8 10 4 5 10 9 7 8 8
9 12 3 1 5 1 2 15 6 9
10 1 2 7 8 13 12 10 8 9 1

Sample Output 1

6
Not Found
3

Explanation

Pada sample input 1 diatas

baris ke 1

16 19 1 8 10 4 5 10 9 7 8 8
               5 10 9 7

ditemukan pada index ke 6 (index dimulai dari 0)

baris ke 3

1 2 7 8 13 12 10 8 9 1
      5 10 9  7

ditemukan pada index ke 3. bisa dilihat bahwa P dengan S berbeda nada dasar

Constraints

• 1≤N<1000
• 1≤A<10000
• 2≤B<10000
• 1≤S1,P,Pk≤60

No. 5: Palindrom

Sebuah teks dikatakan Palindrom apabila: jika susunan hurufnya dibalik menghasilkan teks yang sama dengan teks aslinya. Contoh:

• katak
• kodok
• kasur rusak

Pada suatu hari saat sedang meriset tentang teks palindrom anda menemukan sebuah jurnal tentang angka palindrom. Angka tersebut dianggap palindrom apabila digit biner penyusun angka tersebut membentuk palindrom. Contoh:

• 0 : 0 (palindrom)
• 1 : 1 (palindrom)
• 5 : 11 (palindrom)
• 4 : 10 (tidak palindrom)
• 9 : 101 (palindrom)
• dan seterusnya

Dr. Bernard Mahfouz selaku dosen pembimbing anda menantang anda untuk menemukan angka palindrom terbesar yang dapat diambil dari sebuah Bilangan Bulat X Contoh :

946 (1110110010)

angka palindrom terbesar yang dapat diambil adalah

27 (11011) 

Input Format

Baris pertama adalah bilangan bulat T menandakan jumlah test case

T baris berikutnya adalah Xi

Output Format

T baris bilangan yaitu angka palindrom terbesar dari tiap X

Sample Input

6
512
511
495
247
347
2008

Sample Output

1
511
495
119
45
31

Constraints

• 1≤T<200
• 0≤X<10^15

No. 6 (Singkatan)

Description

Singkatan dapat dibentuk dengan 2 cara pertama dengan mengambil huruf pertama dari Setiap Kata misal National University Singapore (NUS). bisa juga dengan menghilangkan beberapa huruf dan membentuk singkatan misal House Of Technology (HOLOGY).

Tugas anda disini adalah mengecek apakah singkatan tersebut valid apa tidak. Singkatan dianggap valid terhadap kalimat aslinya apabila kita bisa menyisipkan maksimal K character diantara huruf pada singkatan dan menghasilkan kalimat yang sama persis.

Contoh :

HOLOGY K = 10
House Of Technology
H[ouse ]O[f techno]LOGY

menghasilkan keluaran valid

apabila K = 7, maka hasilnya tidak valid

Input Format

Bilangan bulat T yaitu jumlah Testcase

untuk setiap T terdapat 2 baris

baris pertama adalah String S yaitu singkatan dan integer K

baris kedua adalah Kalimat

Output Format

Untuk setiap T

valid atau tidak valid

Sample Input

3
HOLOGY 10
House Of Technology
FILKOM 9
Fakultas Ilmu Komputer 
UB 7
Universitas Brawijaya

Sample Output

Case #1: valid
Case #2: valid
Case #3: tidak valid

Batasan

• 1 <= T <= 1000
• 1 <= K <= 50
• 1 <= length(S) <= 250

No. 7: Let’s Find the root

Description

Diberikan sebuah persamaan polinomial f(x)=axn+bxn-1+...+c dan bilangan x1x1 dan x2x2, tentukan akar persamaan diantara nilai x1x1 dan x2x2.

Input Format

Inputan terdiri dari beberapa testcase sejumlah t. Baris pertama berisi t. Baris kedua adalah n yang merupaka derajat tertinggi dari polinomial tersebut Baris selanjutnya berisi n buah inputan yang menunjukkan konstanta persamaan yang ditulis secara berurutan dimulai dari derajat tertinggi.

Baris terakhir berisi bilangan x1x1 dan x2x2.

Output Format

Sebuah akar persamaan yang dibulatkan ke integer terdekat. Dijamin hanya ada satu akar persamaan diantara x1x1 dan x2x2.

Sample Input 1

1
2
1 2 1
-1 -3

Sample Output 1

-1

Sample Input

1
2
1 6 9
-2 -3

Sample Output

-3

Explanation

Pada inputan pertama merupakan konstanta dari persamaan f(x)=x2+2x+1. Sementara yang kedua adalah konstanta dari persamaan f(x)=x2+6x+9.

Constraints

• 1≤t≤100
• 1≤n≤41≤n≤4
• x1x1 dan x2x2 muat dalam integer C/C++/Java.

No. 8: Applying Principle of Economy in Real Life

Description

Agus sedang berbelanja di sebuah supermarket yang amat lengkap segala kebutuhan hidup. Mulai dari makanan, minuman, pakaian, dan lain-lain. Agus pun kemudian memutuskan untuk membeli beras mengingat stok beras mulai habis. Agus pun sampai pada bagian beras dan ia pun kebingungan.

Ternyata masing-masing merek beras hanya tinggal 1 saja. Harga masing-masing beras tersebut tertulis dalam set A dan berat bersih beras tersebut tertulis dalam set B. Harga sebuah beras ke-i adalah Ai dan berat bersihnya adalah Bi. Di dalam supermarket tersebut, hanya ada N buah merek beras yang tersisa.

Agus sebelumnya telah menganggarkan uang sejumlah M yang digunakan untuk membeli beras. Tentunya Agus ingin mendapatkan jumlah beras sebanyak mungkin. Dan Agus tahu anda adalah programmer yang hebat. Dia pun meminta anda untuk membuat program yang dapat memberi tahu berapa maksimum jumlah beras yang bisa ia bawa pulang.

Input Format

Baris pertama berisi N. Baris kedua berisi Ai dengan nilai i 1 hingga N. Baris ketiga berisi Bi dalam satuan Kilogram. Baris terakhir merupakan M.

Output Format

jumlah maksimum nilai-nilai dari B.

Sample Input

3
10 20 30
60 100 120
50

Sample Output

220

Explanation Dengan M=50, Agus bisa membawa pulang beras dengan biaya 20 dan 30 dengan total berat 220 Kg.

Constraints

• 1≤N<10001≤N<1000
• 1≤1≤Ai, Bi≤200

No. 9 (Eggs Tower) Deskripsi

Di suatu desa pokopek baru saja diresmikan sebuah dan satu satunya museum telur di dunia. Museum tersebut menampilkan (mempamerkan) SATU buah telur langka pada setiap lantainya dimulai dari lantai 1 sampai dengan lantai ke-n. Seorang pencuri profesional yang sudah menjadi buronan bertahun tahun pun tertarik pada telur langka tersebut.

Karena penjagaan yang sangat ketat dan juga ukuran telur yang besar (sangat besar dibanding dengan telur biasa) pencuri tersebut hanya bisa mencuri tepat satu buah telur dari museum tersebut, dengan cara menjatuhkan telur tersebut keluar jendela ke truk yang sudah menunggunya di luar gedung tersebut.

Setiap telur pada setiap lantai gedung tersebut mempunyai berat dan konstruksi yang sama persis, tetapi telur pada lantai atas lebih langka dan lebih berharga dibanding yang ada dibawahnya (telur lantai 2 lebih berharga dibanding lantai 1,dst). Sudah pasti pencuri tersebut ingin mengambil 1 telur yang paling berharga, tetapi masalah pun timbul, ya, telur yang dijatuhkan bisa saja pecah!

Karena tidak mau usahanya sia sia, akhirnya ia mencari cara agar dapat mengetahui telur paling berharga yang tidak akan pecah saat dijatuhkan. pada toko souvenir pencuri tersebut membeli 2 buah telur yang sama persis dengan yang ada di museum (hanya replika dan tak bernilai harganya) Rencananya adalah untuk mencoba menjatuhkan telur tersebut sehingga ia mengetahui lantai tertinggi agar telur yang dijatuhkan tidak pecah namun timbul masalah baru, ia tidak dapat menjatuhkan telur pada setiap lantai karena akan menarik perhatian dari para penjaga. tugas anda adalah untuk menentukan jumlah percobaan paling sedikit yang dibutuhkan pencuri tersebut agar mengetahui lantai paling tertinggi dimana telur yang ia curi tidak akan pecah. perlu diingat ia tidak bisa melanjutkan percobaan jika kedua telurnya sudah pecah!

Input

Satu angka yang menyatakan banyak lantai pada gedung tersebut (1 <= n <= 1000)

Output

jumlah percobaan paling sedikit yang diperlukan untuk mengetahui lantai tertinggi yang dapat ditahan oleh telur tersebut agar tidak pecah

Example Input 1

3

Example Output 1

2

Example Input 2

10

Example Output 2

4

No. 10: (Tidak ada Kerjaan)

Deskripsi

Pada suatu jalan terdapat beberapa gedung yang berderet dan memiliki tinggi yang beragam. Pak Bos tidak punya kerjaan dan ingin mencari persegi atau persegi panjang terbesar yang terbentuk dari gedung-gedung tersebut. lebar dari masing-masing gedung adalah 1.

dari gambar diatas ukuran yang terbesar adalah 12

dari gambar diatas ukuran yang terbesar adalah 14

Format Input

Baris pertama adalah jumlah gedung X

X integer selanjutnya adalah tinggi masing-masing gedung

Contoh Input

12
1 3 6 3 2 2 3 3 1 0 3 6

Contoh Output

14

Contoh Input

11
1 2 3 4 2 3 5 2 1 0 8

Contoh Output

14

Contoh Input

7
5 1 1 1 1 1 0

Contoh Output

6

Batasan

• 1≤X<1000 semua tinggi gedung tidak sampai 100