1159B.md (1717B)
1 Source: https://codeforces.com/problemset/problem/1159/B 2 3 B. Expansion coefficient of the array 4 5 time limit per test 6 7 1 second 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 Let's call an array of non-negative integers $a_1, a_2, \ldots, a_n$ a $k$-extension for some non-negative integer $k$ if for all possible pairs of indices $1 \leq i, j \leq n$ the inequality $k \cdot |i - j| \leq min(a_i, a_j)$ is satisfied. The expansion coefficient of the array $a$ is the maximal integer $k$ such that the array $a$ is a $k$-extension. Any array is a 0-expansion, so the expansion coefficient always exists. 22 23 You are given an array of non-negative integers $a_1, a_2, \ldots, a_n$. Find its expansion coefficient. 24 25 Input 26 27 The first line contains one positive integer $n$ — the number of elements in the array $a$ ($2 \leq n \leq 300\,000$). The next line contains $n$ non-negative integers $a_1, a_2, \ldots, a_n$, separated by spaces ($0 \leq a_i \leq 10^9$). 28 29 Output 30 31 Print one non-negative integer — expansion coefficient of the array $a_1, a_2, \ldots, a_n$. 32 33 Examples 34 35 Input 36 37 ``` 38 4 39 6 4 5 5 40 ``` 41 42 Output 43 44 ``` 45 1 46 ``` 47 48 Input 49 50 ``` 51 3 52 0 1 2 53 ``` 54 55 Output 56 57 ``` 58 0 59 ``` 60 61 Input 62 63 ``` 64 4 65 821 500 479 717 66 ``` 67 68 Output 69 70 ``` 71 239 72 ``` 73 74 Note 75 76 In the first test, the expansion coefficient of the array $[6, 4, 5, 5]$ is equal to $1$ because $|i-j| \leq min(a_i, a_j)$, because all elements of the array satisfy $a_i \geq 3$. On the other hand, this array isn't a $2$-extension, because $6 = 2 \cdot |1 - 4| \leq min(a_1, a_4) = 5$ is false. 77 78 In the second test, the expansion coefficient of the array $[0, 1, 2]$ is equal to $0$ because this array is not a $1$-extension, but it is $0$-extension.