Hackerrank - HourRank 15 - Gaming Array

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.

For  of the maximum score:

• The sum of  over all games does not exceed .

For  of the maximum score:

• 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 ANDYon 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:

1. #include <bits/stdc++.h>
2. #define pb push_back
3. using namespace std;
4. typedef long long LL;
5. const int S = 100003;
6. const int MOD = 1e9+7;
7. const double pi = 2 * acos (0.0);
9. int _Int(){int x; scanf("%d", &x); return x;}
10. LL _LLi(){LL x; scanf("%lld", &x); return x;}
11. void pruts(){puts("-1");exit(EXIT_SUCCESS);}
13. int dirX[] = { 1, 0, -1, 0, 1, -1, 1, -1 };
14. int dirY[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
15. int rX[] = { 1, 1, 2, 2, -1, -1, -2, -2 };
16. int rY[] = { 2, -2, 1, -1, 2, -2, 1, -1 };
18. template < class T > T tri_Area( T x1, T y1, T x2, T y2, T x3, T y3 ){ return abs( x1*( y2-y3 ) - y1*( x2-x3 ) + ( x2*y3-x3*y2 ) );};
19. template < class T > T Distance( T x1, T y1, T x2, T y2 ){ return sqrt( ( x1-x2 ) * ( x1-x2 ) + ( y1-y2 ) * ( y1-y2 ) ); };
20. template < class T > T bigMod( T n, T p, T m ){ if( p == 0 )return 1; if( p&1 )return ( n*bigMod( n, p-1, m ) )%m; T x = bigMod( n, p/2, m ); return ( x*x )%m; };
22. int sset(int N, int pos){return N=N|(1<<pos);}
23. bool check(int N, int pos){return (bool)(N&(1<<pos));}
24. int reset(int N, int pos){return N=N&~(1<<pos);}
25. /*******************###########################################********************
26. ********************##   MD. YA-SEEN ARAFAT(ThunderStroke)   ##********************
27. ********************##    CSE, University of Asia Pacific    ##********************
28. ********************###########################################********************/
30. struct data{
31.     int val, ind;
32. }A[ 100000+3 ];
34. bool cmp( data p, data q ){
35.     return p.val > q.val;
36. }
38. void Love(){
39.     int t = _Int();
40.     while( t-- ){
41.         int n = _Int();
42.         for( int i = 0; i < n; i++ ){
43.             A[ i ].val = _Int();
44.             A[ i ].ind = i;
45.         }
46.         sort( A, A+n, cmp );
47.         int one = 0, last = n;
48.         for( int i = 0; i < n; i++ ){
49.             if( last > A[ i ].ind ){
50.                 if( one ) one = 0;
51.                 else one = 1;
52.                 last = A[ i ].ind;
53.             }
54.         }
55.         if( !one )puts( "ANDY" );
56.         else puts( "BOB" );
57.     }
58. }
60. int main(){
61.     #ifndef ONLINE_JUDGE
62. //        freopen("in.txt", "r", stdin);
63. //        freopen("n.txt", "w", stdout);
64.     #endif
65.     Love();
66.     return 0;
67. }