codeforces-scrape

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

1491B.md (3092B)


      1 Source: https://codeforces.com/problemset/problem/1491/B
      2 
      3 B. Minimal Cost
      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 There is a graph of $n$ rows and $10^6 + 2$ columns, where rows are numbered from $1$ to $n$ and columns from $0$ to $10^6 + 1$:
     22 
     23  ![](https://espresso.codeforces.com/85a0ce2f95971b622b912410ca93d171f8ae1480.png) 
     24 
     25 Let's denote the node in the row $i$ and column $j$ by $(i, j)$.
     26 
     27 Initially for each $i$ the $i$-th row has exactly one obstacle — at node $(i, a_i)$. You want to move some obstacles so that you can reach node $(n, 10^6+1)$ from node $(1, 0)$ by moving through edges of this graph (you can't pass through obstacles). Moving one obstacle to an adjacent by edge free node costs $u$ or $v$ coins, as below:
     28 
     29 * If there is an obstacle in the node $(i, j)$, you can use $u$ coins to move it to $(i-1, j)$ or $(i+1, j)$, if such node exists and if there is no obstacle in that node currently.
     30 * If there is an obstacle in the node $(i, j)$, you can use $v$ coins to move it to $(i, j-1)$ or $(i, j+1)$, if such node exists and if there is no obstacle in that node currently.
     31 * Note that you can't move obstacles outside the grid. For example, you can't move an obstacle from $(1,1)$ to $(0,1)$.
     32 
     33 Refer to the picture above for a better understanding.
     34 
     35 Now you need to calculate the minimal number of coins you need to spend to be able to reach node $(n, 10^6+1)$ from node $(1, 0)$ by moving through edges of this graph without passing through obstacles.
     36 
     37 Input
     38 
     39 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     40 
     41 The first line of each test case contains three integers $n$, $u$ and $v$ ($2 \le n \le 100$, $1 \le u, v \le 10^9$) — the number of rows in the graph and the numbers of coins needed to move vertically and horizontally respectively.
     42 
     43 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — where $a_i$ represents that the obstacle in the $i$-th row is in node $(i, a_i)$.
     44 
     45 It's guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^4$.
     46 
     47 Output
     48 
     49 For each test case, output a single integer — the minimal number of coins you need to spend to be able to reach node $(n, 10^6+1)$ from node $(1, 0)$ by moving through edges of this graph without passing through obstacles.
     50 
     51 It can be shown that under the constraints of the problem there is always a way to make such a trip possible.
     52 
     53 Example
     54 
     55 Input
     56 
     57 ```
     58 3
     59 2 3 4
     60 2 2
     61 2 3 4
     62 3 2
     63 2 4 3
     64 3 2
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 7
     71 3
     72 3
     73 ```
     74 
     75 Note
     76 
     77 In the first sample, two obstacles are at $(1, 2)$ and $(2,2)$. You can move the obstacle on $(2, 2)$ to $(2, 3)$, then to $(1, 3)$. The total cost is $u+v = 7$ coins.
     78 
     79  ![](https://espresso.codeforces.com/310a26a2eae89672776febf07dac23d953ebb615.png) 
     80 
     81 In the second sample, two obstacles are at $(1, 3)$ and $(2,2)$. You can move the obstacle on $(1, 3)$ to $(2, 3)$. The cost is $u = 3$ coins.
     82 
     83  ![](https://espresso.codeforces.com/14098571b9970678331e7aacc7a4e7ffe5f175fe.png)