SCPC COMPFEST 9 PENYISIHAN

      SCPC COMPFEST 9  PENYISIHAN     

A. Restoran Chanek  B.Kucing Warna Warni  C. Makan Malam Chanek  D.Dua Sejoli  E. Epal Berharga  F. Faktorunesia  G.Array yang Hilang  H.Palindromisme  I. Iri Itu Tidak Baik  J. Mencari Waifu 

Restoran Chanek Time limit: 1 s Memory limit: 64 MB

Deskripsi Pak Chanek baru saja mendirikan restoran yang menyediakan M buah jenis makanan-makanan lezat. Untuk menyediakan makanan-makanan lezat tersebut, Pak Chanek berhasil merekrut N koki handal. Pak Chanek yang unik ingin semua koki terlibat dalam memasak setiap makanan yang akan disajikan. Hal ini dilakukan agar cita rasa dari makanan-makanan tersebut menjadi sangat nikmat, setidaknya menurut Pak Chanek. Dikarenakan restoran Chanek baru didirikan dan kurangnya modal, Pak Chanek hanya sanggup membeli satu alat masak untuk dapur restorannya, sehingga hanya tepat satu koki yang bisa bekerja dalam satu waktu. Waktu yang koki ke-i butuhkan untuk menyelesaikan bagiannya dalam memasak makanan ke-j adalah Aij menit. Suatu pekerjaan koki dapat langsung dilaksanakan tepat setelah suatu pekerjaan koki lain selesai dilaksanakan. Pak Chanek sedang memikirkan suatu kasus, yaitu ketika para koki tersebut harus menyiapkan tepat satu makanan untuk semua jenis makanan yang restorannya sediakan. Bantulah Pak Chanek menghitung waktu minimum yang para koki butuhkan dalam kasus tersebut!

Format Masukan Baris pertama berisi sebuah bilangan bulat T yang menyatakan banyaknya kasus uji. Setiap kasus uji akan dinyatakan sebagai berikut. Baris pertama berisi dua bilangan bulat N dan M, banyaknya koki dan banyaknya jenis makanan. N baris berikutnya berisi M bilangan bulat Aij, waktu yang koki ke-i perlukan untuk melaksanakan bagiannya dalam memasak makanan ke-j dalam menit.

Format Keluaran Untuk setiap kasus uji, keluarkan satu baris berisi sebuah bilangan bulat, waktu minimum yang para koki butuhkan dalam menit.

Contoh Masukan 2 1 3 2 9 4

3 2 2 2 3 7

Contoh Keluaran 7 23

Penjelasan

Penjelasan Pada kasus uji pertama, hanya terdapat 1 koki, waktu yang dibutuhkan adalah 3 + 2 + 2 = 7 menit. Pada kasus uji kedua, urutan pengerjaan dapat dilakukan sebagai berikut: 1. 2. 3. 4.

Koki ke-1 memasak makanan ke-2 Koki ke-2 memasak makanan ke-1 Koki ke-2 memasak makanan ke-2 Koki ke-1 memasak makanan ke-1

Waktu yang dibutuhkan adalah 3 + 4 + 7 + 9 = 23 menit.

Batasan 1 ≤ T ≤ 10 1 ≤ N ≤ 250 1 ≤ M ≤ 250 1 ≤ Aij ≤ 50.000

Kucing Warna Warni Time limit: 1 s Memory limit: 64 MB

Deskripsi Pak Chanek sedang ingin memelihara kucing. Oleh karena itu, Pak Chanek membangun N kandang di halaman rumahnya. Kandang-kandang tersebut dinomori dari 1 sampai N, dengan kandang terkiri adalah kandang pertama dan kandang terkanan adalah kandang ke-N. Lucunya, Pak Chanek lupa membeli kucing yang akan tinggal di kandang-kandang tersebut! Pak Chanek ingin agar satu kandang ditinggali oleh tepat satu kucing. Oleh karena itu, Pak Chanek lalu pergi ke pet shop untuk membeli kucing. Ternyata, di pet shop tersebut terdapat M jenis kucing, yang mana untuk setiap jenis terdapat 109 kucing dengan jenis tersebut. Uniknya, perbedaan di tiap jenis hanya berada pada warnanya. Jenis-jenis kucing dinyatakan dengan suatu bilangan bulat yang berada di antara 1 sampai M. Pak Chanek tidak ingin memiliki halaman rumah yang biasa saja. Pak Chanek mendefinisikan suatu pasangan bilangan bulat (i, j) (1 ≤ i ≤ j ≤ N) sebagai pasangan yang indah apabila jenis kucing yang tinggal pada kandang ke-i, ke-(i+1), dan seterusnya hingga kandang ke-j berbeda satu sama lain. Pak Chanek lalu menetapkan suatu bilangan bulat K. Sekarang, Pak Chanek ingin mencari pembelian dan penempatan kucing, sehingga terdapat tepat K buah pasangan yang indah. Pak Chanek lalu meminta bantuanmu untuk mencari pembelian dan penempatan kucing sesuai yang ia inginkan. Bantulah Pak Chanek!

