General Grievous
Time limit2sMemory limit1024 MB
Decide whether n lightsabers, each lasting m seconds per blade or m/2 when both blades are lit, can measure exactly t seconds.
- Level
Medium6 of 10
- Topics
- Math, Simulation
- Solved
- No attempts yet
Statement
General Grievous is a master of the lightsaber. His skill is so high that he can use lightsabers at the same time. However, after sensing the superiority of Anakin and Obi-Wan in battle, he decides to retreat from the battlefield. To do so, he plans to stun them with a grenade he saved for a situation like this. The grenade explodes exactly seconds after it is activated. Using a clock to measure that interval is wasteful, so he wants to use something else.
After new software was installed on the lightsabers, they began to drain faster. Each of the lightsabers runs out after seconds of continuous operation of one blade. If it is on from both sides, it runs out after seconds. At the start, Grievous can turn on some lightsabers on some sides and fight with them. Then, as soon as any lightsaber runs out, he can change the state of some lightsabers at that same moment, until the next one runs out.
Grievous wants to fight so that he can measure exactly the time needed for the grenade to explode. Check whether he can do this. Grievous can activate the grenade together with any of the lightsabers, and the grenade must explode at the moment some lightsaber runs out.
Suppose he has two lightsabers, each lasting four seconds, and the grenade timer is one second. He fights as follows. First he turns on the first lightsaber from both sides and the second from one side. When the first one runs out, he activates the grenade and turns the second lightsaber on from its second side. At the moment the grenade is activated, the second lightsaber has two minutes left to run. After it is turned on from the second side, its remaining time drops to one minute, which is exactly what is needed.