codeforces-scrape

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

1113B.md (2258B)


      1 Source: https://codeforces.com/problemset/problem/1113/B
      2 
      3 B. Sasha and Magnetic Machines
      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 One day Sasha visited the farmer 2D and his famous magnetic farm. On this farm, the crop grows due to the influence of a special magnetic field. Maintaining of the magnetic field is provided by $n$ machines, and the power of the $i$-th machine is $a_i$.
     22 
     23 This year 2D decided to cultivate a new culture, but what exactly he didn't say. For the successful growth of the new culture, it is necessary to slightly change the powers of the machines. 2D can at most once choose an arbitrary integer $x$, then choose one machine and reduce the power of its machine by $x$ times, and at the same time increase the power of one another machine by $x$ times (powers of all the machines must stay positive integers). Note that he may not do that if he wants. More formally, 2D can choose two such indices $i$ and $j$, and one integer $x$ such that $x$ is a divisor of $a_i$, and change powers as following: $a_i = \frac{a_i}{x}$, $a_j = a_j \cdot x$
     24 
     25 Sasha is very curious, that's why he wants to calculate the minimum total power the farmer can reach. There are too many machines, and Sasha can't cope with computations, help him!
     26 
     27 Input
     28 
     29 The first line contains one integer $n$ ($2 \le n \le 5 \cdot 10^4$) — the number of machines.
     30 
     31 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 100$) — the powers of the machines.
     32 
     33 Output
     34 
     35 Print one integer — minimum total power.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 5
     43 1 2 3 4 5
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 14
     50 ```
     51 
     52 Input
     53 
     54 ```
     55 4
     56 4 2 4 4
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 14
     63 ```
     64 
     65 Input
     66 
     67 ```
     68 5
     69 2 4 2 3 7
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 18
     76 ```
     77 
     78 Note
     79 
     80 In the first example, the farmer can reduce the power of the $4$-th machine by $2$ times, and increase the power of the $1$-st machine by $2$ times, then the powers will be: $[2, 2, 3, 2, 5]$.
     81 
     82 In the second example, the farmer can reduce the power of the $3$-rd machine by $2$ times, and increase the power of the $2$-nd machine by $2$ times. At the same time, the farmer can leave is be as it is and the total power won't change.
     83 
     84 In the third example, it is optimal to leave it be as it is.