2014
02-17

# Number Cutting Game

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.

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.

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

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

103
2
999999999999999999
2

1
0

#include <stdio.h>
#include <iostream>
using namespace std;
typedef long long LL;

LL base[22];

void makeBase() {
base[0] = 1;
for (int i = 1; i < 22; i++) {
base[i] = base[i - 1] * 10;
}
}

bool DFS(LL, int);

bool test(LL n, int d, int k, LL cur) {
if (d == k) {
return !DFS(cur + n, k);
} else {
for (int i = 1; i < 22; i++) {
LL a = n % base[i];
LL b = n / base[i];
if (b == 0) {
break;
} else if (test(b, d + 1, k, cur + a)) {
return true;
}
}
return false;
}
}

bool DFS(LL n, int k) {
if (n < base[k - 1]) {
return false; // lose
} else {
return test(n, 1, k, 0);
}
}

int main() {
makeBase();
LL n;
int k;
while (cin >> n >> k) {
bool flag = DFS(n, k);
printf ("%d\n", flag);
}
return 0;
}

1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。