G. The jar of divisors

Codeforces

IDCF10095G

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Alice and Bob play the following game. They choose a number N to play with. The rules are as follows: - They write each number from 1 to N on a paper and put all these papers in a jar. - Alice plays first, and the two players alternate. - In his/her turn, a player can select any available number M and remove its divisors including M. - The person who cannot make a move in his/her turn wins the game. Assuming both players play optimally, you are asked the following question: who wins the game? The first line contains the number of test cases T (1 ≤ T ≤ 20). Each of the next T lines contains an integer (1 ≤ N ≤ 1,000,000,000). Output T lines, one for each test case, containing Alice if Alice wins the game, or Bob otherwise. ## Input The first line contains the number of test cases T (1 ≤ T ≤ 20). Each of the next T lines contains an integer (1 ≤ N ≤ 1,000,000,000). ## Output Output T lines, one for each test case, containing Alice if Alice wins the game, or Bob otherwise. [samples]

**Definitions** Let $ M, N \in \mathbb{Z} $ denote the dimensions of the grid, with $ 5 \leq M, N \leq 1000 $. Let $ Q \in \mathbb{Z} $ denote the number of moves, with $ 1 \leq Q \leq 10^5 $. Let $ G \in \mathbb{Z}^{M \times N} $ be the initial grid, where $ G_{i,j} $ is the value at row $ i $, column $ j $. Let $ \mathcal{M} = \{ (y_1^{(k)}, x_1^{(k)}, y_2^{(k)}, x_2^{(k)}, A^{(k)}) \mid k \in \{1, \dots, Q\} \} $ be the set of moves, where for each move $ k $: - $ (y_1^{(k)}, x_1^{(k)}) $ is the top-left corner, - $ (y_2^{(k)}, x_2^{(k)}) $ is the bottom-right corner, - $ A^{(k)} \in \mathbb{Z} $, $ |A^{(k)}| \leq 100 $, is the value added to all cells in the rectangle. **Constraints** 1. $ 1 \leq Q \leq 10^5 $ 2. $ 5 \leq M, N \leq 1000 $ 3. For each move $ k $: - $ 1 \leq y_1^{(k)} \leq y_2^{(k)} \leq M $ - $ 1 \leq x_1^{(k)} \leq x_2^{(k)} \leq N $ - $ -100 \leq A^{(k)} \leq 100 $ 4. For all $ i \in \{1, \dots, M\}, j \in \{1, \dots, N\} $: $ |G_{i,j}| \leq 100 $ **Objective** Compute the final grid $ G' \in \mathbb{Z}^{M \times N} $, where: $$ G'_{i,j} = G_{i,j} + \sum_{\substack{k=1 \\ (y_1^{(k)} \leq i \leq y_2^{(k)}) \land (x_1^{(k)} \leq j \leq x_2^{(k)})}}^{Q} A^{(k)} $$ Output $ G' $ as an $ M \times N $ matrix.

API Response (JSON)

{
  "problem": {
    "name": "G. The jar of divisors",
    "description": {
      "content": "Alice and Bob play the following game. They choose a number N to play with. The rules are as follows: - They write each number from 1 to N on a paper and put all these papers in a jar. - Alice plays",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10095G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alice and Bob play the following game. They choose a number N to play with. The rules are as follows:\n\n- They write each number from 1 to N on a paper and put all these papers in a jar.\n\n- Alice plays...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ M, N \\in \\mathbb{Z} $ denote the dimensions of the grid, with $ 5 \\leq M, N \\leq 1000 $.  \nLet $ Q \\in \\mathbb{Z} $ denote the number of moves, with $ 1 \\leq Q \\leq 10^5 $.  \nL...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments