final itb senior programming contest 2011€¦ · web viewgajah-gajah peliharaan pak ganesh...

Qt ITB Programming Contest 2011

BABAK FINAL ITB SENIOR PROGRAMMING CONTEST

Rabu, 9 November 2011

ITB Programming Contest 2011

Final ITB Senior Programming Contest 2011

Kelereng Pak GaneshTime Limit 3 s

Memory Limit 128 MB

Deskripsi PermasalahanGajah-gajah peliharaan Pak Ganesh sekarang sudah bertambah pintar. Mereka menciptakan permainan untuk mereka sendiri karena bosan lantaran dikurung seharian di dalam kandang gajah oleh Pak Ganesh.

Permainan itu menggunakan sejumlah kelereng berwarna-warni yang disusun berderetan dalam satu garis sedemikian rupa sehingga tidak ada celah diantara kelereng-kelereng tersebut. Warna kelereng-kelereng tersebut beragam, yaitu dari ‘a’..’z’. Permainan dimainkan oleh 1 ekor gajah. Gajah akan menembak sebuah kelereng ke arah satu kelereng di dalam deretan kelereng yang sudah tersedia. Bila sebuah kelereng ditembakkan ke kelereng urutan ke-i di deretan kelerang yang tersedia, maka kelereng yang ditembakkan tersebut akan menempati tepat setelah kelereng ke-i. Hal ini mengakibatkan kelereng yang baru ditempatkan tidak mungkin menempati posisi paling depan. Kelereng yang ditembakkan harus selalu berwarna sama dengan kelereng ke-i tersebut.

Misalkan diketahui deretan kelereng awal :

abcde

Sebuah kelereng ditembakkan ke kelereng ke-2, sehingga deretan kelereng yang baru menjadi :

abbcde

Karena gajah Pak Ganesh terus menerus menembakkan kelereng, deretan kelereng pun menjadi sangat panjang dan tidak dapat dimainkan di dalam kandang mereka. Maka, mereka pun membuat peraturan sebagai berikut :

● Deretan kelereng yang berwarna sama akan pecah bila jumlah kelereng berwarna sama yang letaknya berderetan (tanpa diselingi oleh kelereng berwarna lain) berjumlah minimal n buah dan salah satunya ditembakoleh gajah Pak Ganesh atau merupakan deretan hasil penyatuan.

● Bila sejumlah kelereng pecah, maka deretan kelereng sebelum dan deretan kelereng sesudah kelereng yang pecah akan menyatu

● Deretan kelereng yang pertama disusun (input) tidak dapat pecah bila belum ditembak. ● Kelereng yang menyatu dari hasil pecahan kelereng sebelumnya dapat langsung pecah

bila kelereng yang menyatu memiliki warna yang sama dan lebih besar dari n.

Misalkan diketahui kelereng akan pecah bila berjumlah minimal 3 buah

abbcddccdeee

Kelereng ditembakkan ke kelereng urutan ke-5 :

abbcdddccbeee -> abbcccbeee -> abbbeee -> aeee



Perhatikan bahwa kelereng ‘e’ yang berada di ujung tidak pecah walau berjumlah 3 buah karena tidak terkena pengaruh tembakan Gajah Pak Ganesh.

Untuk setiap kasus uji, diberikan sebuah deretan kelereng (S), jumlah minimum kelereng agar dapat pecah (n) , dan i yang merupakan indeks dimana kelereng akan ditembakkan.

Format MasukanBaris pertama input merupakan sebuah integer T (1 <= T <= 100) yang menyatakan jumlah kasus uji. Untuk setiap kasus dimulai dengan sebuah string tidak kosong dengan panjang kurang dari 10000, yang merupakan deretan kelereng. Baris selanjutnya terdiri dari 2 bilangan integer N (2<= N <= 10) dan Q (1<= Q <= 100). Q baris selanjutnya merupakan target kelereng yang ditembak oleh Gajah Pak Ganesh. Dijamin kelereng selalu ditembakkan ke salah satu kelereng yang ada dan selalu berwarna sama dengan kelereng ke-i tersebut.

