Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Lucky Stone Game

By Bishal_G · Limits 1s, 512 MB

Alice and Bob are playing a stone game. They consider 4 and 7 as lucky numbers and they like to make use of these numbers in the game. Initially there are n piles of stones and each pile contains m stones.

In each move a player can either remove any of lucky number of piles of stones from the game (i.e. remove either 4 or 7 piles) or a player can reduce the size of each pile by dividing it by the highest possible lucky number given the pile size is divisible by that number. If pile size is not divisible by any of the lucky numbers then they reduce the pile size to m/3 stones from every piles.

For example, if there are 10 piles containing 10 stones each, then in one turn, a player can do one of the following:

  • Reduce every pile size to 10/3 = 3, making all the 10 piles contain 3 stones each
  • Remove 4 piles from the game, leaving 6 piles containing 10 stones each
  • Remove 7 piles from the game, leaving 3 piles containing 10 stones each

Alice starts the game and the players alternate turns removing stones from the pile. The player who cannot make a valid move loses. Now given the number of piles and the number of stones in each pile at the beginning of the game, you have to find the player who wins given both players play optimally.


Input starts with an integer T (1 ≤ T ≤ 10000), denoting the number of test cases. Each case starts with a line containing two integers n (1 ≤ n ≤ 100000) and m(1 ≤ m ≤ 10^9) as described in the problem statement.


For each case, print the case number and the name of the player who will win the game.


10 10
5 10
Case 1: Alice
Case 2: Bob



38% Solution Ratio

SwampFireEarliest, Sep '19

Deshi_TouristFastest, 0.0s

YouKnowWhoLightest, 262 kB

magic_kiriShortest, 433B


Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.