13366 - Honey Game   

Status  |  Limits Submit

Description

Winnie the Pooh and Piglet are fighting for N  jars of honey.

Pooh can carry 1~A  jars of honey at a time, Piglet can carry 1~B jars of honey at a time.

Two players take turns.

Whoever can grab the last jar of honey will win.

Give you N, A, B, Who start first, please answer who will win if Pooh and Piglet play the best. 

 

Example:

N = 6, A = 2, B = 2

The table shows the winner

          If Pooh goes first, even Pooh carry 1 or 2 jars of honey(leave 5 or 4 jars of honey to Piglet), 

        Piglet can leave 3 jars of honey to Pooh.

        Now there are 3 jars of honey left, even Pooh carry 1 or 2 jars of honey, Piglet can grab the last jar.

           

Hint:

int Pooh_turn(int n){                 //return Pooh will win or not if N jars of honey left
     ...
    if( !Piglet_turn(n-1) || ...  !Piglet_turn(n-a) ) return true;         
                                                       //If there is a state Piglet will lose, then Pooh should choose it to win
    else return false;
}
 
int Piglet_turn(int n){               //return Piglet will win or not if N jars of honey left
     ...
    if( !Pooh_turn(n-1) || ...  !Pooh_turn(n-b) ) return true;
    else return false;
}

Input

The first line you are given an integer T, means there will be T tests.(1 ≤ T ≤ 10)

Each test you are given integers N, A, B, and Who starts first(Pooh or Piglet).

(1 ≤ A, B ≤ 10, 1 ≤ N ≤ 10000)

 

Limit:

Testcase 1: N ≤ 10, A = B ≤ 10

Testcase 2~3: N ≤ 10, max{A, B} ≤ 10

Testcase 4~5: N ≤ 10000, max{A, B} ≤ 10

Output

Each test output the winner is Pooh or Piglet, and a new line.

Sample Input  Download

Sample Output  Download

Tags




Discuss