Format KeluaranUntuk setiap kasus, output sebuah baris “Case #X: P S” dimana X adalah nomor kasus, diikuti P dan S. P adalah jumlah kelereng yang pecah dan S adalah deretan kelereng setelah kelereng-kelereng ditembakkan.

Contoh Masukan2abccd3 3 311abbcdeeef4 32 34

Contoh KeluaranCase #1: 6 bdCase #2: 8 acdf

PenjelasanKasus uji 1 : abccd -> abcccd -> abd -> aabd ->aaabd -> bdJumlah kelereng pecah : 6Deretan kelereng baru : bd

Kasus uji 2 :abbcdeeef -> abbbcdeeef ->abbbbcdeeef -> acdeeef -> acdeeeef -> acdf



Lomba Lari Gawang GilaTime Limit 8 s

Memory Limit 128 MB

Deskripsi PermasalahanPak Ganesh sedang mengikuti lomba lari gawang. Lomba ini diadakan di sebuah lintasan berbentuk lingkaran yang memiliki W jalur lari, dengan K rintangan yang harus dilompati pada tiap putarannya. Pak Ganesh juga mengetahui banyaknya lompatan yang harus dilakukan dalam keseluruhan lomba lari adalah N. Dengan kata lain, setelah melompati rintangan ke-K, seorang pelari akan kembali ke tempat awal dan harus melompati kembali rintangan ke-1 (dan rintangan berikutnya) apabila total rintangan yang sudah dilompati belum mencapai N. Rintangan terakhir yang harus dilompati untuk menyelesaikan lomba adalah rintangan ke-K.

Lomba lari gawang ini memiliki banyak keunikan, seperti setelah melompati satu rintangan, peserta diperbolehkan untuk berpindah jalur ke jalur tepat di kiri atau kanan dari jalurnya semula. Selain itu, semua peserta diperbolehkan untuk memilih jalur tempat mulainya sendiri, dan sebagai tuan rumah Pak Ganesh mendapat kesempatan pertama untuk memilih jalur start. Semua pelari dilarang untuk keluar lintasan, dan dalam satu jalur boleh saja terdapat lebih dari satu pelari, kecuali saat start. Pelari juga diperbolehkan finish di jalur yang berbeda dengan jalur tempat mereka start.

Pak Ganesh bisa berlari sangat cepat dibandingkan dengan lawan-lawannya, tetapi kemampuan melompatnya tidak seberapa baik. Karena yang dia takutkan hanyalah bagian melompat saja, maka Pak Ganesh mau mencari tahu berapa total tingkat kesulitan rintangan minimal yang harus dia lompati serta jalur start lari yang harus dia pilih untuk mendapatkan tingkat kesulitan minimal tersebut.

Format MasukanBaris pertama input merupakan sebuah integer T (1 <= T <= 20) yang menyatakan jumlah kasus uji. Untuk setiap kasus dimulai dengan 3 buah integer, yaitu N (K<=N<=10^15), K (2<=K<=50) serta W (2<=W<=30). K baris berikutnya masing-masing berisi W bilangan, yaitu tingkat kesulitan rintangan Wi untuk setiap jalur. Setiap tingkat kesulitan rintangan dijamin berada dalam rentang 1...1000. Dijamin N akan habis dibagi oleh K.

Format KeluaranUntuk setiap kasus, output sebuah baris “Case #X: Y Z” dimana X adalah nomor kasus. Y adalah total tingkat kesulitan rintangan minimal untuk menyelesaikan lomba tersebut dengan memenuhi peraturan yang ada. Z adalah jalur start yang harus dipilih Pak Ganesh untuk mendapatkan total minimal itu.

Apabila ada lebih dari satu pilihan jalur yang mungkin, keluarkan nomor jalur yang paling kecil. Penomoran jalur dimulai dari nomor 1 untuk jalur paling kiri. Dijamin total tingkat kesulitan yang terbesar tidak akan melebihi batasan untuk tipe data signed 64-bit integer.

