codeforces-scrape

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

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\}$.