Google Code Jam 2012 Qualification Round Problem B : Dancing With The Googlers
Setelah di artikel sebelumnya kita membahas Problem A, selanjutnya kita akan membahas soal Google Code Jam 2012 Qualification Round Problem B. Bagi yang belum tahu apa itu Google Code Jam, silahkan membaca artikel ini
Problem
You’re watching a show where Googlers (employees of Google) dance, and then each dancer is given a triplet of scores by three judges. Each triplet of scores consists of three integer scores from 0 to 10 inclusive. The judges have very similar standards, so it’s surprising if a triplet of scores contains two scores that are 2 apart. No triplet of scores contains scores that are more than 2 apart.
For example: ( 8, 8, 8 ) and ( 7, 8, 7 ) are not surprising. ( 6, 7, 8 ) and ( 6, 8, 8 ) are surprising. ( 7, 6, 9 ) will never happen.
The total points for a Googler is the sum of the three scores in that Googler’s triplet of scores. The best result for a Googler is the maximum of the three scores in that Googler’s triplet of scores. Given the total points for each Googler, as well as the number of surprising triplets of scores, what is the maximum number of Googlers that could have had a best result of at least p?
For example, suppose there were 6 Googlers, and they had the following total points:29, 20, 8, 18, 18, 21. You remember that there were 2 surprising triplets of scores, and you want to know how many Googlers could have gotten a best result of 8 or better.
With those total points, and knowing that two of the triplets were surprising, the triplets of scores could have been:
10 9 10
6 6 8 (*)
2 3 3
6 6 6
6 6 6
6 7 8 (*)
The cases marked with a (*) are the surprising cases. This gives us 3 Googlers who got at least one score of 8 or better. There’s no series of triplets of scores that would give us a higher number than 3, so the answer is 3.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line containing integers separated by single spaces. The first integer will be N, the number of Googlers, and the second integer will be S, the number of surprising triplets of scores. The third integer will be p, as described above. Next will be N integers ti: the total points of the Googlers.
Output
For each test case, output one line containing “Case #x: y”, where x is the case number (starting from 1) and y is the maximum number of Googlers who could have had a best result of greater than or equal to p.
Limits
1 ≤ T ≤ 100.
0 ≤ S ≤ N.
0 ≤ p ≤ 10.
0 ≤ ti ≤ 30.
At least S of the ti values will be between 2 and 28, inclusive.
Small dataset
1 ≤ N ≤ 3.
Large dataset
1 ≤ N ≤ 100.
Sample
| Input | Output |
| 4 3 1 5 15 13 11 3 0 8 23 22 21 2 1 1 8 0 6 2 8 29 20 8 18 18 21 |
Case #1: 3 Case #2: 2 Case #3: 1 Case #4: 3 |
Secara garis besar, kita diminta untuk menghitung ada berapa banyak Googlers yang mendapat nilai tertinggi sama dengan atau lebih dari nilai p. Dalam kontes ini, setiap Googlers akan mendapat penilaian dari 3 orang dewan juri dimana ketiga juri tersebut memiliki selera yang sama. Jadi perbedaan nilai ketiga juri tidak akan lebih besar dari 2 point (dari skala 1-10). Jika ada juri yang selisih pemberian nilainya 2 point, maka kasus ini disebut surprise.
Sebagai contoh, juri 1 memberi nilai 8, juri 2 memberi nilai 7, dan juri 3 memberi nilai 6. Karena selisih pemberian nilai juri 1 dan 3 sebanyak 2 point (8-6), maka kasus ini disebut surprise. Dalam kasus di atas, tidak mungkin juri 3 memberi nilai 5, karena selisih perbedaan nilai tidak boleh lebih dari 2. Jika selisih perbedaan nilainya 0 atau 1 (misal 8-8-8 atau 8-8-7), maka kasus tersebut normal.
Solving
Dari ketentuan – ketentuan yang telah disepakati di atas, kita dapat membagi nilai t ke dalam 3 bagian. Pertama nilai t yang normal, artinya nilai t ini triplet nilainya memiliki selisih nilai 0 atau 1 sehingga jatah nilai S (surprise) tidak kita gunakan. Yang kedua, nilai t yang surprise, artinya nilai t ini triplet nilainya memiliki selisih nilai 2 sehingga nantinya kita harus menggunakan jatah nilai S (surprise). Dan yang ketiga, nilai t yang nilai tertingginya tidak melebihi atau menyamai nilai p sehingga tidak akan kita hitung.
Dari ketiga jenis nilai t, yang pasti akan kita hitung adalah nilai yang normal. Untuk nilai surprise, kita harus berhati – hati karena banyaknya nilai surprise tidak boleh melebihi nilai S. Sedangkan jenis ketiga tidak akan masuk hitungan.
Langkah selanjutnya adalah menentukan apakah sebuah nilai t masuk ke kategori normal, surprise, atau tidak masuk hitungan.
Untuk kategori normal, seperti yang telah ditentukan sebelumnya, selisih nilai triplet tidak boleh lebih dari 1. Berarti sebuah nilai t harus berasal dari penjumlahan nilai p + p + p, p + p + (p – 1), atau p + (p – 1) + (p – 1). Dari ketiga kemungkinan itu, p + (p – 1) + (p – 1) memiliki jumlah nilai yang paling minimal (3p – 2). Maka dari itu, sebuah nilai t dapat tergolong normal apabila memiliki nilai minimal 3p – 2.
Selanjutnya untuk kategori surprise, seperti yang telah ditentukan sebelumnya, selisih nilai triplet harus sebanyak 2 point. Hal ini dapat terpenuhi apabila nilai t berasal dari penjumlahan nilai p + p + (p – 2), p + (p – 1) + (p – 2), atau p + (p – 2) + (p – 2). Dalam kasus pertama (p + p + (p – 2)), jumlah nilainya adalah 3p – 2. Ini berarti kasus tersebut memiliki nilai yang sama dengan nilai minimal dari jenis normal. Maka dari itu, dalam kasus ini triplet tersebut masuk ke jenis normal, bukan ke jenis surprise karena p + p + (p – 2) dapat dirubah menjadi p + (p – 1) + (p – 1). Kasus ketiga (p + (p – 2) + (p – 2)) adalah nilai minimal dari jumlah triplet yang dapat masuk ke kategori surprise karena menghasilkan nilai terkecil, yaitu 3p – 4.
Sejauh ini dapat kita tarik kesimpulan bahwa :
Normal >= 3p – 2
3p – 2 > Surprise >= 3p – 4
3p – 4 > Tidak masuk hitungan
Tetapi langkahnya belum selesai sampai di sini. Jika kita aplikasikan kesimpulan di atas, maka untuk case #3 program kita akan mengeluarkan hasil yang salah. Di case #3, nilai p adalah 1 dan nilai t adalah 0. Jika kita aplikasikan kesimpulan di atas, maka nilai t akan masuk kategori surprise karena 3p – 4 menghasilkan nilai 3.1 – 4 = -1 dan nilai t (0) lebih besar dari -1. Padahal, secara logika nilai 0 didapat dari penjumlahan nilai 0 + 0 + 0 dan nilai p yang diminta adalah 1 sehingga seharusnya kasus ini masuk ke kategori tidak masuk hitungan.
Hal ini dapat kita atasi dengan menambahkan conditional statement (if…else) di awal pemeriksaan yang berisi apabila nilai t lebih kecil dari nilai p, maka kasus tersebut tidak masuk hitungan.
Selanjutnya kita perlu menambahkan sebuah counter untuk membatasi banyaknya kasus surprise agar tidak melebihi jumlah nilai S. Apabila banyaknya nilai t yang masuk kategori surprise lebih banyak dibanding nilai S, maka nilai t yang masuk hitungan akan sebanyak nilai S tanpa memperhatikan banyaknya nilai t yang masuk kategori surprise.
Dan langkah terakhir adalah mengimplementasikan logika yang telah dijabarkan di atas ke dalam bentuk kode. Sekadar mengingatkan, Google tidak membatasi penggunaan bahasa pemrograman dalam kontes ini. Jadi meskipun Anda pecinta bahasa C, C++, C#, Java, atau bahkan Pascal sekalipun, asalkan output yang dikeluarkan benar, maka program Anda akan lolos. Selamat mengerjakan!
Related Posts
Category: Event, International Event
Subscribe
If you enjoyed this article, subscribe to receive more just like it.