Format Masukan Baris pertama berisi sebuah bilangan bulat T yang menyatakan banyak kasus uji. Setiap kasus uji akan dinyatakan sebagai berikut. Baris pertama berisi tiga buah bilangan N, M, dan K, masing-masing menyatakan banyak kandang, banyak jenis kucing, dan banyak pasangan yang indah yang diinginkan Pak Chanek.

Format Keluaran Untuk setiap kasus uji, keluarkan satu baris berisi N buah bilangan bulat, yang menyatakan pembelian dan penempatan kucing yang mungkin. Bilangan ke-i menyatakan jenis kucing yang tinggal di kandang ke-i. Apabila terdapat lebih dari satu kemungkinan jawaban, keluarkan yang mana saja. Apabila tidak terdapat pembelian dan penempatan kucing yang memenuhi, N bilangan bulat ini berupa -1.

Contoh Masukan 3 3 2 5 3 3 3 3 2 6

Contoh Keluaran

Contoh Keluaran 1 2 1 3 3 3 -1 -1 -1

Penjelasan Pada kasus uji pertama, terdapat tepat 5 pasangan yang indah, yaitu: 1. 2. 3. 4. 5.

(1, 1) (1, 2) (2, 2) (2, 3) (3, 3)

Perhatikan bahwa (1, 3) bukan pasangan yang indah, karena jenis kucing pada kandang pertama sama dengan jenis kucing pada kandang ketiga, yaitu 1. Selain itu, 2 1 2 juga merupakan pembelian dan penempatan yang mungkin. Pada kasus uji kedua, terdapat 2 pembelian dan penempatan lain yang mungkin, yaitu: 1. 1 1 1 2. 2 2 2 Pada kasus uji ketiga, tidak terdapat pembelian dan penempatan yang mungkin.

Batasan 1 ≤ T ≤ 10 1 ≤ N ≤ 50.000 1 ≤ M ≤ 50.000 1 ≤ K ≤ 109

Makan Malam Chanek Time limit: 3 s Memory limit: 128 MB

Deskripsi Pak Chanek baru saja mulai mempelajari Competitive Programming. Memang susah pada awalnya. Sampai-sampai, ia harus bertapa di puncak gunung sambil berpuasa 3 hari 3 malam. Apakah setelah turun dari puncak gunung Pak Chanek langsung jago? Tentu saja tidak! Karena di puncak gunung tidak terdapat koneksi internet dan Pak Chanek pun tidak bisa latihan di sana. Tetapi Pak Chanek tidak menyerah. Ia tetap berlatih keras. Enam bulan berlalu. Akhirnya Pak Chanek memutuskan untuk mengikuti kompetisi pertamanya. Seperti apa yang telah dipikirkan sebelumnya, Pak Chanek gagal memenangkan kompetisi tersebut. Namun, ternyata Pak Chanek mendapat sebuah hadiah hiburan, yaitu paket makan malam untuk dua orang. Sebagai rasa terima kasihnya kepada temannya Dzul yang telah mengajarinya Competitive Programming sebelum pertapaannya, Pak Chanek memilihnya sebagai orang yang ia ajak makan malam. Pak Chanek dan Dzul duduk berhadapan di meja bundar dengan M makanan. Uniknya, banyak makanan di restoran ini pasti genap. Makanan dinomori dari 0 sampai M - 1 terurut searah jarum jam dengan makanan 0 berada tepat di depan Pak Chanek dan makanan M / 2 berada tepat di depan Dzul. Untuk mengambil suatu jenis makanan, Pak Chanek atau Dzul harus memutar meja hingga makanan yang ingin diambil berada tepat di depan mereka. Putaran bisa dilakukan searah atau berlawanan arah jarum jam. Misal makanan di depan Pak Chanek adalah makanan x (yang berarti makanan di depan Dzul adalah makanan (x + M / 2) mod M). Maka, setelah sekali putaran, makanan di depan Pak Chanek berubah menjadi x', yang bisa bernilai x + 1 (0 apabila x = M - 1) atau x - 1 (M - 1 apabila x = 0). Tentunya, setelah perputaran makanan di depan Dzul adalah makanan (x' + M / 2) mod M. Sebagai catatan, 1 putaran, ke manapun arahnya, membutuhkan waktu 1 detik. Pak Chanek dan Dzul masing-masing memiliki urutan N makanan yang ingin mereka makan. Bisa saja suatu makanan muncul dalam urutan tersebut lebih dari sekali. Anggap saja waktu yang diperlukan untuk mengambil dan memakan suatu makanan 0 detik. Tentukan waktu minimum agar Pak Chanek dan Dzul dapat mengambil dan memakan makanan-makanan yang mereka inginkan!

