#2162

Minimum Cost to Set Cooking Time

expert · 1055 · lc medium +32 · verified · 41.5% accepted · 236 likes · top 22%

⚑ Direct Simulation

Description

A microwave supports cooking times of:

 - At least 1 second.

 - At most 99 minutes and 99 seconds.

To enter a cooking time, you press up to four digits. The microwave pads the input to four digits with leading zeros, interprets the first two as minutes and the last two as seconds, and adds them together. For example:

 - Pressing 9 5 4 is normalized to 0954: 9 minutes and 54 seconds.

 - Pressing 0 0 0 8 gives 0 minutes and 8 seconds.

 - Pressing 8 0 9 0 gives 80 minutes and 90 seconds.

 - Pressing 8 1 3 0 gives 81 minutes and 30 seconds.

You are given startAt, moveCost, pushCost, and targetSeconds. Your finger begins at digit startAt. Moving to a different digit costs moveCost fatigue units; pushing the current digit costs pushCost fatigue units.

Return the minimum total fatigue cost to enter a time equal to targetSeconds.

Recall that one minute is 60 seconds.

Example 1:

Input: startAt = 1, moveCost = 2, pushCost = 1, targetSeconds = 600
Output: 6
Explanation: The following are the possible ways to set the cooking time.
- 1 0 0 0, interpreted as 10 minutes and 0 seconds.
The finger is already on digit 1, pushes 1 (with cost 1), moves to 0 (with cost 2), pushes 0 (with cost 1), pushes 0 (with cost 1), and pushes 0 (with cost 1).
The cost is: 1 + 2 + 1 + 1 + 1 = 6. This is the minimum cost.
- 0 9 6 0, interpreted as 9 minutes and 60 seconds. That is also 600 seconds.
The finger moves to 0 (with cost 2), pushes 0 (with cost 1), moves to 9 (with cost 2), pushes 9 (with cost 1), moves to 6 (with cost 2), pushes 6 (with cost 1), moves to 0 (with cost 2), and pushes 0 (with cost 1).
The cost is: 2 + 1 + 2 + 1 + 2 + 1 + 2 + 1 = 12.
- 9 6 0, normalized as 0960 and interpreted as 9 minutes and 60 seconds.
The finger moves to 9 (with cost 2), pushes 9 (with cost 1), moves to 6 (with cost 2), pushes 6 (with cost 1), moves to 0 (with cost 2), and pushes 0 (with cost 1).
The cost is: 2 + 1 + 2 + 1 + 2 + 1 = 9.

Example 2:

Input: startAt = 0, moveCost = 1, pushCost = 2, targetSeconds = 76
Output: 6
Explanation: The optimal way is to push two digits: 7 6, interpreted as 76 seconds.
The finger moves to 7 (with cost 1), pushes 7 (with cost 2), moves to 6 (with cost 1), and pushes 6 (with cost 2). The total cost is: 1 + 2 + 1 + 2 = 6
Note other possible ways are 0076, 076, 0116, and 116, but none of them produces the minimum cost.

Code

1
2
3