本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1257. F. Faster Microwaving


Description

Chris likes getting his food quickly so he cooks a lot using the microwave. However, he is frustrated by how microwave makers seem not to communicate well with makers of
microwavable foods. For example, many microwaves have a “popcorn” button, but most microwave popcorn instructions say “Do not use the ‘popcorn’ button.” To avoid any chance of ruining his food, Chris uses only timed cooking, entering the time to cook each item in minutes and seconds (in MM:SS format) on the numbered buttons of the microwave. Since there is one digit per button, he has to press one digit at a time and move his finger between different digits, which is tedious and annoying because he’s hungry. One nice thing is that there is no button for the “:” as the microwave always interprets the last 2 digits as seconds, and inserts the “:” appropriately—however, it does not enforce a restriction that the last two digits are 59 seconds or less; if Chris presses 1, then 9, then 0 for a time of “1:90” it will cook for 1 minute and 90  seconds, which is the same as 2 minutes and 30 seconds.


Chris would like to be able to enter the cooking times more quickly. He notices that it takes 1 “moment” (a unit of time just under half a second) to press each digit’s button firmly, and it also takes 1 moment (the same unit of time) to move his finger away from one digit’s button to find the button for a different digit. Therefore, to enter a time “4:00” takes 4 moments in total—one to press “4”, one to move from “4” to “0”, one to press “0”, and one to press “0” again immediately, without having to find the button. It also takes 4 moments to enter “4:45” (press 4, then 4 again, then move from 4 to 5, then press 5), but it takes 5 moments to enter “4:30” (4, then move, then 3, then move, then 0).


After some experimentation, Chris devises the following plan to enter faster cooking times that are reasonably close to the recommended times in the cooking instructions for each item:


1. based on the microwavable item type, consider using a range of proposed cooking times  that are each within a small percent above or below the recommended cooking time. For example, using 10% with a recommended cooking time of 2 minutes and 30 seconds(2:30), the proposed cooking times would be the range of times from 2:15 to 2:45  inclusive.
2. Find the sequence of digits (buttons) that takes the lowest total moments to enter out of any of the proposed cooking times in the range.
3. If there are multiple sequences of digits that have the same lowest total moments, choose the sequence that yields an actual cooking time that is closest to the recommended cooking time.



Chris has verified that the above plan always results in a unique answer so you may assume so.


The Problem:


Given the recommended cooking time for a microwavable item, and a percent to use for the range of proposed cooking times, output the sequence of digits that Chris should press in order to start the microwave as fast as possible, according to his plan.



Input

The first input line contains a positive integer, n, indicating the number of microwavable items for which cooking times should be converted. The first line for each food item contains only the recommended cooking time, which consists of exactly 5 characters in the format MM:SS with 2- digit minutes MM (00 ≤ MM ≤ 20) and 2-digit seconds SS (SS ∈ {00, 15, 30, 45}). The recommended cooking time will be at least 00:15 (15 seconds). The second line contains only an integer p (2 ≤ p ≤ 10), which is the percent of the recommended cooking time that defines the range of lower and higher proposed cooking times.

Output

For each recommended cooking time in the input, first output the heading “Case #d: ”, where d is the test case number, starting with 1. Then, print the exact digits that should be pressed, in the order they should be pressed. Follow the format illustrated in Sample Output. Note that the seconds are always integers and the time must be “within” the percent range. For example, for a recommended cooking time of 00:45 and 10%, the range of proposed cooking times is 41 seconds to 49 seconds (45 ± 4, because 40 and 50 are not within 10% of the recommended time).

Samples

Input Copy
3
01:30
4
00:30
10
06:00
8
Output
Case #1: 88
Case #2: 33
Case #3: 555

Source

UCF2014
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 0 / 1
Tags:
Contests involved

1029. UCF 2014
My history solutions

You didn't submit any solution!
Submit your solution

Login Register