Format Masukan Baris pertama berisi sebuah bilangan bulat T yang menyatakan banyak kasus uji. Setiap kasus uji akan dinyatakan sebagai berikut. Baris pertama berisi 2 bilangan yaitu M dan N. M menandakan berapa banyak jenis makanan yang ada di meja, dan N menandakan banyak makanan yang ingin dimakan oleh Pak Chanek dan Dzul. Baris kedua berisi N bilangan Ai yang menyatakan makanan ke-i yang ingin dimakan oleh Pak Chanek. Baris kedua berisi N bilangan Bi yang menyatakan makanan ke-i yang ingin dimakan oleh Dzul.

Format Keluaran Keluarkan sebuah baris berisi sebuah bilangan bulat, waktu minimum yang dibutuhkan.

Contoh Masukan

Contoh Masukan 2 4 3 3 0 1 0 3 2 10 5 7 8 7 3 6 2 3 0 5 0

Contoh Keluaran 5 17

Penjelasan Pada kasus uji pertama, awalnya Pak Chanek menghadap makanan 0 dan Dzul menghadap makanan 2. Waktu minimum (5 detik) dapat dicapai dengan cara berikut: 1. Putar searah jarum jam, sehingga Pak Chanek menghadap makanan 3 dan Dzul menghadap makanan 1. Pak Chanek bisa memakan makanan ke-1 yang ia inginkan. 2. Putar searah jarum jam, sehingga Pak Chanek menghadap makanan 2 dan Dzul menghadap makanan 0. Dzul bisa memakan makanan ke-1 yang ia inginkan. 3. Putar searah jarum jam, sehingga Pak Chanek menghadap makanan 1 dan Dzul menghadap makanan 3. Dzul bisa memakan makanan ke-2 yang ia inginkan. 4. Putar searah jarum jam, sehingga Pak Chanek menghadap makanan 0 dan Dzul menghadap makanan 2. Pak Chanek bisa memakan makanan ke-2 yang ia inginkan, dan Dzul dapat memakan makanan ke-3 yang ia inginkan. 5. Putar berlawanan arah jarum jam, sehingga Pak Chanek menghadap makanan 1 dan Dzul menghadap makanan 3. Pak Chanek bisa memakan makanan ke-3 yang ia inginkan.

Batasan 1 ≤ T ≤ 10 2 ≤ M ≤ 100.000 M mod 2 = 0 1 ≤ N ≤ 2.000 0 ≤ Ai < M 0 ≤ Bi < M

Dua Sejoli Time limit: 2 s Memory limit: 128 MB

