Odd and Even Game
InterviewTime limit1sMemory limit1024 MB
Two players alternately take cards, and after each player's first card, every card they take must share its parity. Determine the winner under optimal play.
- Level
Medium5 of 10
- Topics
- Game theory, Dynamic programming
- Solved
- No attempts yet
Problem
cards are laid out in a row on the floor from left to right. The card at position from the left has the integer written on its front face.
Chaewan plays an odd-even card game with Heeda. The rules are as follows.
-
The two players take turns, and Chaewan goes first.
-
On each turn, a player picks one card from the cards remaining on the floor and takes it. A player may only take a card that satisfies the following condition.
- There is no restriction on the first card a player takes.
- Every card a player takes after the first must have the same parity as the first card that player took.
-
A player who cannot take any card on their turn loses.
Assuming both players play optimally, determine the winner of the game.
Input
The first line contains the number of test cases .
Each test case follows on the next lines. A test case consists of two lines. The first line contains the number of cards .
The second line contains the integers written on each card, separated by spaces.
Output
For each test case, print one line. Print amsminn if Chaewan wins, and heeda0528 if Heeda wins.