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.