不知不覺畢業(yè)五年了，看了下 poj蜻懦，上一次 submmit 竟然是在 13 年 10 月份宛乃，逝者如斯运授。
具體代碼如下吁朦，以后有時(shí)間再更新思路逗宜。
#include <iostream>
// 用來(lái)記錄結(jié)果空骚，避免重復(fù)計(jì)算
int result[20] = {0};
// n 為最終的結(jié)果囤屹，k 為人數(shù)逢渔，這個(gè)函數(shù)是用來(lái)計(jì)算兩個(gè)值是否匹配
bool isRight(int n, int k) {
//代表每一輪剩余的數(shù)量
int remain[20] = {0};
remain[0] = 0;
for (int t = 1; t <= k; t ++) {
// 每一輪單位長(zhǎng)度
int unitLength = 2 * k - t + 1;
int lengthForThisTurn = n - remain[t - 1];
if (lengthForThisTurn <= k) {
return false;
}
if (lengthForThisTurn <= unitLength) {
remain[t] = unitLength - lengthForThisTurn;
} else if (lengthForThisTurn > unitLength) {
int remainder = lengthForThisTurn % unitLength;
if (remainder == 0) {
remain[t] = 0;
} else if (remainder > k) {
remain[t] = unitLength - remainder;
} else {
return false;
}
}
}
return true;
}
// 計(jì)算總的數(shù)量智厌，有剪枝
int calculateJosef(int k) {
int i = 1;
while (true) {
int n = i * (k + 1);
if(isRight(n, k)) {
return n;
}
if (isRight(n + 1, k)) {
return n + 1;
}
i ++;
}
}
int main(int argc, const char * argv[]) {
int k;
while (scanf("%d", &k) && k != 0) {
if (result[k] == 0) {
result[k] = calculateJosef(k);
}
printf("%d\n", result[k]);
}
return 0;
}