Contoh Masukan24 2 35 2 62 3 14 2 21 1



1 1

Contoh KeluaranCase #1: 6 2Case #2: 4 1

PenjelasanBerikut adalah peta tingkat kesulitan loncatan beserta dengan treknya, sebetulnya trek berbentuk lingkaran, untuk mempermudah penggambaran, trek sudah "diluruskan" serta ditambah panjangnya sesuai dengan banyaknya putaran yang diperlukan (4 / 2 = 2, artinya ada 2 putaran) :

FINISH

| | |

LAP 22 3 1| | |5 2 6| | || | |

LAP 12 3 1| | |5 2 6| | |

START

Jalur dengan tingkat kesulitan minimal dari tempat start adalah kolom 2-3-2-3. Tingkat kesulitan lompatan adalah 2+1+2+1 = 6.



SubstreeTime Limit 3 s

Memory Limit 128 MB

Deskripsi PermasalahanDiberikan sebuah tree yang memiliki tepat N-1 bidirectional edge yang masing-masing diberi label suatu huruf kecil.

Kita definisikan suatu path dari graph tersebut sebagai suatu urutan edge (tanpa duplikat) di mana edge pertama menghubungkan root dengan node lain, yang kemudian dihubungkan dengan edge kedua dengan node lainnya, dan seterusnya.

Ada berapa urutan edge di mana string yang didapat dari mengkonkat semua label dari edge-edge di urutan edge tersebut (secara berurutan dari edge pertama sampai dengan edge terakhir) memiliki string P sebagai substringnya? (substringnya harus continuous)

Format MasukanBaris pertama input merupakan sebuah integer T (1 <= T <= 20) yang menyatakan jumlah kasus uji. Untuk setiap kasus dimulai dengan sebuah integer N (2 <= N <= 200,000). N-1 baris berikutnya masing masing berisi A B C, (1 <= A < B <= N, 'A' <= C <= 'Z') yang berarti ada edge yang menghubungkan node A dengan node B dan memiliki label C. Node 1 ialah node root. Baris selanjutnya ialah string P di mana setiap karakternya adalah antara 'A'-'Z' dan panjangnya antara 1 sampai 200,000 karakter.

Format KeluaranUntuk setiap kasus, output sebuah baris “Case #X: Y” dimana X adalah nomor kasus, dan Y adalah banyaknya urutan edge seperti di soal.

Contoh Masukan161 2 B2 3 A3 4 B4 5 A3 6 BAB21 2 AB

Contoh KeluaranCase #1: 3Case #2: 0

Penjelasan KeluaranUntuk kasus uji pertama, ketiga urutan edge tersebut menghubungkan node-node sebagai berikut:1-2-3-41-2-3-4-51-2-3-6



Love Hate GraphTime Limit 3 s

Memory Limit 128 MB

Deskripsi PermasalahanSebuah makhluk dari planet X mengamati perilaku manusia di bumi dan dengan cepat menyimpulkan bahwa dua orang manusia bisa saling menyukai atau saling membenci. Tetapi tidak mungkin ada dua orang manusia yang bisa saling membenci dan saling menyukai sekaligus.

Karena si makhluk ini belum tahu seluk-beluk manusia secara mendalam, dia secara sederhana hanya menyimpulkan bahwa hubungan suka dan benci itu memenuhi aturan sebagai berikut:

● Suka dan benci bersifat komutatif. Artinya jika a benci b, maka b benci a. Jika a suka b, maka b suka a.

● Jika a suka b, dan b suka c, maka a suka c.● Jika a suka b, dan b benci c, maka a benci c.● Jika a benci b, dan b benci c, maka a suka c.

(Tentu saja observasi si makhluk ini kurang akurat, karena dalam cinta segitiga di dunia nyata, bisa saja a suka c dan b suka c namun a membenci c. Tapi untuk soal ini, kita hanya peduli dengan kesimpulan si makhluk ini)

