E: Combination Lock
Combination Lock was originally going to be the simplest problem in the set. Then, one of our judges got confused about it, and we realized we needed a simpler problem (Lotto).
The confusion comes because the numbers are on the dial, and the arrow on the lock, not the other way around. So, when you turn the lock clockwise, the numbers go down, and counterclockwise, they go up. This was confusing to many people.
Here’s a question we got a lot:
Where does the dial start?
The answer is that it starts at the worst possible place for it to start, which would be n-1 away from t1. This is stated in the problem:
You must find the maximum possible number of ticks the dial must be turned in
order to open the lock.
Here’s the Judge Input, the Judge Output, the main solving program, another Java program, and a C++ program.
A solution waits for you in the spoiler.
[spoiler]
The worst possible case is that you start out n-1 away from t1.
Tally up the number of clicks like this:
| Step One | |
|---|---|
| Go around once: | n |
| Go around again: | n |
| Go to T1: | n-1 |
| Step Two | |
| Go the other way around: | n |
| Go from T1 to T2. | (t2-t1+n)%n (see Note) |
| Step Three | |
| Go from T2 to T3 | (t2-t3+n)%n (see Note) |
| Add’em up | |
| Total | 4n + (t2-t1+n)%n + (t2-t3+n)%n – 1 |
Note: How many clicks is it from t1 to t2? Well, turning the dial counter-clockwise, the numbers go up. If t2>t1, then you just go straight from t1 to t2, and the answer is t2-t1. If t2<t1, then you go up from t1 to n (which is the same as 0), and then from 0 to t2. That’s n-t1 + t2. Either way, (t2-t1+n)%n covers it.
To go to from t2 to t3, it’s the same logic, except the dial is spinning the other way and the numbers go down. Then, you get (t2-t3+n)%n.
[/spoiler]