B. Teams Formation

Codeforces

IDCF878B

Time2000ms

Memory256MB

Difficulty—

data structuresimplementation

English · Original

Chinese · Translation

Formal · Original

This time the Berland Team Olympiad in Informatics is held in a remote city that can only be reached by one small bus. Bus has _n_ passenger seats, seat _i_ can be occupied only by a participant from the city _a__i_. Today the bus has completed _m_ trips, each time bringing _n_ participants. The participants were then aligned in one line in the order they arrived, with people from the same bus standing in the order of their seats (i. e. if we write down the cities where the participants came from, we get the sequence _a_1, _a_2, ..., _a__n_ repeated _m_ times). After that some teams were formed, each consisting of _k_ participants form the same city standing next to each other in the line. Once formed, teams left the line. The teams were formed until there were no _k_ neighboring participants from the same city. Help the organizers determine how many participants have left in the line after that process ended. We can prove that answer doesn't depend on the order in which teams were selected. ## Input The first line contains three integers _n_, _k_ and _m_ (1 ≤ _n_ ≤ 105, 2 ≤ _k_ ≤ 109, 1 ≤ _m_ ≤ 109). The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 105), where _a__i_ is the number of city, person from which must take seat _i_ in the bus. ## Output Output the number of remaining participants in the line. [samples] ## Note In the second example, the line consists of ten participants from the same city. Nine of them will form a team. At the end, only one participant will stay in the line.

这次，贝尔兰信息学团队奥林匹克竞赛在一座偏远城市举行，该城市只能通过一辆小巴士到达。巴士共有 #cf_span[n] 个乘客座位，第 #cf_span[i] 个座位只能由来自城市 #cf_span[ai] 的参与者乘坐。今天，这辆巴士完成了 #cf_span[m] 次行程，每次运送 #cf_span[n] 名参与者。参与者们按到达顺序排成一列，同一辆巴士的参与者按座位顺序排列（即，如果我们写出参与者来自的城市序列，会得到序列 #cf_span[a1, a2, ..., an] 重复 #cf_span[m] 次）。之后，组织者开始组建队伍，每个队伍由 #cf_span[k] 名来自同一城市且在队列中相邻的参与者组成。一旦组成队伍，这些参与者就会离开队列。这个过程持续进行，直到队列中不再存在 #cf_span[k] 个相邻且来自同一城市的参与者为止。请帮助组织者确定该过程结束后，队列中剩余的参与者人数。我们可以证明，答案与队伍选取的顺序无关。第一行包含三个整数 #cf_span[n, k] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 10^5]，#cf_span[2 ≤ k ≤ 10^9]，#cf_span[1 ≤ m ≤ 10^9]）。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 10^5]），其中 #cf_span[ai] 表示必须坐在巴士第 #cf_span[i] 个座位上的参与者所属的城市编号。请输出队列中剩余的参与者人数。在第二个示例中，队列由十名来自同一城市的参与者组成，其中九人组成一个队伍，最终只剩一人留在队列中。 ## Input 第一行包含三个整数 #cf_span[n, k] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 10^5]，#cf_span[2 ≤ k ≤ 10^9]，#cf_span[1 ≤ m ≤ 10^9]）。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 10^5]），其中 #cf_span[ai] 表示必须坐在巴士第 #cf_span[i] 个座位上的参与者所属的城市编号。 ## Output 输出队列中剩余的参与者人数。 [samples] ## Note 在第二个示例中，队列由十名来自同一城市的参与者组成，其中九人组成一个队伍，最终只剩一人留在队列中。

**Parameters** * $n, k, m \in \mathbb{Z}$ satisfying $1 \le n \le 10^5$, $2 \le k \le 10^9$, $1 \le m \le 10^9$. * Sequence $A = (a_1, a_2, \dots, a_n)$ where $a_i \in \mathbb{Z} \cap [1, 10^5]$. **Definitions** 1. Let $\Sigma^*$ be the set of all finite sequences over $\mathbb{Z}$. 2. Let $\oplus$ denote the concatenation of sequences. 3. Let $S_0 \in \Sigma^*$ be constructed by concatenating $m$ copies of $A$: $$ S_0 = \underbrace{A \oplus A \oplus \dots \oplus A}_{m \text{ times}} $$ 4. Define a reduction relation $\to$ on $\Sigma^*$: For any $U, V \in \Sigma^*$ and $c \in \mathbb{Z}$, $$ U \oplus (\underbrace{c, c, \dots, c}_{k \text{ times}}) \oplus V \to U \oplus V $$ (Any contiguous subsequence of $k$ identical elements is removed). 5. Let $S_{final}$ be the normal form of $S_0$ under $\to$, such that $S_0 \to^* S_{final}$ and there exists no $S'$ where $S_{final} \to S'$. **Objective** Compute $|S_{final}|$, where $|\cdot|$ denotes the length of the sequence.

Samples

Input #1

4 2 5
1 2 3 1

Output #1

Input #2

1 9 10
1

Output #2

Input #3

3 2 10
1 2 1

Output #3

API Response (JSON)

{
  "problem": {
    "name": "B. Teams Formation",
    "description": {
      "content": "This time the Berland Team Olympiad in Informatics is held in a remote city that can only be reached by one small bus. Bus has _n_ passenger seats, seat _i_ can be occupied only by a participant from ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF878B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "This time the Berland Team Olympiad in Informatics is held in a remote city that can only be reached by one small bus. Bus has _n_ passenger seats, seat _i_ can be occupied only by a participant from ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "这次，贝尔兰信息学团队奥林匹克竞赛在一座偏远城市举行，该城市只能通过一辆小巴士到达。巴士共有 #cf_span[n] 个乘客座位，第 #cf_span[i] 个座位只能由来自城市 #cf_span[ai] 的参与者乘坐。\n\n今天，这辆巴士完成了 #cf_span[m] 次行程，每次运送 #cf_span[n] 名参与者。参与者们按到达顺序排成一列，同一辆巴士的参与者按座位顺序排列（即，如果我们写出...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Parameters**\n*   $n, k, m \\in \\mathbb{Z}$ satisfying $1 \\le n \\le 10^5$, $2 \\le k \\le 10^9$, $1 \\le m \\le 10^9$.\n*   Sequence $A = (a_1, a_2, \\dots, a_n)$ where $a_i \\in \\mathbb{Z} \\cap [1, 10^5]$.\n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments