codeforces-scrape

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

1901B.md (2727B)


      1 Source: https://codeforces.com/problemset/problem/1901/B
      2 
      3 B. Chip and Ribbon
      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 ribbon divided into $n$ cells, numbered from $1$ to $n$ from left to right. Initially, an integer $0$ is written in each cell.
     22 
     23 Monocarp plays a game with a chip. The game consists of several turns. During the first turn, Monocarp places the chip in the $1$-st cell of the ribbon. During each turn except for the first turn, Monocarp does exactly one of the two following actions:
     24 
     25 * move the chip to the next cell (i. e. if the chip is in the cell $i$, it is moved to the cell $i+1$). This action is impossible if the chip is in the last cell;
     26 * choose any cell $x$ and teleport the chip into that cell. It is possible to choose the cell where the chip is currently located.
     27 
     28 At the end of each turn, the integer written in the cell with the chip is increased by $1$.
     29 
     30 Monocarp's goal is to make some turns so that the $1$-st cell contains the integer $c_1$, the $2$-nd cell contains the integer $c_2$, ..., the $n$-th cell contains the integer $c_n$. He wants to teleport the chip as few times as possible.
     31 
     32 Help Monocarp calculate the minimum number of times he has to teleport the chip.
     33 
     34 Input
     35 
     36 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     37 
     38 Each test case consists of two lines:
     39 
     40 * the first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$);
     41 * the second line contains $n$ integers $c_1, c_2, \dots, c_n$ ($0 \le c_i \le 10^9$; $c_1 \ge 1$).
     42 
     43 It can be shown that under these constraints, it is always possible to make a finite amount of turns so that the integers in the cells match the sequence $c_1, c_2, \dots, c_n$.
     44 
     45 Additional constraint on the input: the sum of values of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     46 
     47 Output
     48 
     49 For each test case, print one integer — the minimum number of times Monocarp has to teleport the chip.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 4
     57 
     58 4
     59 
     60 1 2 2 1
     61 
     62 5
     63 
     64 1 0 1 0 1
     65 
     66 5
     67 
     68 5 4 3 2 1
     69 
     70 1
     71 
     72 12
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 1
     79 2
     80 4
     81 11
     82 ```
     83 
     84 Note
     85 
     86 In the first test case of the example, Monocarp can perform the turns as follows:
     87 
     88 * place the chip in the $1$-st cell; the numbers in the cells are $[1, 0, 0, 0]$;
     89 * move the chip to the next ($2$-nd) cell; the numbers in the cells are $[1, 1, 0, 0]$;
     90 * move the chip to the next ($3$-rd) cell; the numbers in the cells are $[1, 1, 1, 0]$;
     91 * teleport the chip to the $2$-nd cell; the numbers in the cells are $[1, 2, 1, 0]$;
     92 * move the chip to the next ($3$-rd) cell; the numbers in the cells are $[1, 2, 2, 0]$;
     93 * move the chip to the next ($4$-th) cell; the numbers in the cells are $[1, 2, 2, 1]$.