A. Convert to Ones

Codeforces

IDCF997A

Time1000ms

Memory256MB

Difficulty—

brute forcegreedyimplementationmath

English · Original

Chinese · Translation

Formal · Original

You've got a string $a_1, a_2, \dots, a_n$, consisting of zeros and ones. Let's call a sequence of consecutive elements $a_i, a_{i + 1}, \ldots, a_j$ ($1\leq i\leq j\leq n$) a _substring_ of string $a$. You can apply the following operations any number of times: * Choose some substring of string $a$ (for example, you can choose entire string) and reverse it, paying $x$ coins for it (for example, «_0101101_» $\to$ «_0111001_»); * Choose some substring of string $a$ (for example, you can choose entire string or just one symbol) and replace each symbol to the opposite one (zeros are replaced by ones, and ones — by zeros), paying $y$ coins for it (for example, «_0101101_» $\to$ «_0110001_»). You can apply these operations in any order. It is allowed to apply the operations multiple times to the same substring. What is the minimum number of coins you need to spend to get a string consisting only of ones? ## Input The first line of input contains integers $n$, $x$ and $y$ ($1 \leq n \leq 300\,000, 0 \leq x, y \leq 10^9$) — length of the string, cost of the first operation (substring reverse) and cost of the second operation (inverting all elements of substring). The second line contains the string $a$ of length $n$, consisting of zeros and ones. ## Output Print a single integer — the minimum total cost of operations you need to spend to get a string consisting only of ones. Print $0$, if you do not need to perform any operations. [samples] ## Note In the first sample, at first you need to reverse substring $[1 \dots 2]$, and then you need to invert substring $[2 \dots 5]$. Then the string was changed as follows: «_01000_» $\to$ «_10000_» $\to$ «_11111_». The total cost of operations is $1 + 10 = 11$. In the second sample, at first you need to invert substring $[1 \dots 1]$, and then you need to invert substring $[3 \dots 5]$. Then the string was changed as follows: «_01000_» $\to$ «_11000_» $\to$ «_11111_». The overall cost is $1 + 1 = 2$. In the third example, string already consists only of ones, so the answer is $0$.

