-
Notifications
You must be signed in to change notification settings - Fork 513
/
c.go
42 lines (33 loc) · 1.83 KB
/
c.go
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
package main
import (
. "fmt"
"io"
"os"
)
/*
考虑哪些 $n$ 会导致先手必败。
如果只考虑取 $1$ 和 $2$,那么若 $n$ 是 $3$ 的倍数,先手取 $x$ 个石子,后手就可以取 $3-x$ 个石子,这样剩下的石子仍然是 $3$ 的倍数,所以先手必败;若 $n$ 不是 $3$ 的倍数,先手可以将石子个数变成 $3$ 的倍数,这样后手必败,先手必胜。
接下来考虑 $k$。上面的讨论启发我们去讨论 $k$ 与 $3$ 的关系:
- 如果 $k$ 不是 $3$ 的倍数,那么若 $n$ 是 $3$ 的倍数,先手取 $x$ 个石子,后手就可以取 $3-(x\bmod 3)$ 个石子,这样剩下的石子仍然是 $3$ 的倍数,所以先手必败;若 $n$ 不是 $3$ 的倍数,先手可以将石子个数变成 $3$ 的倍数,这样后手必败,先手必胜。因此在 $k$ 不是 $3$ 的倍数的情况下,仍然同上面一样,当 $n$ 是 $3$ 的倍数时先手必败,否则先手必胜。
- 如果 $k$ 是 $3$ 的倍数,那么显然 $n=k$ 时是先手必胜的,而 $n=k+1$ 时由于可以到达的 $k$、$k-1$ 和 $1$ 均为先手必胜,所以此时先手必败。$n=k+2$ 和 $n=k+3$ 时,由于可以到达 $k+1$,所以是先手必胜的,再往后的讨论和上面一样,直到 $n=2k+1$ 时由于可以直接到 $k+1$ 的必败态所以此时是先手必胜的,这样就形成了一个长为 $k+1$ 的循环,循环的最后一个数是必胜的,其余数同上面讨论的模 $3$ 的结果判断胜负。
*/
// github.com/EndlessCheng/codeforces-go
func run(in io.Reader, out io.Writer) {
var T, n, k int
for Fscan(in, &T); T > 0; T-- {
Fscan(in, &n, &k)
if k%3 == 0 {
n %= k + 1
if n == k {
Fprintln(out, "Alice")
continue
}
}
if n%3 > 0 {
Fprintln(out, "Alice")
} else {
Fprintln(out, "Bob")
}
}
}
func main() { run(os.Stdin, os.Stdout) }