## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# An interesting game challenge

Problem statement
Andy loves playing games. He wants to play a game with his little brother, Bob, using an array, , of distinct integers. The rules are as follows:

• Bob always plays first and the two players move in alternating turns.
• In a single move, a player chooses the maximum element currently present in the array and removes it as well as all the other elements to its right. For example, if , then it becomes after the first move because we remove the maximum element (i.e., ) and all elements to its right (i.e., and ).
• The modifications made to the array during each turn are permanent, so the next player continues the game with the remaining array. The first player who is unable to make a move loses the game.

Andy and Bob play games. Given the initial array for each game, can you find and print the name of the winner on a new line? If Andy wins, print ANDY; if Bob wins, print BOB.

Input Format
The first line contains a single integer denoting (the number of games). The subsequent lines describe each game array over two lines:

1. The first line contains a single integer, , denoting the number of elements in .
2. The second line contains distinct space-separated integers describing the respective values of for array .

Constraints
Array contains distinct integers.

The sum of over all games does not exceed .

Output Format
For each game, print the name of the winner on a new line (i.e., either BOB or ANDY).

Sample Input 0

2
5
5 2 6 3 4
2
3 1


Sample Output 0

ANDY
BOB


Explanation 0
Andy and Bob play the following two games:

1.
Initially, the array looks like this:

In the first move, Bob removes and all the elements to its right, resulting in :

In the second move, Andy removes and all the elements to its right, resulting in :

At this point, the array is empty and Bob cannot make any more moves. This means Andy wins, so we print ANDY on a new line.

2.
In the first move, Bob removes and all the elements to its right, resulting in . As there are no elements left in the array for Andy to make a move, Bob wins and we print BOB on a new line.

Solution

public class AnInterestingGame {
private static final String BOB = "BOB";
private static final String ANDY = "ANDY";

private static void solve(int[] a, int start, int end, String player) {
if (start > end) {
System.out.println(player.equals(BOB) ? ANDY : BOB);
} else {
int max = Integer.MIN_VALUE;
int maxIdx = -1;
for (int i = start; i <= end; i++) {
if (a[i] > max) {
max = a[i];
maxIdx = i;
}
}

solve(a, start, maxIdx - 1, player.equals(BOB) ? ANDY : BOB);
}

}

public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
Scanner in = new Scanner(System.in);
int games = in.nextInt();
for (int g = 0; g < games; g++) {
int n = in.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = in.nextInt();
}

solve(a, 0, a.length - 1, BOB);
}
}
}