E. Competitive Seagulls

Codeforces

IDCF10135E

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

There are two seagulls playing a very peculiar game. First they line up N unit squares in a line, all originally colored white. Let L be the length of the longest continuous sub-segment of white unit squares. Let P be any prime that satisfies the condition that . The player can choose any P if it satisfies the conditions but if there is no value of P that does, then P is set to 1. The current player then proceeds to choose any continuous sub-segment of white unit squares of length P and paint them black. The player who can’t make a move loses. If both players play optimally and the first player starts, which player is going to win the game? The first line of input is T – the number of test cases. Each test case contains a line with a single integer N (1 ≤ N ≤ 107). For each test case, output on a single line "first" (without quotes) if the first player would win the game, or "second" if the second would win. ## Input The first line of input is T – the number of test cases.Each test case contains a line with a single integer N (1 ≤ N ≤ 107). ## Output For each test case, output on a single line "first" (without quotes) if the first player would win the game, or "second" if the second would win. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case, let $ N \in \mathbb{Z} $ denote the number of initially white unit squares in a line. Let $ L $ be the length of the longest contiguous segment of white squares. Let $ P $ be the largest prime $ \leq L $, or $ 1 $ if no such prime exists (i.e., if $ L = 0 $ or $ L = 1 $). A move consists of selecting a contiguous white segment of length exactly $ P $ and coloring it black. The game is played by two players alternately, starting with the first player. A player unable to move loses. **Constraints** $ 1 \leq T \leq 10^4 $, $ 1 \leq N \leq 10^7 $ **Objective** Determine the winner under optimal play: output "first" if the first player wins, "second" otherwise. This is equivalent to computing the Grundy number (nimber) $ g(N) $ of the game state with $ N $ contiguous white squares, where a move reduces the segment by removing a contiguous block of length $ p $, with $ p $ being the largest prime $ \leq $ current segment length (or 1 if none). The game is equivalent to an impartial game with state $ N $, and transitions: $$ g(N) = \mathrm{mex} \left\{ g(N - p) \mid p \text{ is the largest prime } \leq N \right\} $$ with $ g(0) = 0 $. The first player wins iff $ g(N) \neq 0 $.

API Response (JSON)

{
  "problem": {
    "name": "E. Competitive Seagulls",
    "description": {
      "content": "There are two seagulls playing a very peculiar game. First they line up N unit squares in a line, all originally colored white. Let L be the length of the longest continuous sub-segment of white unit",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10135E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are two seagulls playing a very peculiar game. First they line up N unit squares in a line, all originally colored white.\n\nLet L be the length of the longest continuous sub-segment of white unit...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ N \\in \\mathbb{Z} $ denote the number of initially white unit squares in a line.  \n\nLet $ L $ be the ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments