Alice and Bob are playing a game with marbles; you may have played this game in childhood. The game is playing by alternating turns. In each turn a player can take exactly one or two marbles.

Both Alice and Bob know the number of marbles initially. Now the game can be started by any one. But the winning condition depends on the player who starts it. If Alice starts first, then the player who takes the last marble loses the game. If Bob starts first, then the player who takes the last marble wins the game.

Now you are given the initial number of marbles and the name of the player who starts first. Then you have to find the winner of the game if both of them play optimally.

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains an integer n (1 ≤ n < 2³¹) and the name of the player who starts first.

Output

For each case, print the case number and the name of the winning player.

Sample

Sample Input	Sample Output
Click to copy 3 1 Alice 2 Alice 3 Bob	Click to copy Case 1: Bob Case 2: Alice Case 3: Alice

Total Submissions

Users Tried

Users Solved

LOJ 1020 - A Childhood Game

Summary

In this problem, you have to find the winner of the game if both Alice and Bob play optimally.

The game is playing by alternating turns. In each turn a player can take exactly 1 or 2 marbles.

Both of them know the number of marbles initially. Now the game can be started by any one. But the winning condition depends on the player who starts it. If Alice starts first, then the player who takes the last marble looses the game. If Bob starts first, then the player who takes the last marble wins the game.

Hint

Consider both of them different case. Start from 1 marbel and gradually increase the marbel. Try to find a pattern.

Solution

Approach

Lets consider '1' as first move and '2' as 2nd move. we will try to win first move(1) if possible.

If Alice start first,

If N = 1 2 wins. who takes last loses
If N = 2 1 wins. Alice takes 1 marbel and bob have to take last one.
If N = 3 1 wins. Alice takes 2 marbel and bob have to take last one.
If N = 4 2 wins. why ? if he takes 1 marbel opposite N(4-1) = 2 and if he takes 2 marbel opposite N(4-2) =2, So it is garanted 2 wins. continue this process you will find pattern of 2 1 1 2 1 1 ...

similar;y If Bob start first, you will find pattern of 1 1 2 1 1 2 ...

Time Complexity: O(1) per test case.
Memory Complexity: O(1) per test case.

Code

C++


#include <bits/stdc++.h>
using namespace std ;

void _main_main()
{
    int n ;
    string s ;
    cin >> n >> s ;
    if(s == "Alice"){
        if (n%3 == 1) cout << "Bob\n" ;
        else cout << "Alice\n" ;
    }
    else {
        if (n%3 != 0) cout << "Bob\n" ;
        else cout << "Alice\n" ;
    }
}

int main ()
{
    int testCase = 1 ; cin >> testCase ;
    for (int i = 0; i < testCase; i++){
        cout << "Case " << i+1 << ": " ;
        _main_main() ;
    }
}

Happy Coding!

Written by: Moontasir Mahmood

Tutorial source