Just a Nim game? - MarisaOJ: Marisa Online Judge

Just a Nim game?

Time limit: 500 ms
Memory limit: 128 MB
Unsatisfied with Reimu and Marisa's proclaimed "too simple" game (see the problem Just a Nim game), Patchouli challenges Marisa an improved version of this game. The new game's rules are as the following: - Patchouli will use Marisa's $n$ baskets of gathered mushrooms. - Each turn, the player takes away an arbitrarily large pile of mushrooms (greater than $0$) from any basket. - However, the first person unable to do this **wins** the game. Patchouli has $t$ challenges respective to $t$ days of the Gensokyo festival. Marisa was initially the first player, but Patchouli allows her to switch turn, and declares to play optimally. If Marisa can't win the challenges, Patchouli won't give this year's donation to the Hakurei shrine ToT. Help Marisa decide whether she should switch her turn! ### Input - The first line consists of an integer $t$ - the duration of the festival in days. - The next $t$ groups of lines come under the form of: - The first line consists of an integer $n$ - the number of baskets. - The next line contains $n$ integers $A_i$..., representing the number of mushrooms in each baskets. ### Output Print $t$ lines, each line is "DA", if Marisa should switch turn, and "ZE", if otherwise. ### Constraints - $1 \le t \le 1000$. - $1 \le n \le 10^5$. - $1 \le A_i \le 10^{10}$. It is guaranteed that the total number of baskets Marisa can gather across all days does not exceed $10^6$. ### Example Input: ``` 3 3 1 2 3 2 1 1 5 1 3 5 7 8 ``` Output: ``` DA DA ZE ```
Topic
Game Theory
Rating 1400
Source VNOI
Solution (0) Solution