Si makhluk ini memperhatikan hubungan di antara N manusia yang dinomori 1 sampai dengan N. Pada awalnya si makhluk ini tidak mengetahui hubungan apapun di antara pasangan manusia manapun. Perlahan-lahan si makhluk akan mendapatkan informasi baru tentang hubungan di antara manusia-manusia. Anda diminta membantu si makhluk ini menjawab pertanyaan-pertanyaan tentang hubungan manusia diberikan data yang dia punyai pada saat tersebut.

Format MasukanBaris pertama berisi dua buah bilangan bulat, N (1 ≤ N ≤ 50000) dan Q (1 ≤ Q ≤ 100000) di mana Q adalah banyaknya query. Setiap baris berikutnya berisi sebuah query. Ada beberapa jenis query:

● ‘L’ diikuti dua buah bilangan bulat i dan j (1 ≤ i, j ≤ N, i ≠ j). Artinya, si makhluk mendapatkan informasi bahwa i menyukai j.

● ‘H’ diikuti dua buah bilangan bulat i dan j (1 ≤ i, j ≤ N, i ≠ j). Artinya, si makhluk mendapatkan informasi bahwa i membenci j.

● ‘Q’ diikuti dua buah bilangan bulat i dan j (1 ≤ i, j ≤ N, i ≠ j). Ini adalah pertanyaan: apakah hubungan antara i dan j diberikan informasi yang sudah ada sampai saat ini?

Format KeluaranUntuk setiap query yang diberikan, keluarkanlah sebuah baris tanggapan.

Jika quey berisi informasi (diawali ‘L’ atau ‘H’), keluarkanlah salah satu dari:

● ‘OK’ jika informasi sudah diterima dan informasi tidak menimbulkan kontradiksi di love-hate graph yang telah terbentuk. Informasi ini mungkin saja redundan (hanya mengulangi hubungan yang sudah dapat dideduksi dari informasi-informasi yang telah ada)



● ‘IMPOSSIBLE’ jika informasi menimbulkan kontradiksi di love-hate graph yang telah terbentuk. Jika Anda menemui kasus ini, informasi hubungan ini dapat diabaikan setelah mengeluarkan ‘IMPOSSIBLE’.

Jika query merupakan pertanyaan (diawali dengan ‘Q’), keluarkanlah sebuah baris yang berisi:

● ‘L’ jika i dan j dalam pertanyaan memiliki hubungan ‘suka’● ‘H’ jika i dan j dalam pertanyaan memiliki hubungan ‘benci’● ‘U’ jika hubungan i dan j belum bisa disimpulkan dari informasi yang ada atau tidak memiliki

hubungan

Contoh Masukan10 12L 1 2L 3 4Q 1 4H 2 3H 4 5Q 1 5L 1 4H 1 4H 6 7H 7 8L 2 7Q 5 6

Contoh KeluaranOKOKUOKOKLIMPOSSIBLEOKOKOKOKH



Kotak dan KartuTime Limit 1 s

Memory Limit 128 MB

Deskripsi PermasalahanPak Ganesh memiliki K kartu serta B kotak, dimana setiap kotak dapat memuat maksimal C kartu. Pak Ganesh ingin menyimpan kartu-kartu tersebut di dalam kotak-kotaknya, tetapi Pak Ganesh tidak menyukai kotak yang ada tempat kosongnya, karena akan menimbulkan bunyi tidak enak bila digerakkan. Karena itu Pak Ganesh mendefinisikan keburukan sebuah kotak sebagai kuadrat dari banyaknya tempat dalam kotak tersebut yang tidak terpakai. Untuk contoh, bila sebuah kotak bisa memuat 10 kartu tapi hanya diisi 7 kartu, maka keburukan kotak tersebut adalah (10-7)^2 = 9. Pak Ganesh ingin tahu berapa minimal total keburukan semua kotak yang ada. Bantulah Pak Ganesh dalam menghitungnya.

