codeforces-scrape

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

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.