1397B.md (1360B)
1 Source: https://codeforces.com/problemset/problem/1397/B 2 3 B. Power Sequence 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 a list of positive integers $a_0, a_1, ..., a_{n-1}$ a power sequence if there is a positive integer $c$, so that for every $0 \le i \le n-1$ then $a_i = c^i$. 22 23 Given a list of $n$ positive integers $a_0, a_1, ..., a_{n-1}$, you are allowed to: 24 25 * Reorder the list (i.e. pick a permutation $p$ of $\{0,1,...,n - 1\}$ and change $a_i$ to $a_{p_i}$), then 26 * Do the following operation any number of times: pick an index $i$ and change $a_i$ to $a_i - 1$ or $a_i + 1$ (i.e. increment or decrement $a_i$ by $1$) with a cost of $1$. 27 28 Find the minimum cost to transform $a_0, a_1, ..., a_{n-1}$ into a power sequence. 29 30 Input 31 32 The first line contains an integer $n$ ($3 \le n \le 10^5$). 33 34 The second line contains $n$ integers $a_0, a_1, ..., a_{n-1}$ ($1 \le a_i \le 10^9$). 35 36 Output 37 38 Print the minimum cost to transform $a_0, a_1, ..., a_{n-1}$ into a power sequence. 39 40 Examples 41 42 Input 43 44 ``` 45 3 46 1 3 2 47 ``` 48 49 Output 50 51 ``` 52 1 53 ``` 54 55 Input 56 57 ``` 58 3 59 1000000000 1000000000 1000000000 60 ``` 61 62 Output 63 64 ``` 65 1999982505 66 ``` 67 68 Note 69 70 In the first example, we first reorder $\{1, 3, 2\}$ into $\{1, 2, 3\}$, then increment $a_2$ to $4$ with cost $1$ to get a power sequence $\{1, 2, 4\}$.