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. }

UVa - 490 - Rotating Sentences

Problem link:
490 - Rotating Sentences

Solution:

1. #include <bits/stdc++.h>
2. using namespace std;
3. typedef long long LL;
4. const int S = 103;
5. const int MOD = 1e9+7;
6. const double pi = 2 * acos (0.0);
7. int _I(){int x; scanf("%d", &x); return x;}
8. LL _LL(){LL x; scanf("%lld", &x); return x;}
9. int dirX[]={1, 0, -1, 0, 1, -1, 1, -1};
10. int dirY[]={0, 1, 0, -1, 1, -1, -1, 1};
11. int rX[] = {1, 1, 2, 2, -1, -1, -2, -2};
12. int rY[] = {2, -2, 1, -1, 2, -2, 1, -1};
13.  
14. template <class T> T Distance(T x1, T y1, T x2, T y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));};
15.  
16. int sset(int N, int pos){return N=N|(1<<pos);}
17. bool check(int N, int pos){return (bool)(N&(1<<pos));}
18. int reset(int N, int pos){return N=N&~(1<<pos);}
19. ///...............Code Starts From Here...............///
20.  
21. char s[S][S];
22.  
23. int main(){
24.     int k = 0, mx = 0;
25.     memset(s, ' ', sizeof(s));
26.     while(gets(s[k])){
27.         int sz = strlen(s[k]);
28.         s[k][sz] = 32;
29.         mx = max(mx, sz);
30.         k++;
31.     }
32.     for(int i = 0; i < mx; i++){
33.         for(int j = k-1; j >= 0; j--){
34.             printf("%c", s[j][i]);
35.         }
36.         puts("");
37.     }
38.     return 0;
39. }

UVa - 306 - Cipher

Problem link:
306 - Cipher

Solution:

1. #include <bits/stdc++.h>
2. using namespace std;
3. typedef long long LL;
4. const int S = 203;
5. const int MOD = 1e9+7;
6. const double pi = 2 * acos (0.0);
7. int _I(){int x; scanf("%d", &x); return x;}
8. LL _LL(){LL x; scanf("%lld", &x); return x;}
9. int dirX[]={1, 0, -1, 0, 1, -1, 1, -1};
10. int dirY[]={0, 1, 0, -1, 1, -1, -1, 1};
11. int rX[] = {1, 1, 2, 2, -1, -1, -2, -2};
12. int rY[] = {2, -2, 1, -1, 2, -2, 1, -1};
13.  
14. template <class T> T Distance(T x1, T y1, T x2, T y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));};
15.  
16. int sset(int N, int pos){return N=N|(1<<pos);}
17. bool check(int N, int pos){return (bool)(N&(1<<pos));}
18. int reset(int N, int pos){return N=N&~(1<<pos);}
19. ///...............Code Starts From Here...............///
20.  
21. char ans[S];
22. char input[S];
23. int number[S];
24.  
25. int main(){
26.     int n;
27.     while(scanf("%d", &n) == 1 && n){
28.         for(int i = 0; i < n; i++)number[i] = _I()-1;
29.         int k;
30.         while(scanf("%d", &k) == 1 && k){
31.             getchar();
32.             gets(input);
33.             memset(ans, ' ', sizeof(ans));
34.             int ind, cn;
35.             for(int i = 0; input[i]; i++){
36.                 ind = i, cn = 0;
37.                 int f = 0;
38.                 while(cn < k){
39.                     if(ind == i && f){
40.                         f = 2;
41.                         break;
42.                     }
43.                     ind = number[ind];
44.                     cn++, f = 1;
45.                 }
46.                 int p = k%cn;
47.                 if(f == 2){
48.                     ind = i, cn = 0;
49.                     while(cn < p){
50.                         ind = number[ind];
51.                         cn++;
52.                     }
53.                 }
54.                 ans[ind] = input[i];
55.             }
56.             for(int i = 0; i < n; i++)printf("%c", ans[i]);
57.             puts("");
58.         }
59.         puts("");
60.     }
61.     return 0;
62. }

UVa - 11044 - Searching for Nessy

Problem link:
11044 - Searching for Nessy

Solution:

1. #include <bits/stdc++.h>
2. using namespace std;
3. typedef long long LL;
4. const int S = 300003;
5. const int MOD = 1e9+7;
6. const double pi = 2 * acos (0.0);
7. int _I(){int x; scanf("%d", &x); return x;}
8. LL _LL(){LL x; scanf("%lld", &x); return x;}
9. int dirX[]={1, 0, -1, 0, 1, -1, 1, -1};
10. int dirY[]={0, 1, 0, -1, 1, -1, -1, 1};
11. int rX[] = {1, 1, 2, 2, -1, -1, -2, -2};
12. int rY[] = {2, -2, 1, -1, 2, -2, 1, -1};
13.  
14. template <class T> T Distance(T x1, T y1, T x2, T y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));};
15.  
16. int sset(int N, int pos){return N=N|(1<<pos);}
17. bool check(int N, int pos){return (bool)(N&(1<<pos));}
18. int reset(int N, int pos){return N=N&~(1<<pos);}
19. ///...............Code Starts From Here...............///
20.  
21. int main(){
22.     int t = _I();
23.     while(t--){
24.         int n = _I(), m = _I();
25.         n /= 3;
26.         m /= 3;
27.         n *= m;
28.         printf("%d\n", n);
29.     }
30.     return 0;
31. }