Bob vs ATM
All submissions for this problem are available.
Due to shortage of ATMs, a bank decided to convert some arcade gaming machines into ATMs. Unfortunately, due to a bug, the converted machine will only dispense cash if the withdrawer can win the game. The game is played over a valid bracket sequence. Formally a valid bracket sequence is defined as:
- An empty string is valid
- If A is a valid bracket sequence, then (A) is also valid
- If A and B are valid, AB is also valid
In each move a player can erase such a non-empty valid sub-string of the remaining brackets such that they cannot be formed by concatenating 2 valid sequences. E.g. a player can erase (()) or (()()) but not ()() or (())(). The ATM always plays first. The player that is not able to make a move will lose the game. Assume that both the players play optimally.
Bob is trying to withdraw money and is frustrated as he keeps losing against the machine. He suspects the machine is rigged and always wins the game. So, he has asked you to help him out. Given a valid bracket sequence, can you determine who wins the game?
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each of the test case consists of a single line containing the string S - the initial bracket sequence.
For each test case, output a single line containing the winner - either "ATM" or "Bob" without quotes.
- 1 ≤ T ≤ 105
- 2 ≤ length of S ≤ 105
- The sum of all lengths of S will be not more than 106
- S will be a valid bracket sequence
Input: 5 () (()()(())) ()() (())() (()()(()))((())) Output: ATM ATM Bob ATM Bob
Example case 1. The ATM will erase the entire sequence and win the game
Example case 2. The ATM will again erase the entire sequence and win the game
Example case 3. The ATM can erase either the first or the second (), Bob will erase the other one and win
|Tags||admin3, amr16, icpc2016|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.