B. Mancala

Codeforces

IDCF975B

Time1000ms

Memory256MB

Difficulty—

brute forceimplementation

English · Original

Chinese · Translation

Formal · Original

Mancala is a game famous in the Middle East. It is played on a board that consists of 14 holes. <center>![image](https://espresso.codeforces.com/920ad783d519ca86df1e488b1acd1c886d0e69e5.png)</center>Initially, each hole has $a_i$ stones. When a player makes a move, he chooses a hole which contains a **positive** number of stones. He takes all the stones inside it and then redistributes these stones one by one in the next holes in a counter-clockwise direction. Note that the counter-clockwise order means if the player takes the stones from hole $i$, he will put one stone in the $(i+1)$\-th hole, then in the $(i+2)$\-th, etc. If he puts a stone in the $14$\-th hole, the next one will be put in the first hole. After the move, the player collects all the stones from holes that contain even number of stones. The number of stones collected by player is the score, according to Resli. Resli is a famous Mancala player. He wants to know the maximum score he can obtain after one move. ## Input The only line contains 14 integers $a_1, a_2, \ldots, a_{14}$ ($0 \leq a_i \leq 10^9$) — the number of stones in each hole. It is guaranteed that for any $i$ ($1\leq i \leq 14$) $a_i$ is either zero or odd, and there is at least one stone in the board. ## Output Output one integer, the maximum possible score after one move. [samples] ## Note In the first test case the board after the move from the hole with $7$ stones will look like _1 2 2 0 0 0 0 0 0 0 1 1 1 1_. Then the player collects the even numbers and ends up with a score equal to $4$.

Mancala 是一种在中东地区广为流传的游戏。游戏在一个由 14 个洞组成的棋盘上进行。初始时，每个洞中有 $a_i$ 颗石子。当玩家进行一步操作时，他选择一个包含 *正数* 石子的洞，取出其中的所有石子，然后按逆时针方向，将这些石子逐个放入后续的洞中。注意，逆时针顺序意味着：如果玩家从第 $i$ 个洞取石子，他会将一颗石子放入第 $(i + 1)$ 个洞，接着是第 $(i + 2)$ 个洞，依此类推。如果一颗石子被放入第 14 个洞，下一颗石子将被放入第 1 个洞。操作完成后，玩家收集所有包含偶数个石子的洞中的石子。根据 Resli 的规则，玩家收集的石子总数即为得分。 Resli 是一位著名的 Mancala 玩家。他想知道，在一步操作后，他能获得的最大得分是多少。输入仅一行，包含 14 个整数 $a_1, a_2, dots.h, a_{14}$（$0 lt.eq a_i lt.eq 10^9$）—— 每个洞中的石子数量。保证对于任意 $i$（$1 lt.eq i lt.eq 14$），$a_i$ 要么为 0，要么为奇数，且棋盘上至少有一颗石子。请输出一个整数，表示一步操作后可能获得的最大得分。在第一个测试用例中，从含有 7 颗石子的洞进行操作后，棋盘状态变为 _1 2 2 0 0 0 0 0 0 0 1 1 1 1_。然后玩家收集所有偶数数量的石子，最终得分等于 4。 ## Input 输入仅一行，包含 14 个整数 $a_1, a_2, dots.h, a_{14}$（$0 lt.eq a_i lt.eq 10^9$）—— 每个洞中的石子数量。保证对于任意 $i$（$1 lt.eq i lt.eq 14$），$a_i$ 要么为 0，要么为奇数，且棋盘上至少有一颗石子。 ## Output 请输出一个整数，表示一步操作后可能获得的最大得分。 [samples] ## Note 在第一个测试用例中，从含有 7 颗石子的洞进行操作后，棋盘状态变为 _1 2 2 0 0 0 0 0 0 0 1 1 1 1_。然后玩家收集所有偶数数量的石子，最终得分等于 4。

**Definitions** Let $ A = (a_1, a_2, \dots, a_{14}) \in \mathbb{Z}_{\geq 0}^{14} $ be the initial stone configuration, where: - $ a_i \equiv 0 \pmod{2} $ or $ a_i \equiv 1 \pmod{2} $ for all $ i \in \{1, \dots, 14\} $, - $ a_i = 0 $ or $ a_i $ is odd for all $ i $, - $ \sum_{i=1}^{14} a_i \geq 1 $. Let $ S(i) $ denote the resulting configuration after performing a move from hole $ i $ where $ a_i > 0 $. **Move Operation** For a move from hole $ i $ (with $ a_i = s > 0 $): - Set $ a_i' = 0 $. - Distribute $ s $ stones one by one into holes $ i+1, i+2, \dots $ (modulo 14, wrapping from 14 to 1). - For each $ j \in \{1, \dots, 14\} \setminus \{i\} $: $$ a_j' = a_j + \left\lfloor \frac{s + (j - i - 1) \bmod 14}{14} \right\rfloor $$ More precisely: Let $ d_j = ((j - i - 1) \bmod 14) + 1 $, then $$ a_j' = a_j + \begin{cases} 1 & \text{if } 1 \leq d_j \leq s \\ 0 & \text{otherwise} \end{cases} $$ **Score Function** After move from hole $ i $, the score is: $$ \text{Score}(i) = \sum_{\substack{j=1 \\ a_j' \text{ even}}}^{14} a_j' $$ **Objective** Compute: $$ \max_{\substack{i \in \{1, \dots, 14\} \\ a_i > 0}} \text{Score}(i) $$

Samples

Input #1

0 1 1 0 0 0 0 0 0 7 0 0 0 0

Output #1

Input #2

5 1 1 1 1 0 0 0 0 0 0 0 0 0

Output #2

API Response (JSON)

{
  "problem": {
    "name": "B. Mancala",
    "description": {
      "content": "Mancala is a game famous in the Middle East. It is played on a board that consists of 14 holes. <center>![image](https://espresso.codeforces.com/920ad783d519ca86df1e488b1acd1c886d0e69e5.png)</center>",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF975B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mancala is a game famous in the Middle East. It is played on a board that consists of 14 holes.\n\n<center>![image](https://espresso.codeforces.com/920ad783d519ca86df1e488b1acd1c886d0e69e5.png)</center>...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Mancala 是一种在中东地区广为流传的游戏。游戏在一个由 14 个洞组成的棋盘上进行。\n\n初始时，每个洞中有 $a_i$ 颗石子。当玩家进行一步操作时，他选择一个包含 *正数* 石子的洞，取出其中的所有石子，然后按逆时针方向，将这些石子逐个放入后续的洞中。\n\n注意，逆时针顺序意味着：如果玩家从第 $i$ 个洞取石子，他会将一颗石子放入第 $(i + 1)$ 个洞，接着是第 $(i + 2)$ ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ A = (a_1, a_2, \\dots, a_{14}) \\in \\mathbb{Z}_{\\geq 0}^{14} $ be the initial stone configuration, where:  \n- $ a_i \\equiv 0 \\pmod{2} $ or $ a_i \\equiv 1 \\pmod{2} $ for all $ i \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments