> A young Jedi named Darth Vader, who was a pupil of mine until he turned to evil, helped the Empire hunt down and destroy the Jedi Knights. He betrayed and murdered your father. Now the Jedi are all but extinct."
>
> --- Obi-Wan Kenobi, to Luke Skywalker
> The Jedi Purge was the period in which the Jedi Order was destroyed by the Sith and the Jedi were hunted by the Galactic Empire to near-extinction.
>
> --- Wookieepedia
In the Jedi Temple, the 501-st Legion headed by Darth Vader are having an intense battle with the Jedi. The Jedi Temple can be seen as an n×m matrix. There are Meditations that can enhance the force and pollutant sources from the dark side that weaken the force. There are some crystals in the Temple. Vader and Jedi master Yoda are playing a game, which is moving the crystals in turns.
Each turn, the player can choose a cell (x,y) with crystals. Suppose that there are w crystals in (x,y), the player can pick up t(1≤t≤w) crystals. If there is a Meditation in (x,y), because of the amazing power of Meditation, the player can produce t extra crystals: he can place t crystals in (x+1,y) and t crystals in (x,y+1). Otherwise (there is no Mediation in (x,y)), the player can just place t crystals in (x+1,y) *or* place t crystals in (x,y+1).
However, if t crystals are put into a cell (x,y) where there is a pollutant source, ⌈t2⌉ crystals will be destroyed and only ⌊t2⌋ are saved.
Besides, there is a super pollutant source in (n,m), and it will destroy all crystals put into (n,m). To control this darkness, there is a Meditation in (n−1,m).
In addition, there is a force field outside the Jedi Temple, which means that you can not move any crystals outside the matrix. That is to say:
- If you should put k crystals into (x+1,y) and k crystals into (x,y+1), but (x+1,y) is outside the matrix, then you can only put 2k crystals into (x,y+1). Similarly, you can only put 2k crystals into (x+1,y) if (x,y+1) is outside the matrix.
- If you can choose to put k crystals into (x+1,y) or (x,y+1) but one of them is outside the matrix, you can only put the crystals into the other one.
The one who cannot move any crystal will lose the game. Both Darth and Yoda are smart and will always choose the optimal strategy. Now, Vader is playing first, can he win the game and evade the Jedi Temple?
Because of the collision of Meditations and pollutant sources, for every pair of Meditations (x,y) and pollutant sources (a,b),
>
> --- Obi-Wan Kenobi, to Luke Skywalker
> The Jedi Purge was the period in which the Jedi Order was destroyed by the Sith and the Jedi were hunted by the Galactic Empire to near-extinction.
>
> --- Wookieepedia
In the Jedi Temple, the 501-st Legion headed by Darth Vader are having an intense battle with the Jedi. The Jedi Temple can be seen as an n×m matrix. There are Meditations that can enhance the force and pollutant sources from the dark side that weaken the force. There are some crystals in the Temple. Vader and Jedi master Yoda are playing a game, which is moving the crystals in turns.
Each turn, the player can choose a cell (x,y) with crystals. Suppose that there are w crystals in (x,y), the player can pick up t(1≤t≤w) crystals. If there is a Meditation in (x,y), because of the amazing power of Meditation, the player can produce t extra crystals: he can place t crystals in (x+1,y) and t crystals in (x,y+1). Otherwise (there is no Mediation in (x,y)), the player can just place t crystals in (x+1,y) *or* place t crystals in (x,y+1).
However, if t crystals are put into a cell (x,y) where there is a pollutant source, ⌈t2⌉ crystals will be destroyed and only ⌊t2⌋ are saved.
Besides, there is a super pollutant source in (n,m), and it will destroy all crystals put into (n,m). To control this darkness, there is a Meditation in (n−1,m).
In addition, there is a force field outside the Jedi Temple, which means that you can not move any crystals outside the matrix. That is to say:
- If you should put k crystals into (x+1,y) and k crystals into (x,y+1), but (x+1,y) is outside the matrix, then you can only put 2k crystals into (x,y+1). Similarly, you can only put 2k crystals into (x+1,y) if (x,y+1) is outside the matrix.
- If you can choose to put k crystals into (x+1,y) or (x,y+1) but one of them is outside the matrix, you can only put the crystals into the other one.
The one who cannot move any crystal will lose the game. Both Darth and Yoda are smart and will always choose the optimal strategy. Now, Vader is playing first, can he win the game and evade the Jedi Temple?
Because of the collision of Meditations and pollutant sources, for every pair of Meditations (x,y) and pollutant sources (a,b),
max(|(x−a)+(y−b)|,|(x−y)−(a−b)|)
is constrained to be an odd number.