Number Cutting Game

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2848
64-bit integer IO format: %I64d      Java class name: Main

Description

Two boys boyA and boyB are playing a simple game called Number Cutting Game. Now I will introduce it to you, my friend.

At the beginning of the game, a machine will generate two numbers, N(10 < N < 10 ^ 19) and K(2 <= K <= length(N)). Then boyA and boyB are take turns to play it:

When one player receives two numbers N and K, his task is to cut N into K nonempty pieces. If length(N) < K, that is to say he can not able to cut, he loses the game. Otherwise, he adds these K pieces together and get the sum SUM. Then let N = SUM and throw N and K to another player.

We assume boyA receives the two numbers from the machine firstly and they are smart enough to choose the best strategy for himself.
Now please help boyA to calculate weather he can win if he receives N and K firstly.

Here is a sample for you N = 103, K = 2.
Fisrtly, boyA receives N = 103, K = 2. He has two ways to cut like: 1|03 => 1 + 03 = 4, or 10|3 => 10 + 3 = 13.
Then, boyB receives from boyA. If boyB receives N = 4, K = 2, he loses the game. If boyB receives N = 13 and K = 2, he has only one way to cut: 1|3 = 1 + 3 = 4, then he will win the game.
So you can see boyA will win if he choose the best strategy.

Input

No more than 1000 cases. Each contains two line, first line an integer N(10 < N < 10 ^ 19), second line K(2 <= K <= length(N)).

Output

If boyA can win, print 1, otherwise 0.

Sample Input

103
2
999999999999999999
2

Sample Output

1
0

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .