codeforces-scrape

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

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.