Under construction

Still being built. Things may change

General Grievous

Time limit2sMemory limit1024 MB

Summary
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 nn 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 tt 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 nn lightsabers runs out after mm seconds of continuous operation of one blade. If it is on from both sides, it runs out after m2\frac{m}{2} 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.

Examples3

  1. Example 1

    Input
    2 1 4
    
    Expected output
    Yes
    
  2. Example 2

    Input
    5 640 128
    
    Expected output
    Yes
    
  3. Example 3

    Input
    2 1 8
    
    Expected output
    No