The part 1 can be found here: Taming a Bomb Puzzle (Part 1 of 3)
Ampera Bridge, the famous landmark of Palembang City is in danger! A terrorist has sticked a bomb in the middle of Ampera Bridge. The bomb cannot be removed and it can explode anytime.
The bomb has N buttons, labeled from 1 to N (inclusive). It will explode right after pushing any of those buttons T times except one thing as follows.
Among the buttons, there is exactly one button, namely X. The bomb is designed so that when X has been pushed, it will sound “BEEP” but delayed at next K button pushings after it was pushed. In other word, if X was pushed at the i-th push, its “BEEP” can be heard at the (i+K)-th push. You don't know the value of K, but K is guaranteed to be between 0 to N-1. Of course, you also don't know the value of X.
Whenever the "BEEP" has been heard for N times (not necessarily consecutive), the bomb can be deactivated (tamed), of course, as long as the total number of button pushes does not exceed T times. When you hear the "BEEP", you may not know from which push it is made. But surely, if at the i-th push you hear the "BEEP", then your (i-K)-th push must be X.
To help you follow the definition and the example, here's a quick glossary:
N: the number of buttons
T: at this many button presses, the bomb goes off
X: the button you need to identify
K: an unknown but constant delay before the beep, measured in button presses. From 0 up to, but not including N
i: the total press count, when a particular button was pressed
You, as a top bomb tamer, are to find a sequence of button pushes for deactivating the bomb.
Let's say you have the information of N = 4 and T = 20.
You have no clue at the beginning that this bomb has a value of X = 3 and K = 2.
-----------------------
| No | You Push | Beep? |
-----------------------
| 1 | 3 | - |
| 2 | 2 | - |
| 3 | 3 | BEEP! |
| 4 | 4 | - |
| 5 | 1 | BEEP! |
| 6 | 4 | - |
| 7 | 3 | - |
| 8 | 1 | - |
| 9 | 1 | BEEP! |
| 10 | 1 | - |
| 11 | 1 | - |
| 12 | 3 | - |
| 13 | 3 | - |
| 14 | 3 | BEEP! |
Some key points:
- You push button X = 3 as the first push, but its "BEEP" is heard after third (1+K = 1+2 = 3) push. Same as the third push's "BEEP" is heard at fifth push.
- The bomb hasn't been tamed at 12-th push. It will be tamed after 14-th push, when the N = 4-th "BEEP" is heard.
- If T is 13 or less, the bomb will explode in this case.
Now, let's up for the challenge. You know that the bomb has N = 50 buttons with a limit of T = 250 pushes. You don't know what are the values for X and K.
Find a way to tame the bomb!
Bonus: Can you generalize with any N given that T = 5N?
This puzzle is based on a competitive programming problem authored by me. It is used in Indonesia National Science Olympiad in Informatics 2016. The link is here (spoiler ahead for further parts!)
Answer
First,
press all the buttons in order 1..N and then again in reverse order N..1. You will hear beeps at times X+K and 2N+1-X+K, so once those have happened you can deduce X and K (say the first beep is at time t and the second at time u; then t+u=2N+1+2K, giving K, and u-t=2N+1-2X, giving X. (You haven't necessarily heard the second beep by the time you reach button 1 for the second time; in that case, start up from 1 again.)
As soon as
you hear the second beep, at time 2N+1-X+K, you know which button you have to keep pressing. You've pressed it at least twice by now, so you need another N-2 presses, for a total of 3N-1-X+K. And then you have to wait another K presses for all the beeps to occur (might as well keep mashing on button X for this), for a total of 3N-1-X+2K. Since X is at least 1 and K is at most N-1, this is no worse than 3N-1-1+2N-2=5N-4 button presses.
No comments:
Post a Comment