codeforces-scrape

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

1667A.md (1330B)


      1 Source: https://codeforces.com/problemset/problem/1667/A
      2 
      3 A. Make it Increasing
      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 given an array $a$ consisting of $n$ positive integers, and an array $b$, with length $n$. Initially $b_i=0$ for each $1 \leq i \leq n$.
     22 
     23 In one move you can choose an integer $i$ ($1 \leq i \leq n$), and add $a_i$ to $b_i$ or subtract $a_i$ from $b_i$. What is the minimum number of moves needed to make $b$ increasing (that is, every element is strictly greater than every element before it)?
     24 
     25 Input
     26 
     27 The first line contains a single integer $n$ ($2 \leq n \leq 5000$).
     28 
     29 The second line contains $n$ integers, $a_1$, $a_2$, ..., $a_n$ ($1 \leq a_i \leq 10^9$) — the elements of the array $a$.
     30 
     31 Output
     32 
     33 Print a single integer, the minimum number of moves to make $b$ increasing.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 5
     41 1 2 3 4 5
     42 ```
     43 
     44 Output
     45 
     46 ```
     47 4
     48 ```
     49 
     50 Input
     51 
     52 ```
     53 7
     54 1 2 1 2 1 2 1
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 10
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 8
     67 1 8 2 7 3 6 4 5
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 16
     74 ```
     75 
     76 Note
     77 
     78 Example $1$: you can subtract $a_1$ from $b_1$, and add $a_3$, $a_4$, and $a_5$ to $b_3$, $b_4$, and $b_5$ respectively. The final array will be [$-1$, $0$, $3$, $4$, $5$] after $4$ moves.
     79 
     80 Example $2$: you can reach [$-3$, $-2$, $-1$, $0$, $1$, $2$, $3$] in $10$ moves.