Bash游戏
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1066
有一堆石子共有N个。A B两个人轮流拿，A先拿。每次最少拿1颗，最多拿K颗，拿到最后1颗石子的人获胜。
假设A B都非常聪明，拿石子的过程中不会出现失误。给出N和K，问最后谁能赢得比赛。
例如N = 3，K = 2。无论A如何拿，B都可以拿到最后1颗石子。
Input
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)
第2 - T + 1行：每行2个数N，K。中间用空格分隔。（1 <= N,K <= 10^9)
Output
共T行，如果A获胜输出A，如果B获胜输出B。
Input示例
4
3 2
4 2
7 3
8 3
Output示例
B
A
A
B
分析：
N % (K + 1) == 0 时，先手必输。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
in.nextToken();
int T = (int) in.nval;
int[] N = new int[T], K = new int[T];
for (int i = 0; i < T; i++) {
in.nextToken();
N[i] = (int) in.nval;
in.nextToken();
K[i] = (int) in.nval;
}
for (int i = 0; i < T; i++) {
if (N[i] % (K[i] + 1) == 0) {
out.println("B");
} else {
out.println("A");
}
}
out.flush();
}
}
|
Bash游戏 V2
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1067
有一堆石子共有N个。A B两个人轮流拿，A先拿。每次只能拿1，3，4颗，拿到最后1颗石子的人获胜。
假设A B都非常聪明，拿石子的过程中不会出现失误。给出N，问最后谁能赢得比赛。
例如N = 2。A只能拿1颗，所以B可以拿到最后1颗石子。
Input
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)
第2 - T + 1行：每行1个数N。(1 <= N <= 10^9)
Output
共T行，如果A获胜输出A，如果B获胜输出B。
Input示例
3
2
3
4
Output示例
B
A
A
分析：
想不出来的话，可以通过 SG 函数打表发现规律：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| import java.util.Arrays;
public class Main {
static int MAXN = 105;
static int N = 3;
static int[] f = { 1, 3, 4 };
static boolean[] isVisit = new boolean[MAXN];
static int[] SG = new int[MAXN];
public static void main(String[] args) {
getSG(100);
}
static void getSG(int n) {
for (int i = 1; i < n; i++) {
Arrays.fill(isVisit, false);
for (int j = 0; j < N && f[j] <= i; j++) {
isVisit[SG[i - f[j]]] = true;
}
for (int j = 0;; j++) {
if (!isVisit[j]) {
SG[i] = j;
break;
}
}
System.out.println(i + " " + SG[i]);
}
}
}
|
可以发现只有 mod 7 = 0、mod 7 = 2 必败。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
in.nextToken();
int T = (int) in.nval;
int[] a = new int[T];
for (int i = 0; i < T; i++) {
in.nextToken();
a[i] = (int) in.nval;
}
for (int i = 0; i < T; i++) {
out.println(a[i] % 7 == 0 || a[i] % 7 == 2 ? "B" : "A");
}
out.flush();
}
}
|
Bash游戏 V3
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1068
有一堆石子共有N个。A B两个人轮流拿，A先拿。每次拿的数量只能是2的正整数次幂，比如(1,2,4,8,16….)，拿到最后1颗石子的人获胜。
假设A B都非常聪明，拿石子的过程中不会出现失误。给出N，问最后谁能赢得比赛。
例如N = 3。A只能拿1颗或2颗，所以B可以拿到最后1颗石子。（输入的N可能为大数）
Input
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 1000)
第2 - T + 1行：每行1个数N。(1 <= N <= 10^1000)
Output
共T行，如果A获胜输出A，如果B获胜输出B。
Input示例
3
2
3
4
Output示例
A
B
A
分析：
同样可以通过 SG 函数打表发现规律：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| import java.util.Arrays;
public class Main {
static int MAXN = 105;
static int N = 20;
static int[] f = new int[N];
static boolean[] isVisit = new boolean[MAXN];
static int[] SG = new int[MAXN];
public static void main(String[] args) throws IOException {
for (int i = 0; i < N; i++) {
f[i] = (int) Math.pow(2, i);
}
getSG(100);
}
static void getSG(int n) {
for (int i = 1; i < n; i++) {
Arrays.fill(isVisit, false);
for (int j = 0; j < N && f[j] <= i; j++) {
isVisit[SG[i - f[j]]] = true;
}
for (int j = 0;; j++) {
if (!isVisit[j]) {
SG[i] = j;
break;
}
}
System.out.println(i + " " + SG[i]);
}
}
}
|
mod 3 = 0 必败。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.math.BigInteger;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(in.readLine());
BigInteger three = BigInteger.valueOf(3);
for (int i = 0; i < T; i++) {
BigInteger N = new BigInteger(in.readLine());
out.println(N.mod(three).intValue() == 0 ? "B" : "A");
}
out.flush();
}
}
|
Bash游戏 V4
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1070
有一堆石子共有N个。A B两个人轮流拿，A先拿。每次拿的数量最少1个，最多不超过对手上一次拿的数量的2倍（A第1次拿时要求不能全拿走）。拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N，问最后谁能赢得比赛。
例如N = 3。A只能拿1颗或2颗，所以B可以拿到最后1颗石子。
Input
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 1000)
第2 - T + 1行：每行1个数N。(1 <= N <= 10^9)
Output
共T行，如果A获胜输出A，如果B获胜输出B。
Input示例
3
2
3
4
Output示例
B
B
A
分析：
当石头数为斐波那契数时，必败。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Main {
static int N = 50;
static int[] f = new int[N];
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
getFibonacci();
in.nextToken();
int T = (int) in.nval;
for (int i = 0; i < T; i++) {
in.nextToken();
int n = (int) in.nval;
if (isFibonacci(n)) {
out.println("B");
} else {
out.println("A");
}
}
out.flush();
}
static void getFibonacci() {
f[0] = f[1] = 1;
for (int i = 2; i < N; i++) {
f[i] = f[i - 1] + f[i - 2];
}
}
static boolean isFibonacci(int n) {
for (int j = 1; j < N; j++) {
if (n == f[j]) {
return true;
}
}
return false;
}
}
|
