TLE '17 Contest 4 P2 - Microwave Buttons

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type
The return of the microwave.

Fax McClad, Croneria's hungriest bounty hunter, wants to cook a quick meal in his microwave. Unfortunately, some of the buttons on his microwave have broken down.

Fax wants to microwave his food for hh:mm:ss, where hh is a 2 digit number representing the number of hours, mm is a 2 digit number representing minutes, and ss is a 2 digit number representing seconds. Note that mm and ss do not necessarily have to be less than 60.

For reference, there are 60 seconds in a minute, and 3600 seconds in an hour.

The list of usable buttons will be given in a string as input. There will be at least one usable button.

Can you tell Fax the closest time that can be inputted to his desired time? That is, tell him the time with the smallest time difference that can be inputted in the microwave. Note that all digits (including zeroes) of the inputted time must be present in the string of working buttons.

Input Specification

The first line of input will contain Fax's desired time in the form hh:mm:ss.

The second line of input will contain a string of at least 1 character and up to 10 characters, consisting of unique digits 0 through 9 in order. A digit in the string means that the corresponding button is working.

Output Specification

Output the closest time in hh:mm:ss format that can be inputted in the microwave to Fax's desired time.

If there is more than one answer, output any of them.

Sample Input 1


Sample Output 1


Explanation for Sample Output 1

Fax wants to microwave his food for 1 \times 3600 + 17 \times 60 + 27 = 4647 seconds. All of the buttons on the microwave work, except for 7.

A 1 second difference is the best difference possible. For example, all of the digits in 01:16:86 are allowed, and this time results in 4646 seconds. Another possible answer is 01:16:88.

Sample Input 2


Sample Output 2



There are no comments at the moment.