# Internet Problem Solving Contest

## Problem K – Keys and locks

• This problem has no input files.

```To: Agent 047.
Mission: Acquire suitcase from room #723.
Briefing:
We managed to get you into room #719, which is on the same floor of the hotel. The hotel still uses the old pin tumbler
locks.  Housekeeping should have a master key that works for the entire floor.  Obtain it in order to get to room #723
undetected.  This mission statement will self-destruct in five seconds.  In case it does not, please tear it into small
pieces and eat it.
```

Pin tumbler locks

The photograph on the right shows a door with a pin tumbler lock. The static part of the lock is highlighted in green. The inside part, called the plug, is shown in yellow. This part of the lock rotates when a correct key is inserted and turned.

Below are four drawings of the inside of the lock. The ﬁrst one shows a lock without any key. Inside the lock there are multiple metal pins (blue+red). If there is no key present, the springs push these pins almost, but not entirely, into the plug.

The second and third drawing show what happens when a correct key is inserted into the lock: Each of the pins is actually cut into two separate parts (a blue part and a red part). When a key is inserted into the lock, it pushes the pins out of the plug. The correct key has the property that the boundary between the red and the blue part of each pin exactly matches the boundary of the plug. When this happens, the key can be used to turn the plug and thereby to lock/unlock the door.

The last drawing shows what happens when an incorrect key is inserted into the lock. The pins will be aligned diﬀerently and they will block the plug from turning.

Master keys

When you run a hotel, you have the following situation: On one hand, you have a lot of guests, and each guest should only be able to open their own door. On the other hand, you don’t want housekeeping to carry a ring with hundreds of keys. It is way more convenient for them to have a master key – a single key that can open all the locks.

With pin tumbler locks, creating a master key is really simple. You can even take a set of existing locks+keys and one new key and modify the locks to achieve the desired state – each lock can still be unlocked by its original key, and the new key can unlock all of the locks. How to do this? Each pin in each lock will now be divided in two places: one that corresponds to the original key, and one that corresponds to the new master key. (Technically, some of the pins will still be divided in one place. This happens whenever the original key and the master key have the same height at the corresponding location.)

The drawing on the right shows the lock from the previous drawings modiﬁed to also admit the second key. Three of the ﬁve pins are now divided into three parts (blue, cyan, and red). Now the plug can also be rotated with this new key inside. When that happens, the red and some of the cyan parts of the pins will be inside the plug.

Key proﬁles and bitting

On the right you can see a key proﬁle – an “empty” key. If you want to create a new key for a lock, you need to take the corresponding key proﬁle (one that ﬁts your lock) and then you need to create the right pattern (called bitting) on the part of the key that goes into the lock. The locksmiths have machines that do this easily, but you can also do it using an iron ﬁle, if you have to. (In this task, you have to.)

Each particular bitting can be described by a string of digits. If you have a lock with p pins, there will be exactly p locations on the key that touch the pins when the key is inserted properly. Each pin can be cut in one of k 10 places. (The possible cut locations are suﬃciently apart to prevent the same key from working with diﬀerently cut pins.) Thus there are exactly kp diﬀerent lock-key pairs. Each particular key can be described as a string of p digits from the set {0,,k 1}.

Diﬀerent manifacturers use diﬀerent encodings of the bitting. In this problem, 0 represents the shortest pin and correspondingly the shallowest cut on the key. (I.e., the larger the number, the more you have to ﬁle away when creating the key from an empty proﬁle.) The ﬁrst number is the pin closest to your hand. (This actually does not matter in this problem.)

In this problem, an empty key proﬁle works as a key with bitting containing all zeroes.

(Note: In practice there is also a standard saying that adjacent pins should have similar cut locations. This is to ensure that the correct key can be inserted and removed smoothly. In this problem we will ignore this and consider all possible keys valid – after all, you will not be using any key too many times.)

The red line in the ﬁgure on the right shows how to ﬁle the key proﬁle in order to obtain a key for p = 6, k = 5, and bitting 034132.

Problem speciﬁcation

You may assume that the bittings of the three actual keys (the master key and the guest keys for rooms #719 and #723) are distinct and that they were generated uniformly at random before you started solving the task. (I.e., our grader will not try to do any nasty tricks.)

Your task is to unlock the room #723, using any key that works. There are two completely independent scenarios with slightly diﬀerent rules. You will be submitting your actions for the easier scenario as output ﬁles for the subproblem K1, and for the harder scenario as K2. Here is the list of allowed actions:

• checkin” – check into room #719 at the hotel. Our answer will have the form: “room key: XXXXX”, where the string of Xs will be replaced by the bitting of the guest key to room #719. (You are not allowed to modify this key, you will need it to check out without raising any suspicions.)
• file A XXXXX” – use an iron ﬁle on key proﬁle number A to produce the speciﬁed bitting. Our answer will have the form “key A new bitting YYYYY”. Note that YYYYY may diﬀer from XXXXX. We will only apply the changes that are still possible. E.g., if you take a key with bitting 444222 and try to ﬁle it to the bitting 333333, you will get the key 444333.
• try A R” – try using key A to unlock room R. The room number must be one of 719 and 723. Our answer will have the form “success” or “failure”. Once you get the answer “success” for R = 723, you have successfully solved the particular subproblem.
• restart” – only use this if you did something stupid and want to start again from scratch. We will generate new keys for you and reset all your key proﬁles. Our response will be “restarted”.

Rules common for both subproblems

• You are allowed to make at most 30 submissions (not just 10 as for other problems).
• Each submission in which you do not solve a subproblem does count as an incorrect submission.
(Using as few submissions as possible is probably not a bad idea.)
• Each submission must be a text ﬁle containing between 1 and 20 lines, inclusive.
• Each line must contain exactly one of the commands speciﬁed above.
• Commands are processed one by one in the order in which you speciﬁed them.
• Lines with incorrect syntax are ignored and an error message is printed for each of them.

Speciﬁc rules for the easy subproblem

• The number of diﬀerent pin heights is k = 3.
• The number of pins in the lock is p = 9. That means there are 39 = 19683 possible keys.
(Two of those are the master key and the guest key to #723.)
• At the beginning, you have 160 empty key proﬁles, numbered 1 through 160.
(In other words, you have 160 keys, each with the bitting 000000.)
• You have the additional (possibly useless) information that the bittings for the master key and for the guest key to room #723 diﬀer in all positions. (This does not have to be the case for the key to room #719.)

Speciﬁc rules for the hard subproblem

• The number of diﬀerent pin heights is k = 9.
• The number of pins in the lock is p = 10. (There are 910 = 3486784401 diﬀerent keys.)
• At the beginning, you have 23 empty key proﬁles, numbered 1 through 23.
• Trying to unlock the room #723 is dangerous and requires a lot of time. The command “try A 723” may only be sent as the only command in the ﬁle. That is, the ﬁle must contain just a single line with this command. In all other cases this command will be ignored with an error message.

Communication example (for the easy subproblem)

input
checkin
file 13 012012012
try 13 723
file 13 111111111
try 9999 -47
output
room key: 202102022
key 13 new bitting 012012012
failure
key 13 new bitting 112112112
try failed -- incorrect syntax

input
try 13 719
restart
checkin
file 13 012012012
try 13 723
output
failure
restarted
room key: 220012110
key 13 new bitting 012012012
success

Notes: The problem statement describes an actual way how master keys for pin tumbler locks are made. The ﬁrst four drawings in the problem statement are derived works from pictures in the Wikipedia article “Pin tumbler lock”. Their authors are Wikipedia users Wapcaplet, GWirken and Pbroks13. The drawings are available under the CC BY-SA 3.0 licence.