Responsive image

问题 1875 --Galaxy at War

1875: Galaxy at War

时间限制: 4 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

> 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),
max(|(x−a)+(y−b)|,|(x−y)−(a−b)|)
is constrained to be an odd number.
 

输入描述

The first line of the input contains an integer T, denoting the number of test cases.
For each test case, the first line contains two integers n,m (1≤n,m≤10^3). 
The next line contains an integer k (0≤k≤5×10^5), denoting the number of places containing crystals. 
Each of the following k lines contains three integers x,y,w, representing that there are w (1≤w≤10^9) crystals in cell (x,y). 
The next line contains an integer t (0≤t≤5×10^5). 
Each of the following t lines contains two integer x,y, which means that there is a Meditation in (x,y). 
The next line contains an integer s (0≤s≤5×10^5). 
Each of the following s lines contains two integer x,y, which means that there is a pollutant sources in (x,y). 
All x and y satisfy 1≤x≤n,1≤y≤m.
 

输出描述

Output “win” if Vader can win the game, otherwise output “lose”.
 

样例输入

1
2 2
1
1 1 1
1
1 2
1 
2 2

样例输出

lose

来源

 

[提交][状态]
ACM算法攻关部
  • Anything about this OnlineJudge, Please Contact Administrator. Click add QQ

    OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap

    Copyright 2016 ACM算法攻关部
    关于网站改版