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

Besides, there have Ma special number for Pooh, k1k2...kMa, 

means that if in Pooh's turn(haven't taken), the remaining number of jars is either k1,k2,..., or kMa, then Pooh wins.

Also have Mb special number for Piglet, l1 l2...lMb, 

means that if in Piglet's turn(haven't taken), the remaining number of jars is either l1,l2,..., or lMb, then Piglet wins.

Give you N, A, B, Ma, Mb, Who start first, k1 k2...kMa, l1 l2...lMb

Please answer who will win if Pooh and Piglet play the best. 

 

Example 1:

N = 6, A = 2, B = 2, Ma = 0, Mb = 0

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.

 

Example 2:

N = 6, A = 2, B = 1, Ma = 0, Mb = 2

l1 = 3, l2 = 4

The table shows the winner

You can notice that when N=3, A=2, B=1, and it's Piglet's turn, Piglet originally will lose since Piglet left 2 jars of honey after taking 1, and Pooh can take the remaining 2.

        However, since I1 = 3, Piglet wins.

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<=20)

Each test first line you are given integers N, A, B, Ma, Mb and Who start first(Pooh or Piglet).

(1<= N, A, B, Ma, Mb <=100000)

The second line contains Ma integers k1 k2...kMa.(1<= k1 k2...kMa <=N)

The third line contains Mb integers l1 l2...lMb.(1<= l1 l2...lMb <=N)

 

Limit:

Testcase 1: N ≤ 10, A = B ≤ 10, Ma = Mb = 0

Testcase 2: N ≤ 10, max{A, B} ≤ 10, Ma = Mb= 0

Testcase 3: N ≤ 100, max{A, B} ≤ 10, max{Ma, Mb} ≤ 100

Testcase 4: N ≤ 10000, max{A, B} ≤ 10, max{Ma, Mb} ≤ 100

Testcase 5: N ≤ 100000, max{A, B} ≤ 10, max{Ma, Mb} ≤ 100000

(advance) 

Testcase 6: N ≤ 100000, max{A, B} ≤ 100000, max{Ma, Mb} ≤ 100000

Hint: If there is a state (x jars of honey) someone will lose, it will make the other win if (x+1, x+2, ... x+y) jars of honey left. Try to use Loop, and prefix sum to maintain it.

 

Output

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

Sample Input  Download

Sample Output  Download

Tags




Discuss