Deskripsi Pak Chanek sedang patah hati karena ditinggal pasangannya. Karena ia sangat menderita, ia merasa bahwa semua pasangan tidak boleh bersatu. Pada acara Komunitas Pasangan Erat Sekali, atau KomPES, ia ingin menutup jalan sedemikian sehingga suatu pasangan tidak akan dapat bertemu. Acara KomPES terdiri dari N tempat pertemuan dan N jalan dua arah yang menghubungkan dua tempat pertemuan yang berbeda. Dipastikan terdapat setidaknya satu rute dari satu tempat pertemuan ke tempat pertemuan lainnya. Pak Chanek tidak ingin supaya rencananya diketahui, jadi ia ingin supaya banyak jalan yang ditutup seminimum mungkin. Ia juga ingin menyiapkan beberapa rencana penutupan jalan sebagai cadangan. Tetapi, Pak Chanek kesulitan menyiapkan rencana-rencananya. Oleh karena itu, ia meminta Anda untuk membantunya. Pak Chanek akan memberikan Q pertanyaan. Untuk setiap pertanyaan, Pak Chanek ingin tahu berapa minimum jalan yang harus ditutup untuk memisahkan pasangan dengan laki-laki berada di tempat pertemuan ke-Xj dan perempuan berada di tempat pertemuan ke-Yj, serta banyaknya cara untuk melakukan hal tersebut. Suatu pasangan dikatakan terpisah apabila dari tempat pertemuannya, laki-laki tidak dapat ke tempat pertemuan tempat perempuan berada dengan menggunakan jalan-jalan yang tidak ditutup. Dua cara dikatakan berbeda apabila terdapat jalan yang ditutup pada salah satu cara, namun tidak pada cara lainnya. Pak Chanek tidak tahu paling banyak ada berapa cara yang mungkin, sehingga ia ingin agar Anda menghitungnya dalam modulo 109+7 saja. Pak Chanek ingin agar pertanyaannya dijawab secepat mungkin. Jawablah pertanyaan Pak Chanek!

Format Masukan Baris pertama berisi sebuah bilangan bulat T yang menyatakan banyak kasus uji. Setiap kasus uji akan dinyatakan sebagai berikut. Baris pertama berisi sebuah bilangan bulat N, banyak tempat pertemuan dan jalan pada acara KomPES. N baris berikutnya masing-masing berisi dua bilangan bulat Ui dan Vi, yang menyatakan bahwa terdapat jalan yang menghubungkan tempat pertemuan ke-Ui dan tempat pertemuan ke-Vi. Baris berikutnya berisi sebuah bilangan bulat Q, banyak pertanyaan yang diberikan Pak Chanek. Q baris berikutnya masing-masing berisi dua bilangan bulat Xj dan Yj, posisi laki-laki dan posisi perempuan pada pertanyaan ke-j.

Format Keluaran Untuk setiap kasus uji, keluarkan Q baris masing-masing berisi dua bilangan bulat, jawaban dari pertanyaan yang diberikan, dengan banyak cara dalam modulo 109+7.

Contoh Masukan

Contoh Masukan 1 5 1 2 2 3 3 2 3 2 1 4

1 4 5 3 5

Contoh Keluaran 2 2 1 2

Penjelasan Pada pertanyaan pertama, Pak Chanek dapat menutup jalan-jalan sebagai berikut: 1. jalan pertama dan jalan ketiga 2. jalan kedua dan jalan ketiga Perhatikan bahwa tidak mungkin memisahkan pasangan tersebut dengan hanya menutup 0 atau 1 jalan.

Batasan 1 ≤ T ≤ 10 2 ≤ N ≤ 50.000 2 ≤ Q ≤ 50.000 1 ≤ Ui, Vi ≤ N 1 ≤ Xj, Yj ≤ N Xj ≠ Yj untuk setiap 1 ≤ j ≤ Q

Epal Berharga Time limit: 1 s Memory limit: 64 MB

Deskripsi Epal adalah buah yang hanya tumbuh di negeri Bineria, dan sangat disukai oleh warga negaranya. Mereka memiliki tradisi yang dijalankan setiap tahun ketika pohon-pohon epal banyak berbuah. Tradisi tersebut dimulai dari pengumpulan epal, yang mana masing-masing orang akan mengumpulkan sebanyakbanyaknya epal. Setelah itu, orang-orang tersebut akan berjejer dari kiri ke kanan, dan boleh memberikan hanya satu epal kepada orang di sebelah kiri atau sebelah kanannya. Dengan kata lain, orang ke-i boleh memberikan hanya satu epal kepada orang ke-(i-1) atau orang ke-(i+1), namun tidak ke keduanya. Tentunya, setiap orang boleh saja tidak memberikan epalnya sama sekali. Pada tahun ini, Terdapat N orang yang mengikuti tradisi negeri Bineria. N orang tersebut dinomori dari 1 sampai N, dengan orang ke-i mengumpulkan Ei epal. Pak Chanek sebagai penonton penasaran, berapakah maksimum dari minimum epal yang mungkin dimiliki N orang tersebut setelah sesi pemberian epal selesai?

Format Masukan Baris pertama berisi sebuah bilangan bulat T yang menyatakan banyak kasus uji. Setiap kasus uji akan dinyatakan sebagai berikut. Baris pertama berisi sebuah bilangan bulat N, banyak orang yang mengikuti tradisi pada tahun ini. Baris kedua berisi N bilangan Ei, banyak epal yang dimiliki orang ke-i sebelum sesi pemberian epal dimulai.

Format Keluaran Untuk setiap kasus uji, keluarkan satu baris berisi sebuah bilangan bulat, jawaban dari pertanyaan Pak Chanek.

Contoh Masukan 2 3 4 7 4 5 9 5 5 7 6

Contoh Keluaran 4 6

Penjelasan Pada kasus uji pertama, orang kedua hanya dapat memberikan epal kepada satu di antara orang pertama atau ketiga, sehingga jawabannya adalah 4.

Pada kasus uji kedua, orang pertama dapat memberikan epal kepada orang kedua, dan orang keempat dapat memberikan epal kepada orang ketiga, sehingga jawabannya adalah 6.

Batasan 1 ≤ T ≤ 10 1 ≤ N ≤ 100.000 1 ≤ Ei ≤ 109

Faktorunesia Time limit: 3 s Memory limit: 128 MB

Deskripsi Pak Chanek sedang berlibur di Negara Faktorunesia. Terdapat N kota di Faktorunesia serta M buah jalan dua arah yang menghubungkan dua kota berbeda. Jalan ke-i menghubungkan kota ke-Ui dan kota ke-Vi, serta memiliki suatu nilai Ci. Pak Chanek baru saja mendarat di kota ke-1, dan ingin pergi ke kota ke-N dengan menggunakan jalan-jalan yang ada. Suatu rute perjalanan memiliki aturan yang cukup aneh di Faktorunesia. Misal suatu rute perjalanan berturut-turut menggunakan jalan ke-e1, jalan ke-e2, dan seterusnya, hingga jalan ke-ek. Maka: Untuk setiap i (1 ≤ i ≤ k), berlaku Cei < i (nilai jalan yang dipakai ke-i harus lebih kecil dari i) Panjang dari rute perjalanan tersebut adalah Ce1 * 1! + Ce2 * 2! + ... + Cek * k! Sekarang, Pak Chanek penasaran, apakah ada rute perjalanan yang berawal dari kota ke-1 dan berakhir di kota ke-N, dan jika ada, berapakah panjang minimum rute perjalanan tersebut? Keluarkan jawabannya setelah dimodulo 109+7.

Format Masukan Baris pertama berisi sebuah bilangan bulat T yang menyatakan banyak kasus uji. Setiap kasus uji akan dinyatakan sebagai berikut. Baris pertama berisi dua buah bilangan bulat N dan M, masing-masing menyatakan banyak kota dan banyak jalan di Faktorunesia. M baris selanjutnya berisi Ui, Vi, dan Ci, yang menyatakan jalan ke-i menghubungkan kota ke-Ui dan kota ke-Vi, serta memiliki nilai Ci.

Format Keluaran Untuk setiap kasus uji, keluarkan satu baris berisi sebuah bilangan bulat yang menyatakan panjang rute perjalanan minimum, atau -1 apabila tidak ada rute perjalanan yang berawal dari kota ke-1 dan berakhir di kota ke-N.

Contoh Masukan 2 3 1 2 3 1 2

2 2 3 2 2 3

0 2 2 0

Contoh Keluaran 48 -1

Penjelasan

Penjelasan Pada kasus uji pertama, rute perjalanan terpendek adalah sebagai berikut: 1. 2. 3. 4.

Gunakan jalan ke-1, sehingga sekarang Pak Chanek berada di kota ke-2. Gunakan jalan ke-1, sehingga sekarang Pak Chanek berada di kota ke-1. Gunakan jalan ke-1, sehingga sekarang Pak Chanek berada di kota ke-2. Gunakan jalan ke-2, sehingga sekarang Pak Chanek berada di kota ke-3.

Panjang rute perjalanan tersebut adalah 0 * 1! + 0 * 2! + 0 * 3! + 2 * 4! = 48. Pada kasus uji kedua, tidak ada rute perjalanan yang berawal dari kota ke-1 dan berakhir di kota ke-N.

Batasan 1≤T≤8 2 ≤ N ≤ 2.000 1 ≤ M ≤ 4.000 1 ≤ Ui, Vi ≤ N Ui ≠ Vi untuk setiap 1 ≤ i ≤ M 0 ≤ Ci ≤ 2.000

Array yang Hilang Time limit: 1 s Memory limit: 64 MB

Deskripsi Pak Chanek sedang frustasi. Ia memiliki banyak pekerjaan yang harus diselesaikan. Tetapi karena sudah terlalu stres, ia tidak dapat berpikir jernih untuk melanjutkan pekerjaannya. Oleh karena itu, Pak Chanek memutuskan untuk pergi berlibur. Ia segera pergi ke bank mengambil uang untuk membeli persiapan liburan. Ia butuh koper baru, baju baru, celana baru, dan banyak benda baru lainnya. Dengan rasa senang dan penuh semangat ia berjalan dari rumah ke bank. Sesampainya di bank raut wajah Pak Chanek berubah. Bayangkan saja, ia harus menunggu 50 orang yang antreannya lebih depan. Namun dengan semangat berliburnya, Pak Chanek tetap mengantre. Meskipun ia harus melewatkan acara TV favoritnya. Setelah 4 jam mengantre, tiba giliran Pak Chanek menghadap teller. Setelah teller berbicara, wajah Pak Chanek langsung cemberut. Teller berkata karena satu dan lain hal, tabungan Pak Chanek terpaksa dibekukan selama 2 minggu. Tentu saja Pak Chanek makin frustasi. Dalam perjalanan pulang, Pak Chanek melihat sebuah brosur. Di brosur tersebut terdapat tebak-tebakan yang berisi, "Tebaklah sebuah array X yang berisi N bilangan bulat, sehingga X1 * X2 * .. * XN bernilai sama dengan A1 * A2 * A3 * ... * AN. Siapapun yang berhasil menebak array tersebut akan mendapatkan hadiah sebuah paket liburan." Muncul sedikit harapan di hati Pak Chanek. Sebelum harapannya membesar, Pak Chanek bertanya kepada Anda: ada berapa banyak kemungkinan array yang mungkin dibentuk dari tebak-tebakan tersebut? Anda yang iba melihat Pak Chanek akhirnya memutuskan untuk menjawab pertanyaan tersebut. Pak Chanek lalu menambahkan bahwa Anda cukup menjawabnya dalam modulo 109+7. Jawablah pertanyaan Pak Chanek! Dua buah array B dan C yang berukuran N dikatakan berbeda jika dan hanya jika terdapat sebuah indeks i (1 ≤ i ≤ N) sehingga Bi ≠ Ci.

Format Masukan Baris pertama berisi sebuah bilangan bulat T yang menyatakan banyak kasus uji. Setiap kasus uji akan dinyatakan sebagai berikut. Baris pertama berisi sebuah bilangan bulat N yang menyatakan ukuran array. Baris kedua berisi N buah bilangan bulat Ai, bilangan-bilangan sesuai deskripsi soal.

Format Keluaran Untuk setiap kasus uji, keluarkan satu baris berisi sebuah bilangan bulat yang menyatakan jawaban pertanyaan Pak Chanek modulo 109+7.

Contoh Masukan 2 2 2 3 3 3 2 2

Contoh Keluaran

Contoh Keluaran 4 18

Penjelasan Pada contoh kasus uji pertama, array-array yang mungkin adalah sebagai berikut: 1. 2. 3. 4.

[2, 3] [3, 2] [1, 6] [6, 1]

Batasan 1 ≤ T ≤ 10 1 ≤ N ≤ 100.000 1 ≤ Ai ≤ 100.000

Palindromisme Time limit: 1 s Memory limit: 64 MB

Deskripsi Pak Chanek sedang berulang tahun! Sebagai teman baik Pak Chanek, Irwanto pun memberikan hadiah pada Pak Chanek. Hadiah tersebut berupa string dengan panjang N yang dibungkus dengan kado yang sangat indah. Sayangnya, Irwanto memberikan hadiah tanpa mengetahui bahwa Pak Chanek merupakan pengikut ajaran Palindromisme. Setiap pengikut ajaran Palindromisme diwajibkan untuk mengubah string apapun yang mereka lihat hingga setiap substring dari string tersebut merupakan palindrom. Pengubahan ini dilakukan dalam beberapa langkah, yang mana dalam satu langkah terdapat satu indeks sehingga karakter pada indeks tersebut diubah menjadi karakter lain. Misal string hasil pengubahan adalah X. Maka, untuk setiap pasang (i, j) (1 ≤ i ≤ j ≤ |X|), substring Xi..j harus merupakan palindrom. Pak Chanek yang telah membuka kado dari Irwanto lalu mencoba mengubah string dari Irwanto sesuai ajaran Palindromisme. Sekarang, Pak Chanek justru penasaran, berapa langkah minimum yang ia perlukan dalam mengubah string tersebut? Suatu string dikatakan palindrom jika dan hanya jika string tersebut dapat dibaca dengan sama baik dari depan maupun belakang.

Format Masukan Baris pertama berisi sebuah bilangan bulat T yang menyatakan banyak kasus uji. Setiap kasus uji akan dinyatakan sebagai berikut. Baris pertama berisi sebuah bilangan N, panjang string yang diberikan Irwanto. Baris kedua berisi sebuah string S, string yang diberikan Irwanto.

Format Keluaran Untuk setiap kasus uji, keluarkan satu baris berisi sebuah bilangan bulat, banyak langkah minimum yang diperlukan Pak Chanek.

Contoh Masukan 2 1 c 2 pc

Contoh Keluaran 0 1

Batasan

Batasan 1 ≤ T ≤ 100 1 ≤ N ≤ 1.000 S hanya terdiri dari huruf kecil alfabet ('a' - 'z')

Iri Itu Tidak Baik Time limit: 1 s Memory limit: 64 MB

Deskripsi Pak Chanek adalah seorang pengusaha kaya. Ia mempekerjakan N karyawan di perusahaannya, dengan karyawan ke-i mendapat gaji sebesar Si per hari. Akhir-akhir ini, Pak Chanek sering mendapat surat dari karyawannya yang iri terhadap gaji karyawan lain. Sebagai orang yang baik, Pak Chanek tidak ingin banyak karyawannya yang merasa iri, sehingga ia memutuskan untuk memindahkan paling banyak K orang karyawan ke perusahaan temannya. Tingkat iri hati di perusahaan Pak Chanek dapat didefinisikan sebagai selisih gaji tertinggi seorang karyawan dengan gaji terendah seorang karyawan di perusahaannya. Pak Chanek ingin meminimalkan tingkat iri hati dengan memindahkan paling banyak K orang dari perusahaannya. Bantulah Pak Chanek menentukan tingkat iri hati minimum yang dapat dicapai!

Format Masukan Baris pertama berisi sebuah bilangan bulat T yang menyatakan banyaknya kasus uji. Setiap kasus uji dinyatakan sebagai berikut. Baris pertama berisi 2 buah bilangan bulat N dan K, masing-masing menyatakan banyak karyawan di perusahaan Pak Chanek dan banyak karyawan yang paling banyak akan dipindahkan. Baris kedua berisi N buah bilangan bulat Si, yang menyatakan gaji yang diterima karyawan ke-i.

Format Keluaran Untuk setiap kasus uji, keluarkan 1 bilangan bulat yang menyatakan tingkat iri hati minimum.

Contoh Masukan 2 4 3 6 6

2 4 3 4 1 9 8 6 7 9

Contoh Keluaran 0 3

Batasan 1 ≤ T ≤ 10 2 ≤ N ≤ 100.000 0≤K≤N-2 1 ≤ Si ≤ 109

Mencari Waifu Time limit: 1 s Memory limit: 64 MB

