Infinity Xor

1.5

2 votes
Logic-Based, Easy, Game Theory
Problem

Ironman and Thanos are playing the game of Infinity Xor with an array of non-negative integers. They take alternate turns.

Let the size of the array at the beginning of each turn be n. Initially n=N=2x ,where x is some non-negative integer . During a player's turn he can choose any n/2  elements from the array such that their XOR is Odd and discard the remaining n/2 elements. The new array for the next turn contains the n/2 elements chosen in this turn. 

A player loses if n is odd or if he cannot choose n/2 elements such that their XOR is Odd. Decide the winner if both the players play optimally. Ironman plays first.

Input:

  • The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
  • The first line of each test case contains a single integer N.
  • The next line contains N space-separated integers A1,A2,....,AN

Output:

  • For each test case, print the winner of the game "IRONMAN" or "THANOS" (without quotes).
  • Answer for each test case should come in a new line.

Constraints:

  • 1T20
  • 1N220
  • 0Ai109
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
  • First, IRONMAN chooses (1,4)  from [1,2,3,4]. Now new Array For next turn becomes [1,4]
  • Next THANOS chooses (1) from [1,4]. Now new array for next turn becomes [1].
  • Now, IRONMAN is not able to divide the array in two halves. He loses. 
Editor Image

?