F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Number Cutting Game

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 634    Accepted Submission(s): 251


Problem 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
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 07:26:27, Gzip enabled