1105A.md (1750B)
1 Source: https://codeforces.com/problemset/problem/1105/A 2 3 A. Salem and Sticks 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 Salem gave you $n$ sticks with integer positive lengths $a_1, a_2, \ldots, a_n$. 22 23 For every stick, you can change its length to any other positive integer length (that is, either shrink or stretch it). The cost of changing the stick's length from $a$ to $b$ is $|a - b|$, where $|x|$ means the absolute value of $x$. 24 25 A stick length $a_i$ is called almost good for some integer $t$ if $|a_i - t| \le 1$. 26 27 Salem asks you to change the lengths of some sticks (possibly all or none), such that all sticks' lengths are almost good for some positive integer $t$ and the total cost of changing is minimum possible. The value of $t$ is not fixed in advance and you can choose it as any positive integer. 28 29 As an answer, print the value of $t$ and the minimum cost. If there are multiple optimal choices for $t$, print any of them. 30 31 Input 32 33 The first line contains a single integer $n$ ($1 \le n \le 1000$) — the number of sticks. 34 35 The second line contains $n$ integers $a_i$ ($1 \le a_i \le 100$) — the lengths of the sticks. 36 37 Output 38 39 Print the value of $t$ and the minimum possible cost. If there are multiple optimal choices for $t$, print any of them. 40 41 Examples 42 43 Input 44 45 ``` 46 3 47 10 1 4 48 ``` 49 50 Output 51 52 ``` 53 3 7 54 ``` 55 56 Input 57 58 ``` 59 5 60 1 1 2 2 3 61 ``` 62 63 Output 64 65 ``` 66 2 0 67 ``` 68 69 Note 70 71 In the first example, we can change $1$ into $2$ and $10$ into $4$ with cost $|1 - 2| + |10 - 4| = 1 + 6 = 7$ and the resulting lengths $[2, 4, 4]$ are almost good for $t = 3$. 72 73 In the second example, the sticks lengths are already almost good for $t = 2$, so we don't have to do anything.