codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1207C.md (3253B)


      1 Source: https://codeforces.com/problemset/problem/1207/C
      2 
      3 C. Gas Pipeline
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are responsible for installing a gas pipeline along a road. Let's consider the road (for simplicity) as a segment $[0, n]$ on $OX$ axis. The road can have several crossroads, but for simplicity, we'll denote each crossroad as an interval $(x, x + 1)$ with integer $x$. So we can represent the road as a binary string consisting of $n$ characters, where character 0 means that current interval doesn't contain a crossroad, and 1 means that there is a crossroad.
     22 
     23 Usually, we can install the pipeline along the road on height of $1$ unit with supporting pillars in each integer point (so, if we are responsible for $[0, n]$ road, we must install $n + 1$ pillars). But on crossroads we should lift the pipeline up to the height $2$, so the pipeline won't obstruct the way for cars.
     24 
     25 We can do so inserting several zig-zag-like lines. Each zig-zag can be represented as a segment $[x, x + 1]$ with integer $x$ consisting of three parts: $0.5$ units of horizontal pipe + $1$ unit of vertical pipe + $0.5$ of horizontal. Note that if pipeline is currently on height $2$, the pillars that support it should also have length equal to $2$ units.
     26 
     27  ![](https://espresso.codeforces.com/d9d49d8d0560a060a2f1fc785ef616c3b1af3c0b.png) 
     28 
     29 Each unit of gas pipeline costs us $a$ bourles, and each unit of pillar — $b$ bourles. So, it's not always optimal to make the whole pipeline on the height $2$. Find the shape of the pipeline with minimum possible cost and calculate that cost.
     30 
     31 Note that you must start and finish the pipeline on height $1$ and, also, it's guaranteed that the first and last characters of the input string are equal to 0.
     32 
     33 Input
     34 
     35 The fist line contains one integer $T$ ($1 \le T \le 100$) — the number of queries. Next $2 \cdot T$ lines contain independent queries — one query per two lines.
     36 
     37 The first line contains three integers $n$, $a$, $b$ ($2 \le n \le 2 \cdot 10^5$, $1 \le a \le 10^8$, $1 \le b \le 10^8$) — the length of the road, the cost of one unit of the pipeline and the cost of one unit of the pillar, respectively.
     38 
     39 The second line contains binary string $s$ ($|s| = n$, $s_i \in \{0, 1\}$, $s_1 = s_n = 0$) — the description of the road.
     40 
     41 It's guaranteed that the total length of all strings $s$ doesn't exceed $2 \cdot 10^5$.
     42 
     43 Output
     44 
     45 Print $T$ integers — one per query. For each query print the minimum possible cost of the constructed pipeline.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 4
     53 8 2 5
     54 00110010
     55 8 1 1
     56 00110010
     57 9 100000000 100000000
     58 010101010
     59 2 5 1
     60 00
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 94
     67 25
     68 2900000000
     69 13
     70 ```
     71 
     72 Note
     73 
     74 The optimal pipeline for the first query is shown at the picture above.
     75 
     76 The optimal pipeline for the second query is pictured below:
     77 
     78  ![](https://espresso.codeforces.com/a41006fd19dd10b3d679b41d596923b03797cc43.png) 
     79 
     80 The optimal (and the only possible) pipeline for the third query is shown below:
     81 
     82  ![](https://espresso.codeforces.com/c500012aeed6af93d1135531ce2657d2a8f9cc76.png) 
     83 
     84 The optimal pipeline for the fourth query is shown below:
     85 
     86  ![](https://espresso.codeforces.com/f5236edc8e3bd8bf1e756268fa678efcb31f7901.png)