Deskripsi Ayaze, seorang mahasiswa yang pintar sedang bermimpi indah di suatu malam sebelum ujian Struktur Data dan Algoritma. Pada mimpinya, Ayaze berada dalam dunia yang mana terdapat N + 1 istri-istri dua dimensi khayalan Ayaze yang disebut 'waifu'. Waifu-waifu tersebut tersebar dalam dunia dua dimensi yang mana sistem koordinat yang digunakan adalah koordinat kartesius. Di dunia tersebut, Ayaze diberikan suatu daftar koordinat dari setiap posisi waifu-waifunya. Perlu diketahui, koordinat posisi suatu waifu bisa sama dengan waifu lainnya, karena dunia tersebut adalah dunia mimpi. Ayaze pun langsung berlari, berusaha untuk bertemu dengan semua waifunya. Namun, malang nasib Ayaze. Setelah ia bertemu dengan N waifunya, mimpinya berubah menjadi mimpi sangat buruk karena ia bertemu dengan temannya yang bernama Imhaf. Ayaze langsung terbangun dari mimpinya dalam keadaan syok. Ayaze langsung berusaha mengingat-ingat letak koordinat dari setiap waifu yang ada pada dunia mimpi tersebut, dengan harapan ia akan mendapatkan mimpi yang sama. Dia hanya mengingat: Seluruh koordinat posisi waifu berada pada koordinat (x,y) dengan 0 ≤ x, y ≤ 2.000 Koordinat posisi dari semua waifu yang sempat ditemuinya Semua koordinat berhasil dicatatnya kecuali satu, yaitu waifu yang belum sempat ditemuinya. Namun, Ayaze ingat bahwa jumlahan dari jarak Manhattan untuk setiap pasang titik koordinat posisi waifu-waifunya adalah K. Ayaze meminta bantuan Anda sebagai peserta penyisihan SCPC Compfest 9 untuk mencari koordinat posisi waifu tersebut berdasarkan koordinat posisi N waifu yang berhasil dicatat dan nilai K. Bantulah Ayaze!

Format Masukan Baris pertama berisi sebuah bilangan bulat T yang menyatakan banyak kasus uji. Setiap kasus uji akan dinyatakan sebagai berikut. Baris pertama berisi dua buah bilangan bulat N dan K, masing-masing menyatakan banyak waifu yang koordinatnya berhasil Ayaze catat dan jumlah jarak Manhattan setiap pasang titik koordinat posisi waifu-waifunya. N baris berikutnya berisi Xi dan Yi, yaitu koordinat posisi waifu ke-i yang berhasil dicatat Ayaze.

Format Keluaran Untuk setiap kasus uji, keluarkan satu baris berisi dua buah bilangan bulat x dan y, yaitu koordinat posisi waifu yang belum dicatat Ayaze. Posisi x dan y dari koordinat harus berada dalam rentang [0, 2000]. Apabila terdapat lebih dari satu jawaban, keluarkan yang mana saja. Apabila tidak ada jawaban yang memungkinkan (mungkin saja ia salah hitung), keluarkan "-1 -1" (tanpa tanda kutip).

Contoh Masukan

Contoh Masukan 2 3 16 1 1 3 1 3 3 1 3 3

3 2 1 1 3

Contoh Keluaran 1 3 -1 -1

Penjelasan Untuk kasus uji pertama, berikut adalah gambar dari koordinat posisi waifu-waifu yang tercatat:

Salah satu koordinat posisi yang memungkinkan agar jumlahan jarak Manhattan terpenuhi adalah titik (1,3) atau titik ANS pada gambar. Selain itu, (2,0) dan (4,2) juga merupakan posisi yang mungkin. Untuk kasus uji kedua, tidak ada titik yang memungkinkan sehingga jumlahan jarak Manhattan adalah 2.

Batasan 1 ≤ T ≤ 10 1 ≤ N ≤ 50.000 0 ≤ K ≤ 1012 0 ≤ Xi ≤ 2.000 0 ≤ Yi ≤ 2.000

Catatan

Catatan Jarak Manhattan dari dua buah titik koordinat (x1, y1) dan (x2, y2) adalah (|x2 - x1| + |y2 - y1|).

Saran Dalam mencari istri, carilah istri tiga dimensi.