Format MasukanBaris pertama input merupakan sebuah integer T (1 <= T <= 100) yang menyatakan jumlah kasus uji. Untuk setiap kasus terdapat 3 bilangan, yaitu K (1<=K<=10^18), B (1<= B <=10^10), dan C (1<=C<=10^4).

Format KeluaranUntuk setiap kasus, output sebuah baris “Case #X: Y” dimana X adalah nomor kasus, dan Y adalah total keburukan semua kotak yang minimal. Dijamin hasilnya dapat dimuat dalam 64-bit signed integer.

Contoh Masukan27 1 101 1 1




Pool FillingTime Limit 30 s

Memory Limit 128 MB

Deskripsi PermasalahanPak Ganesh sangat gemar membuat permainan komputer berbasis blok. Kali ini, ia ingin membuat sebuah permainan yang disebut dengan Pool Filling. Dalam permainan ini, pemain diberikan sebuah area berupa susunan M x N blok, dengan beberapa blok dibuat sebagai penghalang atau dindingdanblok-bloklainnyamerupakantanahkosong. Susunan penghalang di area tersebutdapat beragam. Salah satu contohnya sebagai berikut.#..###.#..##....

Denganadanyapenghalangtersebut, adaruangan (bisasatuataulebih) yang terbentuk di area tersebut.Pak Ganesh ingin membuatkolamsebanyakjumlahruangan yang ada. Pak Ganesh akanmengisisetiapruangantersebutdengan air dengan cara membuat sebuah sumber air di setiap ruangan. Setelah memilih sumber air untuk setiap ruangan, pengisian mulaidijalankan. Proses pengisian berlangsung secara bertahap (sebutsaja 1 tahap membutuhkanwaktu 1 detik). Pada setiap tahap, blok-blok yang berada di kanan, kiri, atas, atau bawah (selain blok dinding) dari blok yang berisi air akan ikut terisi air. Proses ini berlangsung hingga semua blok kosong di kolam terisi dengan air (dengan kata lain, semua blok kosong berubah menjadi blok air). Pemain yang dapat mengisi kolam dengan waktu yang paling sedikit adalah pemenangnya.

Diberikan N, tentukan waktu minimum yang dibutuhkan untuk mengisi kolam.

Format MasukanBaris pertama input merupakan sebuah integer T (1 <= T <= 11) yang menyatakan jumlah kasus uji. Setiap kasus dimulai dengan 2 buah integer R dan C (1 <= R,C<= 100). Setiap R baris berikutnya terdiri dari C karakter yang menandakan kosong atau penghalang.

Format KeluaranUntuk setiap kasus, output sebuah baris “Case #X: Y” dimana X adalah nomor kasus dan Y adalah waktu minimum untuk mengisi kolam.

Contoh Masukan24 4#..###.#..##....3 2##..##

Contoh OutputCase #1: 2Case #2: 1



Rekonstruksi ArrayTime Limit 2 s

Memory Limit 128 MB

Deskripsi PermasalahanPak Ganesh memiliki permainan baru. Permainan ini sangat sederhana namun cukup mengasah otak. Beginilah permainannya.

Ada sebuah array yang terdiri atas N bilangan bulat (1 ≤ N ≤ 100.000) dengan index 1 sampai dengan N. Elemen ke-i berisi bilangan Ei (-2^30 ≤ Ei ≤ 2^30). Namun, Pak Ganesh tidak mengetahui berapakah nilai Ei ini. Pak Ganesh hanya diberikan informasi jumlah elemen-elemen subarray-subarray.

Lebih tepatnya, Pak Ganesh diberikan N buah informasi, di mana informasi ke-i menyatakan bahwa jumlah elemen-elemen dari index ke Ai sampai denganE Bi (inklusif) (1 ≤ Ai ≤ Bi ≤ N) adalah Ci (-10000 ≤ Ci ≤ 10000). Hanya dengan informasi ini, Pak Ganesh diminta merekonstruksi elemen-elemen pada array.

Pak Ganesh kesulitan memainkan permainan ini sehinga dia meminta Pak Ganesh untuk membuatkan program untuknya.

Format MasukanBaris pertama berisi banyaknya kasus uji, P (1 ≤ P ≤ 5). Untuk setiap kasus uji, format input adalah sebagai berikut.

Baris pertama berisi sebuah bilangan bulat N. N baris berikutnya masing-masing berisi tiga buah bilangan bulat: Ai, Bi, Ci.

Dijamin bahwa tidak mungkin ada kontradiksi di dalam informasi-informasi yang diberikan.

Format KeluaranUntuk setiap kasus, output sebuah baris “Case #X: Y1 ... YN” dimana X adalah nomor kasus, dan Y1...YN berisi N buah elemen dari E1 hingga EN. Jika ada cukup informasi untuk merekonstruksi nilai Ei, keluarkanlah nilai Ei. Jika tidak ada cukup informasi untuk merekonstruksi nilai Ei, keluarkanlah ‘?’ pada posisi tersebut.

Contoh Masukan272 3 54 5 56 7 51 4 03 6 03 4 02 4 -571 2 32 3 51 3 65 6 115 7 18



1 5 154 5 9

Contoh KeluaranCase #1: 5 -5 10 -10 15 -15 20Case #2: 1 2 3 ? ? ? 7

PenjelasanKasus uji 1 cukup jelas. Tidak ada array lain yang memenuhi informasi jumlah subarray yang diberikan.

Kasus uji 2: elemen ke-4, ke-5, dan ke-6 tidak bisa ditentukan dengan pasti. Contoh beberapa kemungkinan array yang dapat memenuhi informasi yang diberikan:

1 2 3 4 5 6 71 2 3 5 4 7 71 2 3 6 3 8 7



Photo CroppingTime Limit 2 s

Memory Limit 128 MB

Deskripsi PermasalahanMembuat algoritma image cropping yang sangat general sehingga dapat dipakai untuk mengautomatisasi cropping untuk berbagai logo dan foto tidaklah mudah. Misalkan ada sebuah foto di Facebook yang berukuran W x H (1 ≤ W ≤ 1000000, 1 ≤ H ≤ 1000000). Sebuah aplikasi iPad ingin memakai foto tersebut di layout mereka yang ukurannya terbatas.

Persisnya, mereka ingin meng-crop foto itu menjadi berukuran P x Q (1 ≤ P ≤ 800000, 1 ≤ Q ≤ 800000) tanpa melakukan pembesaran / pengecilan gambar (scaling). Lebih persisnya, Anda diminta mengambil koordinat (x1, y1) dan (x2, y2) (0 ≤ x1< x2 ≤ W, 0 ≤ y1< y2 ≤ H) pada foto asli, di mana x2 – x1 = P dan y2 – y1 = Q. Bagian foto yang berada di luar segi empat yang dibatasi (x1, y1) dan (x2, y2) akan dibuang.

Namun, di dalam foto ini terdapat gambar wajah-wajah berbagai macam orang dari yang ganteng sampai dengan yang kurang ganteng. Tepatnya, ada N (1 ≤ N ≤ 20000) wajah orang, di mana wajah orang ke-i berada pada segi empat yang dibatasi (ui1, vi1) hingga (ui2, vi2) (0 ≤ ui1<ui2 ≤ W, 0 ≤ vi1<vi2 ≤ H), dan memiliki tingkat kegantengan Gi (1 ≤ Gi ≤ 1000). Lokasi wajah-wajah orang ini bisa saling overlapping (bertumpukan).

Anda diminta untuk membuat algoritma yang, diberikan ukuran foto asli, ukuran crop, dan data wajah-wajah orang di dalam foto tersebut, menentukan (x1, y1) dan (x2, y2) sehingga jumlah total tingkat kegantengan wajah-wajah yang terambil seluruhnya (tidak terpotong sedikitpun) adalah sebesar-besarnya. Dengan kata lain, wajah yang terpotong sedikitpun tidak mendapatkan nilai.

