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, the last part of this puzzle is the real challenge. Same as before, 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.
Unluckily, the terrorist has upgraded the bomb! There is an additional behavior: the bomb will explode as after a “BEEP” heard, the next “BEEP” is not heard in the next N button pushes.
So, on above example, the bomb will explode after the 13-th push because the "BEEP" is not heard since the 9-th push.
Let's 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.