有一堆弹珠，共 n 颗，两个人轮流拿弹珠。
每一轮必须拿 1 颗以上、k 颗以下，并且不能拿得比剩下的多。
不能拿与对方上一轮所拿数量相同的数量。
最开始的一轮没有这个限制。
轮到自己时没有任何数量可拿的人输。
弹珠一颗不剩时当然输，即使还有弹珠，如果能拿的数量全都被堵住，也算输。
例如对方刚拿了 1 颗，还剩 1 颗，那就拿不了，所以输。
两个人只要有能赢的拿法，就一定那样拿。
k 是固定的一个数，给出 q 个 n。
对每个 n，求出先手在第一轮拿了之后，无论对方怎么拿都能赢的所有数量。
把这些数量从小到大用一个空格隔开输出在一行；如果一个也没有，输出 0。
4 5 2 3 5 6 9
1 2 3 0 1 3 2 4
1 3 1 2 7
1 1 1
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
只看剩下的弹珠数是不知道能不能赢的。
还要一起记下“哪个数量被堵住”，所以表是二维的。
设 win[r][f] 为“剩 r 颗、f 颗被堵住时，现在拿的人能不能赢”，从小的 r 开始填（动态规划）。
拿 t 颗后对方站在 win[r - t][t]，所以只要没被堵住的 t 中有一个使这个值为假，就能赢。
看第一个样例的 n = 2：2 颗全拿能赢，拿 1 颗也能赢，因为对方不能照着拿 1 颗。
所以是 1 2。
陷阱一：去掉不能照着拿的规则，就成了常见的“留下 (k + 1) 的倍数”游戏，n = 2 只得到 2，n = 6 只得到 1。
陷阱二：如果被堵住的人不算输，而是照样拿被堵住的数量，n = 2 只得到 2，第二个样例（k = 1）的 n = 2 会变成 0。
陷阱三：如果不拦住拿得比剩下的多，下标会变成负数。
Python 的 win[-1] 不报错地读到最后一行，对 n = 3 给出 3 4 这样的错误答案。
JS、TS 得到 undefined，接着的 [t] 会因 TypeError 停下，Craykon 也会说没有这个下标而停下。
Java、C# 抛出异常，C、C++ 则是未定义行为。
陷阱四：建表的方法。
Python 的 [[False] * (k + 1)] * (top + 1) 和 JS、TS 的 new Array(top + 1).fill(new Array(k + 1).fill(false)) 是多次指向同一行，改一个格子，所有行都会变（第一个样例会全部输出 1）。
Python 要写 [[False] * (k + 1) for _ in range(top + 1)]，JS、TS 要写 Array.from({ length: top + 1 }, () => …)，每行新建一个。
Java new boolean[top + 1][k + 1]、C# new bool[top + 1, k + 1]、C++ vector<vector<char>>(top + 1, vector<char>(k + 1)) 和 C 的全局二维数组从一开始各行就是分开的。
Craykon 的 新列表(末 + 1, 新列表(k + 1, 假)) 也会为每行单独新建。
陷阱五：从上往下用递归并记住结果的做法，n 有几千时递归也有几千层。
Python 会超过默认上限 1,000，因 RecursionError 停下，所以要从下往上填表。
陷阱六：没有能赢的第一手时，要写 0，而不是空行。
import sys def main(): data = sys.stdin.read().split() k, q = int(data[0]), int(data[1]) asks = [int(x) for x in data[2:2 + q]] top = max(asks) # win[r][f]: 구슬이 r개 남았고 f개는 가져갈 수 없을 때(f = 0이면 제한 없음), 지금 둘 사람이 이기는가 win = [[False] * (k + 1) for _ in range(top + 1)] for r in range(1, top + 1): # good: 가져가면 상대가 지는 자리로 가는 개수들(제한은 아직 따지지 않음) good = [t for t in range(1, min(k, r) + 1) if not win[r - t][t]] row = win[r] for f in range(k + 1): row[f] = len(good) >= 2 or (len(good) == 1 and good[0] != f) out = [] for n in asks: first = [t for t in range(1, min(k, n) + 1) if not win[n - t][t]] out.append(" ".join(map(str, first)) if first else "0") print("\n".join(out)) main()const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const k = data[0], q = data[1];const asks = data.slice(2, 2 + q);const top = Math.max(...asks); // win[r][f]: 구슬이 r개 남았고 f개는 가져갈 수 없을 때(f = 0이면 제한 없음), 지금 둘 사람이 이기는가// fill(배열)은 같은 배열 하나를 모든 줄에 넣으므로, 줄마다 새로 만든다const win = Array.from({ length: top + 1 }, () => new Array(k + 1).fill(false));for (let r = 1; r <= top; r++) { // 가져가면 상대가 지는 자리로 가는 개수가 몇 가지인지, 한 가지뿐이면 그것이 무엇인지 let count = 0, only = 0; for (let t = 1; t <= k && t <= r; t++) { if (!win[r - t][t]) { count++; only = t; } } for (let f = 0; f <= k; f++) { win[r][f] = count >= 2 || (count === 1 && only !== f); }} const out = [];for (const n of asks) { const first = []; for (let t = 1; t <= k && t <= n; t++) { if (!win[n - t][t]) first.push(t); } out.push(first.length > 0 ? first.join(" ") : "0");}console.log(out.join("\n"));const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const k = data[0], q = data[1];const asks = data.slice(2, 2 + q);const top = Math.max(...asks); // win[r][f]: 구슬이 r개 남았고 f개는 가져갈 수 없을 때(f = 0이면 제한 없음), 지금 둘 사람이 이기는가// fill(배열)은 같은 배열 하나를 모든 줄에 넣으므로, 줄마다 새로 만든다const win: boolean[][] = Array.from({ length: top + 1 }, () => new Array(k + 1).fill(false));for (let r = 1; r <= top; r++) { // 가져가면 상대가 지는 자리로 가는 개수가 몇 가지인지, 한 가지뿐이면 그것이 무엇인지 let count = 0, only = 0; for (let t = 1; t <= k && t <= r; t++) { if (!win[r - t][t]) { count++; only = t; } } for (let f = 0; f <= k; f++) { win[r][f] = count >= 2 || (count === 1 && only !== f); }} const out: string[] = [];for (const n of asks) { const first: number[] = []; for (let t = 1; t <= k && t <= n; t++) { if (!win[n - t][t]) first.push(t); } out.push(first.length > 0 ? first.join(" ") : "0");}console.log(out.join("\n"));import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int k = in.nextInt(), q = in.nextInt(); int[] asks = new int[q]; int top = 0; for (int i = 0; i < q; i++) { asks[i] = in.nextInt(); top = Math.max(top, asks[i]); } // win[r][f]: 구슬이 r개 남았고 f개는 가져갈 수 없을 때(f = 0이면 제한 없음), 지금 둘 사람이 이기는가 boolean[][] win = new boolean[top + 1][k + 1]; // 모두 false로 시작한다 for (int r = 1; r <= top; r++) { // 가져가면 상대가 지는 자리로 가는 개수가 몇 가지인지, 한 가지뿐이면 그것이 무엇인지 int count = 0, only = 0; for (int t = 1; t <= k && t <= r; t++) { if (!win[r - t][t]) { count++; only = t; } } for (int f = 0; f <= k; f++) { win[r][f] = count >= 2 || (count == 1 && only != f); } } StringBuilder out = new StringBuilder(); for (int n : asks) { StringJoiner first = new StringJoiner(" "); for (int t = 1; t <= k && t <= n; t++) { if (!win[n - t][t]) first.add(String.valueOf(t)); } out.append(first.length() > 0 ? first.toString() : "0").append('\n'); } System.out.print(out); }}using System;using System.Collections.Generic;using System.Text; class Program{ static void Main() { string[] data = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int k = int.Parse(data[0]), q = int.Parse(data[1]); var asks = new int[q]; int top = 0; for (int i = 0; i < q; i++) { asks[i] = int.Parse(data[2 + i]); top = Math.Max(top, asks[i]); } // win[r, f]: 구슬이 r개 남았고 f개는 가져갈 수 없을 때(f = 0이면 제한 없음), 지금 둘 사람이 이기는가 var win = new bool[top + 1, k + 1]; // 네모난 2차원 배열, 모두 false로 시작한다 for (int r = 1; r <= top; r++) { // 가져가면 상대가 지는 자리로 가는 개수가 몇 가지인지, 한 가지뿐이면 그것이 무엇인지 int count = 0, only = 0; for (int t = 1; t <= k && t <= r; t++) { if (!win[r - t, t]) { count++; only = t; } } for (int f = 0; f <= k; f++) { win[r, f] = count >= 2 || (count == 1 && only != f); } } var output = new StringBuilder(); foreach (int n in asks) { var first = new List<int>(); for (int t = 1; t <= k && t <= n; t++) { if (!win[n - t, t]) first.Add(t); } output.Append(first.Count > 0 ? string.Join(" ", first) : "0").Append('\n'); } Console.Write(output); }}#include <algorithm>#include <iostream>#include <vector>using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int k, q; cin >> k >> q; vector<int> asks(q); for (int &n : asks) cin >> n; int top = *max_element(asks.begin(), asks.end()); // win[r][f]: 구슬이 r개 남았고 f개는 가져갈 수 없을 때(f = 0이면 제한 없음), 지금 둘 사람이 이기는가 vector<vector<char>> win(top + 1, vector<char>(k + 1, 0)); // 줄마다 따로 복사된다 for (int r = 1; r <= top; r++) { // 가져가면 상대가 지는 자리로 가는 개수가 몇 가지인지, 한 가지뿐이면 그것이 무엇인지 int count = 0, only = 0; for (int t = 1; t <= k && t <= r; t++) { if (!win[r - t][t]) { count++; only = t; } } for (int f = 0; f <= k; f++) { win[r][f] = count >= 2 || (count == 1 && only != f); } } for (int n : asks) { bool printed = false; for (int t = 1; t <= k && t <= n; t++) { if (!win[n - t][t]) { if (printed) cout << ' '; cout << t; printed = true; } } if (!printed) cout << 0; cout << '\n'; } return 0;}#include <stdio.h>#include <stdlib.h> #define MAX_N 9000#define MAX_K 10 /* win[r][f]: 구슬이 r개 남았고 f개는 가져갈 수 없을 때(f = 0이면 제한 없음), 지금 둘 사람이 이기는가 */static char win[MAX_N + 1][MAX_K + 1]; /* 전역 배열은 모두 0으로 시작한다 */ int main(void) { int k, q; if (scanf("%d %d", &k, &q) != 2) return 1; int *asks = malloc(sizeof(int) * q); int top = 0; for (int i = 0; i < q; i++) { scanf("%d", &asks[i]); if (asks[i] > top) top = asks[i]; } for (int r = 1; r <= top; r++) { /* 가져가면 상대가 지는 자리로 가는 개수가 몇 가지인지, 한 가지뿐이면 그것이 무엇인지 */ int count = 0, only = 0; for (int t = 1; t <= k && t <= r; t++) { if (!win[r - t][t]) { count++; only = t; } } for (int f = 0; f <= k; f++) { win[r][f] = count >= 2 || (count == 1 && only != f); } } for (int i = 0; i < q; i++) { int n = asks[i], printed = 0; for (int t = 1; t <= k && t <= n; t++) { if (!win[n - t][t]) { printf(printed ? " %d" : "%d", t); printed = 1; } } if (!printed) printf("0"); printf("\n"); } free(asks); return 0;}첫줄 = 控制台.读数字();k = 첫줄[0];q = 첫줄[1];묻는수 = [];끝 = 0;循环 (i = 0; i < q; i++){ n = 控制台.读行().转数字(); 묻는수.添加(n); 끝 = 数学.较大值(끝, n);} // 이김[r][f]: 구슬이 r개 남았고 f개는 가져갈 수 없을 때(f = 0이면 제한 없음), 지금 둘 사람이 이기는가이김 = 新列表(끝 + 1, 新列表(k + 1, 假));循环 (r = 1; r <= 끝; r++){ // 가져가면 상대가 지는 자리로 가는 개수가 몇 가지인지, 한 가지뿐이면 그것이 무엇인지 가짓수 = 0; 하나뿐 = 0; 循环 (t = 1; t <= k && t <= r; t++) { 如果 (!이김[r - t][t]) { 가짓수 += 1; 하나뿐 = t; } } 循环 (f = 0; f <= k; f++) { 이김[r][f] = 가짓수 >= 2 || 가짓수 == 1 && 하나뿐 != f; }} 遍历 (n 在 묻는수){ 첫수 = []; 循环 (t = 1; t <= k && t <= n; t++) { 如果 (!이김[n - t][t]) { 첫수.添加(t); } } 如果 (첫수.数量 > 0) { 控制台.输出(첫수); } 否则 { 控制台.输出(0); }}