Format MasukanBaris pertama berisi banyaknya kasus uji, Z (1 ≤ Z ≤ 4). Untuk setiap kasus uji, format input adalah sebagai berikut.

Baris pertama berisi empat buah bilangan bulat: W, H, P, Q. Baris kedua berisi sebuah bilangan bulat, N. N baris berikutnya masing-masing mendeskripsikan wajah ke-i dan terdiri atas lima bilangan bulat: ui1, vi1, ui2, vi2, Gi. Bisa saja ada lebih dari satu wajah yang terletak di posisi yang sama dan tingkat kegantengannya bisa sama atau berbeda.

Format KeluaranUntuk setiap kasus, output sebuah baris “Case #X: Y” dimana X adalah nomor kasus, dan Y adalah total jumlah tingkat kegantengan maksimum yang dapat diperoleh dengan meng-crop foto tersebut.

Contoh Masukan27 6 4 540 0 3 2 62 1 5 5 24 4 6 6 31 4 3 6 56 6 3 34



1 0 3 2 53 1 5 3 42 3 4 5 30 2 2 4 2


Penjelasan ContohKedua kasus uji digambarkan dengan gambar-gambar di bawah ini. Segi empat berwarna biru adalah bagian foto yang dicrop sehingga total skor adalah sebesar-besarnya.



Surat TantanganTime Limit 1 s

Memory Limit 128 MB

Deskripsi PermasalahanPak Ganesh sedang mengunjungi gajah-gajahnya. Beliau kaget ketika melihat seluruh gajah-gajahnya tidak berada di dalam kandang. Beliau menemukan sepucuk surat yang berisi tantangan dari sang penculik. Surat itu berisikan sandi-sandi rahasia yang merupakan petunjuk tempat di mana gajah-gajah Pak Ganesh disembunyikan. Surat itu berisikan N karakter (1 < N <= 1000000). Pak Ganesh sangat khawatir dengan keadaan gajah-gajahnya, namun beliau bingung karena beliau tidak mengerti apa arti dari sandi-sandi rahasia yang tertulis dalam surat tantangan sang penculik itu. Oleh karena itu, beliau meminta bantuan Anda untuk memecahkan sandi-sandi rahasia itu.

Setelah berjuang selama beberapa jam, Pak Ganesh mendapatkan petunjuk untuk memecahkan sandi tersebut dengan mengubah karakter di posisi ke-i menjadi karakter i sebelumnya di urutan alfabet. Jika ternyata sudah kurang dari ‘a’ maka akan dilanjutkan dari ‘z’, begitu pula untuk huruf kapital. Untuk seluruh karakter lain selain alfabet tidak dilakukan perubahan apapun.

Format MasukanSebanyak N buah karakter (1<N<=1000000) yang merupakan sandi-sandi rahasia dari sang penculik. Karakter yang tertulis di surat dijamin merupakan printing character (nilai ASCII >32 dan <127).

Format KeluaranSebanyak N buah karakter (1<N<=1000000) yang merupakan terjemahan sandi-sandi rahasia dari sang penculik.

Contoh Masukan 1Hcmem-nisksyh quiswu zf HTC.

Contoh Keluaran 1Gajah-gajahmu berada di ITB.

Contoh Masukan 2Tgpyf nisks qwhudtnhtehym ek vzshp Zlw Rtdxceyf.

Contoh Keluaran 2Semua gajah disembunyikan di rumah Pak Dengklek.

Contoh Masukan 3Kkne qhud tztwc xscuc-dyiaiox xksivke, apar duhq fzrvu tjxnq up gsbfrl Cioqgsuu Wiptvtxqt Cfdwisfgdjd Boovhwy 2011 pvosqbsg.

Contoh Keluaran 3Jika kamu ingin gajah-gajahmu selamat, maka kamu harus pergi ke tempat Institut Teknologi Programming Contest 2011 diadakan.

final itb senior programming contest 2011€¦ · web viewgajah-gajah peliharaan pak ganesh...

Documents