246B.md (1450B)
1 Source: https://codeforces.com/problemset/problem/246/B 2 3 B. Increase and Decrease 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Polycarpus has an array, consisting of *n* integers *a*1, *a*2, ..., *a**n*. Polycarpus likes it when numbers in an array match. That's why he wants the array to have as many equal numbers as possible. For that Polycarpus performs the following operation multiple times: 22 23 * he chooses two elements of the array *a**i*, *a**j* (*i* ≠ *j*); 24 * he simultaneously increases number *a**i* by 1 and decreases number *a**j* by 1, that is, executes *a**i* = *a**i* + 1 and *a**j* = *a**j* - 1. 25 26 The given operation changes exactly two distinct array elements. Polycarpus can apply the described operation an infinite number of times. 27 28 Now he wants to know what maximum number of equal array elements he can get if he performs an arbitrary number of such operation. Help Polycarpus. 29 30 Input 31 32 The first line contains integer *n* (1 ≤ *n* ≤ 105) — the array size. The second line contains space-separated integers *a*1, *a*2, ..., *a**n* (|*a**i*| ≤ 104) — the original array. 33 34 Output 35 36 Print a single integer — the maximum number of equal array elements he can get if he performs an arbitrary number of the given operation. 37 38 Examples 39 40 Input 41 42 ``` 43 2 44 2 1 45 ``` 46 47 Output 48 49 ``` 50 1 51 ``` 52 53 Input 54 55 ``` 56 3 57 1 4 1 58 ``` 59 60 Output 61 62 ``` 63 3 64 ```