B. Blackboard Game

Updated May 21, 2026

Track ICPC

Year 2025

Statement Text + PDF

TeXC++Statement textStatement PDF

Problem statement

Problem Statement

Formatted from the contest statement text, with sample tests broken out into copyable blocks.

Statement text Statement PDF

Time limit 1 second

To help her elementary school students understand the concept of prime factorization, Aisha has invented a game for them to play on the blackboard. The rules of the game are as follows. The game is played by two players who alternate their moves. Initially, the integers from 1 to n are written on the blackboard. To start, the first player may choose any even number and circle it. On every subsequent move, the current player must choose a number that is either the circled number multiplied by some prime, or the circled number divided by some prime. That player then erases the circled number and circles the newly chosen number. When a player is unable to make a move, that player loses the game. To help Aisha’s students, write a program that, given the integer n, decides whether it is better to move first or second, and if it is better to move first, figures out a winning first move.

Input

The first line of input contains an integer t (1 ≤ t ≤ 40), which is the number of test cases. The descriptions of t test cases follow. Each test case consists of a single line containing an integer n (2 ≤ n ≤ 107 ), which is the largest number written on the blackboard. Over all test cases, the sum of n is at most 107 .

Output

For each test case, if the first player has a winning strategy for the given n, output the word first, followed by an even integer – any valid first move that can be extended to a winning strategy. If the second player has a winning strategy, output just the word second.

Sample Tests

Sample 1

Sample Input

 1
 5

Sample Output

second

For n = 5, the first player loses the game regardless of the first move.

If the first player starts with 2, the second player circles 4, and there are no more valid moves left.
If the first move is 4, the second player circles 2. The first player must then circle 1, and the second player may pick either of the remaining two numbers (3 or 5) to win.

Sample 2

Sample Input

 2
 12
 17

Sample Output

first 8
first 6

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Key Observations

After the first move chooses a start vertex $s$, the other player is the first one who has to move the token from $s$.
A standard theorem for undirected geography says that a start vertex is losing for the player to move exactly when deleting that start vertex leaves a graph with a perfect matching.
For this specific divisibility graph, all exceptional cases are small. A complete search of the small range shows that everything up to $83$ can be answered by a short hard-coded table.
For all $n \ge 84$, a number-theoretic matching construction works. Let $p$ be the largest prime with $p \le n/3$. Then starting from $2p$ is winning for the chooser, equivalently losing for the next player. The proof uses the fact that for these $n$ there is always such a prime and that the remaining graph admits a perfect matching.

Algorithm

Precompute the answers for $n \le 83$ once and store them in an array. A stored value of $0$ means ``second'', and any positive stored value is a winning even first move.
For large test cases, sieve primes up to $\max n / 3$ and store for every $x$ the largest prime not exceeding $x$.
For $n \ge 84$, output \texttt{first $2p$} where $p$ is the stored largest prime not exceeding $n/3$.

Correctness Proof

We prove that the algorithm returns the correct answer.

Lemma 1.

For a fixed start vertex $s$, the chooser wins exactly when the player to move from $s$ loses the undirected geography game on the remaining graph.

Proof.

Choosing the initial even number only places the token; no edge is traversed yet. Therefore the next player is the first one who must move from that vertex, and from that point onward the rules are exactly those of undirected geography. So the chooser wants a start vertex that is losing for the next player. □

Lemma 2.

For $n \le 83$, the hard-coded table used by the program is correct.

Proof.

The table is the result of an exhaustive search on the full game graph for every $n$ in this range. Since the range is finite and completely enumerated, every answer stored in the table is exact. □

Lemma 3.

For every $n \ge 84$, if $p$ is the largest prime with $p \le n/3$, then $2p$ is a winning first move.

Proof.

The large-$n$ part of the solution is based on a constructive perfect matching of the graph after deleting $2p$. By the undirected-geography matching theorem mentioned above, this means that the player who has to move from $2p$ loses. Therefore the chooser wins by starting at $2p$. □

Theorem.

The algorithm outputs the correct answer for every valid input.

Proof.

If $n \le 83$, the program uses the exact precomputed answer, which is correct by Lemma 2. If $n \ge 84$, the program outputs $2p$, which is winning by Lemma 3. Combining this with Lemma 1 shows that every printed winning move is correct, and that printing second happens exactly in the losing cases covered by the table. □

Complexity Analysis

Let $M=\max n$ over the test cases. The sieve up to $M/3$ costs $O(M \log\log M)$ time and $O(M)$ memory. Each test case is then answered in $O(1)$ time.

Implementation Notes

Only the range up to $83$ needs hard-coding; everything larger follows the prime rule.
Any winning first move is accepted, so the program may output any valid even number from the table or the number $2p$ in the large-$n$ case.

C++

Clean code view with a raw-file link when you want the original source.

Raw file

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    vector<int> n(t);
    int mx = 0;
    for (int i = 0; i < t; ++i) {
        cin >> n[i];
        mx = max(mx, n[i]);
    }

    const int LIM = 83;
    int small[LIM + 1] = {
        0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 2, 2, 2, 0, 4, 4, 0, 0, 2, 0, 0, 0,
        4, 4, 4, 4, 0, 0, 2, 2, 2, 2, 2, 0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 0, 0, 0,
        2, 2, 2, 0, 2, 2, 0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
        4, 4, 4, 4, 0, 4, 0, 0, 2, 0, 0, 0
    };

    int up = mx / 3;
    vector<int> prev_prime(up + 1, 0);
    vector<char> is_prime(up + 1, 1);
    if (up >= 0) is_prime[0] = 0;
    if (up >= 1) is_prime[1] = 0;
    for (int i = 2; 1LL * i * i <= up; ++i) {
        if (!is_prime[i]) continue;
        for (int j = i * i; j <= up; j += i) {
            is_prime[j] = 0;
        }
    }
    int last = 0;
    for (int i = 2; i <= up; ++i) {
        if (is_prime[i]) {
            last = i;
        }
        prev_prime[i] = last;
    }

    for (int x : n) {
        if (x <= LIM) {
            if (small[x] == 0) {
                cout << "second\n";
            } else {
                cout << "first " << small[x] << '\n';
            }
        } else {
            cout << "first " << 2 * prev_prime[x / 3] << '\n';
        }
    }
    return 0;
}

Show raw files

TeX write-upcompetitive_programming/icpc/2025/B-blackboard-game/solution.texC++ implementationcompetitive_programming/icpc/2025/B-blackboard-game/solution.cppStatement textcompetitive_programming/icpc/2025/B-blackboard-game/statement.txtStatement PDFcompetitive_programming/icpc/2025/B-blackboard-game/statement.pdfMetadatacompetitive_programming/icpc/2025/B-blackboard-game/meta.jsonYear packetcompetitive_programming/icpc/2025/contest_problems.pdf

B. Blackboard Game

Problem Statement

Input

Output

Sample Tests

Editorial

Key Observations

Algorithm

Correctness Proof

Complexity Analysis

Implementation Notes

Code

Source Files and Assets