你有一个由 0 和 1 组成的字符串 $a_1, a_2, dots.h, a_n$。我们称连续元素序列 $a_i, a_(i + 1), dots.h, a_j$（$1 lt.eq i lt.eq j lt.eq n$）为字符串 $a$ 的一个 _子串_。你可以任意次数地应用以下操作：你可以按任意顺序应用这些操作，允许对同一个子串多次应用操作。求获得一个仅由 1 组成的字符串所需的最少硬币数。输入的第一行包含整数 $n$, $x$ 和 $y$（$1 lt.eq n lt.eq 300 thin 000$, $0 lt.eq x, y lt.eq 10^9$）——字符串长度、第一种操作（子串反转）的代价和第二种操作（子串内所有元素取反）的代价。第二行包含长度为 $n$ 的字符串 $a$，由 0 和 1 组成。输出一个整数——为获得仅由 1 组成的字符串所需花费的最小总代价。如果无需执行任何操作，请输出 $0$。在第一个样例中，首先你需要反转子串 $[ 1 dots.h 2 ]$，然后你需要对子串 $[ 2 dots.h 5 ]$ 取反。字符串变化如下： «_01000_» $arrow.r$ «_10000_» $arrow.r$ «_11111_»。操作总代价为 $1 + 10 = 11$。在第二个样例中，首先你需要对子串 $[ 1 dots.h 1 ]$ 取反，然后你需要对子串 $[ 3 dots.h 5 ]$ 取反。字符串变化如下： «_01000_» $arrow.r$ «_11000_» $arrow.r$ «_11111_»。总代价为 $1 + 1 = 2$。在第三个样例中，字符串已经仅由 1 组成，因此答案为 $0$。 ## Input 输入的第一行包含整数 $n$, $x$ 和 $y$（$1 lt.eq n lt.eq 300 thin 000$, $0 lt.eq x, y lt.eq 10^9$）——字符串长度、第一种操作（子串反转）的代价和第二种操作（子串内所有元素取反）的代价。第二行包含长度为 $n$ 的字符串 $a$，由 0 和 1 组成。 ## Output 输出一个整数——为获得仅由 1 组成的字符串所需花费的最小总代价。如果无需执行任何操作，请输出 $0$。 [samples] ## Note 在第一个样例中，首先你需要反转子串 $[ 1 dots.h 2 ]$，然后你需要对子串 $[ 2 dots.h 5 ]$ 取反。字符串变化如下：«_01000_» $arrow.r$ «_10000_» $arrow.r$ «_11111_»。操作总代价为 $1 + 10 = 11$。在第二个样例中，首先你需要对子串 $[ 1 dots.h 1 ]$ 取反，然后你需要对子串 $[ 3 dots.h 5 ]$ 取反。字符串变化如下：«_01000_» $arrow.r$ «_11000_» $arrow.r$ «_11111_»。总代价为 $1 + 1 = 2$。在第三个样例中，字符串已经仅由 1 组成，因此答案为 $0$。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the length of the binary string. Let $ x, y \in \mathbb{Z}_{\geq 0} $ be the costs of the reverse and invert operations, respectively. Let $ a = (a_1, a_2, \dots, a_n) \in \{0,1\}^n $ be the input binary string. Let a *substring* be any contiguous subsequence $ a_i, a_{i+1}, \dots, a_j $ with $ 1 \leq i \leq j \leq n $. Two operations are permitted: 1. **Reverse**: Choose a substring and reverse its order. Cost: $ x $. 2. **Invert**: Choose a substring and flip all bits (0 → 1, 1 → 0). Cost: $ y $. **Constraints** 1. $ 1 \leq n \leq 300{,}000 $ 2. $ 0 \leq x, y \leq 10^9 $ 3. $ a_i \in \{0,1\} $ for all $ i \in \{1, \dots, n\} $ **Objective** Find the minimum total cost to transform $ a $ into the all-ones string $ (1,1,\dots,1) $ using any sequence of reverse and invert operations (applied any number of times to any substrings). **Key Insight** Since reversing does not change the multiset of bits, and only invert operations can change 0s to 1s, the problem reduces to covering all 0-blocks with invert operations. Reverse operations can be used to merge adjacent 0-blocks, potentially reducing the number of invert operations needed. Let $ k $ be the number of maximal contiguous blocks of zeros in $ a $. - If $ k = 0 $, output $ 0 $. - Otherwise, the minimal cost is: $$ \min\left( k \cdot y,\ (k - 1) \cdot x + y \right) $$ because: - Option 1: Invert each zero-block individually: cost $ k \cdot y $. - Option 2: Use $ k-1 $ reverse operations to merge all zero-blocks into one, then invert once: cost $ (k-1) \cdot x + y $. *(Note: Reverse operations can only merge adjacent zero-blocks if they are separated by exactly one 1-block — but optimally, any sequence of reverses can be used to consolidate all zero-blocks into one contiguous block, as the string can be rearranged arbitrarily via reverses.)* Thus, the answer is: $$ \begin{cases} 0 & \text{if } k = 0 \\ \min(k \cdot y,\ (k - 1) \cdot x + y) & \text{if } k \geq 1 \end{cases} $$

Samples

Input #1

5 1 10
01000

Output #1

Input #2

5 10 1
01000

Output #2

Input #3

7 2 3
1111111

Output #3

API Response (JSON)

{
  "problem": {
    "name": "A. Convert to Ones",
    "description": {
      "content": "You've got a string $a_1, a_2, \\dots, a_n$, consisting of zeros and ones. Let's call a sequence of consecutive elements $a_i, a_{i + 1}, \\ldots, a_j$ ($1\\leq i\\leq j\\leq n$) a _substring_ of string $",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF997A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You've got a string $a_1, a_2, \\dots, a_n$, consisting of zeros and ones.\n\nLet's call a sequence of consecutive elements $a_i, a_{i + 1}, \\ldots, a_j$ ($1\\leq i\\leq j\\leq n$) a _substring_ of string $...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你有一个由 0 和 1 组成的字符串 $a_1, a_2, dots.h, a_n$。\n\n我们称连续元素序列 $a_i, a_(i  +  1), dots.h,  a_j$（$1 lt.eq  i lt.eq  j lt.eq  n$）为字符串 $a$ 的一个 _子串_。\n\n你可以任意次数地应用以下操作：\n\n你可以按任意顺序应用这些操作，允许对同一个子串多次应用操作。\n\n求获得一个仅由 1 组成...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the binary string.  \nLet $ x, y \\in \\mathbb{Z}_{\\geq 0} $ be the costs of the reverse and invert operations, respectively.  \nLet $ a = (a_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments