| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 13359 | Honey Game Ⅱ |
|
| 13369 | Fibonacci Sequence |
|
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:
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
Description
In this problem, you are asked to help us develop a method to compute the n-th term, Fn, of the fibonacci sequence. The fibonacci sequence is a recursive sequence defined as Fi=Fi-1+Fi-2, where we let F0=0, F1=1 in this problem. This recursive relation can be written as a matrix multiplication:
and this is the general form of Fn and Fn+1:
This problem is a partial judge problem. You are asked to design a function to calculate (Ab % m) where A is a 2x2 matrix and b,m are integers. Then, using your function and the matrix equation above, we are able to compute our desired Fn of the fibonacci sequence. For the details, please check the main() function carefully.
The power computation for integers ...
Given integers a, b and m, calculating the answer of (ab % m) may be trivial for you because it can be solved by using a single for loop:
, or a recursive way:
if (b == 0) return 1;
return a * pow(a, b-1);
}
However, this isn't the best way to do so since its time complexity is O(b). In other words, it requires b times of steps, so it may not be able to finish the task in a second if b is large (e.g. b <= 1018).
Therefore, we have another better algorithm to achieve it. Define a function P(a,b)=ab. For P(a,b), we don't need the answer of P(a, b-1). Instead, we are interested in the answer of P(a, b/2). To explain why, we discuss in two cases of P(a,b):
- b is even: ab = ab/2 * ab/2
- b is odd: ab = ab/2 * ab/2 * a
The code below is a demonstration of this simple algorithm.
if (b==0) return 1;
int t = pow1(a, b/2);
if (b%2 == 0) t = t * t % m;
else t = t * t % m * a % m;
return t;
}
Next, we want to analyze the time complexity, or, the steps required to solve this problem. Since pow(a,b) will only call the function pow(a,b/2) once, there're log2(b) of steps. Therefore, the time complexity is O(log(b)), which is much more efficient than the original method O(b).
Note that the following implementation can give the right answer, but the time complexity is still O(b). It is recommended to figure the reason out with your thoughts.
if (b==0) return 1;
if (b%2 == 0) return pow2(a, b/2) * pow2(a, b/2) % m;
else return pow2(a, b/2) * pow2(a, b/2) % m * a % m;
}
In this problem ...
In this problem, for us to compute Fn of the fibonacci sequence, you are asked to design a function to calculate (Ab % m) where A is a 2x2 matrix and b,m are integers.
This function has the following prototype, as declared in function.h:
}
- Note 1: The 2x2 matrix A is represented as a 1-D long long int array of length 4, which is in the following format:
.
- Note 2: Please malloc a 1-D long long int array of length 4 in matrix_pow() to store the computed (Ab % m), and return the address of this malloced dynamic array as the function's return value.
- Note 3:
A0=
, the 2x2 identity matrix.
- Note 4: You can consider to define/implement other function(s) in your function.c to help complete the design of your matrix_pow(), if you feel necessary.
Input
The input only consists of two integers n and m, where 0 <= n <= 1018, 0 < m <=2*109.
Output
Output Fn % m in a single line.