There is one pile of n marbles, and two players take marbles in turn.
On a turn a player must take at least 1 and at most k marbles, and cannot take more than are left.
A player cannot take the same number of marbles that the opponent took on the turn just before.
The very first turn has no such restriction.
A player who has no number of marbles they can take on their turn loses.
This means losing when no marbles are left, and also when marbles are left but every number that could be taken is blocked. For example, if the opponent has just taken 1 and 1 marble is left, the player cannot take it and loses.
Both players always play a winning move whenever they have one.
k is fixed, and q values of n are given.
For each n, find every number the first player can take on the first turn and then win no matter how the opponent plays.
Print those numbers on one line from smallest to largest, separated by single spaces, or print 0 if there are none.
Input
The first line has k and q separated by one space, and each of the next q lines has one n. 1 ≤ k ≤ 10, 1 ≤ q ≤ 9,000, 1 ≤ n ≤ 9,000. All are integers
Output
One line per n: the numbers the first player can take on the first turn and win (smallest first, separated by single spaces), or 0
Example 1 · stdin
4 5
2
3
5
6
9
stdout
1 2
3
0
1 3
2 4
Example 2 · stdin
1 3
1
2
7
stdout
1
1
1
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
The number of marbles left is not enough to tell who wins. You also have to record 'which number is blocked', so the table is two-dimensional. Let win[r][f] mean 'with r marbles left and f blocked, does the player to move win', and fill it from small r upwards (dynamic programming). Taking t puts the opponent at win[r - t][t], so the player wins if any unblocked t has that value false. Look at n = 2 in the first example: taking both wins, and taking 1 also wins because the opponent cannot copy by taking 1. So the answer is 1 2. Trap one: drop the no-copying rule and it becomes the common 'leave a multiple of (k + 1)' game, which gives only 2 for n = 2 and only 1 for n = 6. Trap two: if a blocked player simply takes the blocked number instead of losing, n = 2 gives only 2, and n = 2 in the second example (k = 1) becomes 0. Trap three: if you do not stop taking more than are left, the index goes negative. In Python win[-1] reads the last row without an error and gives a wrong answer such as 3 4 for n = 3. In JS and TS you get undefined and the following [t] stops with TypeError, and Craykon also stops, saying there is no such index. Java and C# throw an exception, and in C and C++ it is undefined behaviour. Trap four: how to make the table. Python [[False] * (k + 1)] * (top + 1) and JS/TS new Array(top + 1).fill(new Array(k + 1).fill(false)) point to one and the same row many times, so changing one cell changes every row (the first example prints 1 everywhere). In Python write [[False] * (k + 1) for _ in range(top + 1)] and in JS/TS Array.from({ length: top + 1 }, () => …) to make a new row each time. Java new boolean[top + 1][k + 1], C# new bool[top + 1, k + 1], C++ vector<vector<char>>(top + 1, vector<char>(k + 1)) and a global two-dimensional array in C have separate rows from the start. Craykon NewList(top + 1, NewList(k + 1, false)) also makes a separate row each time. Trap five: solving from the top with recursion and remembering results makes the recursion thousands deep when n is in the thousands. Python passes its default limit of 1,000 and stops with RecursionError, so fill the table from the bottom. Trap six: when there is no winning first move, print 0, not an empty line.
Pythonmain.py · 26 lines
import sysdef 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()
JavaScriptmain.js · 31 lines
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"));
TypeScriptmain.ts · 31 lines
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"));
JavaMain.java · 40 lines
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); }}
C#Main.cs · 51 lines
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); }}
C++main.cpp · 44 lines
#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;}
Cmain.c · 47 lines
#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;}
Craykonmain.cray · 52 lines
첫줄 = Console.ReadNumbers();k = 첫줄[0];q = 첫줄[1];묻는수 = [];끝 = 0;for (i = 0; i < q; i++){ n = Console.ReadLine().ToNumber(); 묻는수.Add(n); 끝 = Mathf.Max(끝, n);}// 이김[r][f]: 구슬이 r개 남았고 f개는 가져갈 수 없을 때(f = 0이면 제한 없음), 지금 둘 사람이 이기는가이김 = NewList(끝 + 1, NewList(k + 1, false));for (r = 1; r <= 끝; r++){ // 가져가면 상대가 지는 자리로 가는 개수가 몇 가지인지, 한 가지뿐이면 그것이 무엇인지 가짓수 = 0; 하나뿐 = 0; for (t = 1; t <= k && t <= r; t++) { if (!이김[r - t][t]) { 가짓수 += 1; 하나뿐 = t; } } for (f = 0; f <= k; f++) { 이김[r][f] = 가짓수 >= 2 || 가짓수 == 1 && 하나뿐 != f; }}foreach (n in 묻는수){ 첫수 = []; for (t = 1; t <= k && t <= n; t++) { if (!이김[n - t][t]) { 첫수.Add(t); } } if (첫수.Count > 0) { Console.WriteLine(첫수); } else { Console.WriteLine(0); }}