English · Original
Chinese · Translation
Formal · Original
Anya and Kirill are doing a physics laboratory work. In one of the tasks they have to measure some value _n_ times, and then compute the average value to lower the error.
Kirill has already made his measurements, and has got the following integer values: _x_1, _x_2, ..., _x__n_. It is important that the values are close to each other, namely, the difference between the maximum value and the minimum value is **at most 2**.
Anya does not want to make the measurements, however, she can't just copy the values from Kirill's work, because the error of each measurement is a random value, and this coincidence will be noted by the teacher. Anya wants to write such integer values _y_1, _y_2, ..., _y__n_ in her work, that the following conditions are met:
* the average value of _x_1, _x_2, ..., _x__n_ is equal to the average value of _y_1, _y_2, ..., _y__n_;
* all Anya's measurements are in the same bounds as all Kirill's measurements, that is, the maximum value among Anya's values is not greater than the maximum value among Kirill's values, and the minimum value among Anya's values is not less than the minimum value among Kirill's values;
* the number of equal measurements in Anya's work and Kirill's work is as small as possible among options with the previous conditions met. Formally, the teacher goes through all Anya's values one by one, if there is equal value in Kirill's work and it is not strike off yet, he strikes off this Anya's value and one of equal values in Kirill's work. The number of equal measurements is then the total number of **strike off** values in Anya's work.
Help Anya to write such a set of measurements that the conditions above are met.
## Input
The first line contains a single integer _n_ (1 ≤ _n_ ≤ 100 000) — the numeber of measurements made by Kirill.
The second line contains a sequence of integers _x_1, _x_2, ..., _x__n_ ( - 100 000 ≤ _x__i_ ≤ 100 000) — the measurements made by Kirill. It is guaranteed that the difference between the maximum and minimum values among values _x_1, _x_2, ..., _x__n_ does not exceed 2.
## Output
In the first line print the minimum possible number of equal measurements.
In the second line print _n_ integers _y_1, _y_2, ..., _y__n_ — the values Anya should write. You can print the integers in arbitrary order. Keep in mind that the minimum value among Anya's values should be not less that the minimum among Kirill's values, and the maximum among Anya's values should be not greater than the maximum among Kirill's values.
If there are multiple answers, print any of them.
[samples]
## Note
In the first example Anya can write zeros as here measurements results. The average value is then equal to the average value of Kirill's values, and there are only two equal measurements.
In the second example Anya should write two values 100 and one value 101 (in any order), because it is the only possibility to make the average be the equal to the average of Kirill's values. Thus, all three measurements are equal.
In the third example the number of equal measurements is 5.
Anya 和 Kirill 正在进行一项物理实验。在其中一项任务中，他们需要测量某个值 #cf_span[n] 次，然后计算平均值以减小误差。
Kirill 已经完成了他的测量，得到了以下整数值：#cf_span[x1], #cf_span[x2], ..., #cf_span[xn]。重要的是，这些值彼此接近，即最大值与最小值的差 *至多为 #cf_span[2]*。
Anya 不想进行测量，但她也不能直接复制 Kirill 的结果，因为每次测量的误差是随机的，这种巧合会被老师发现。Anya 希望在她的实验报告中写下一组整数值 #cf_span[y1], #cf_span[y2], ..., #cf_span[yn]，满足以下条件：
帮助 Anya 写出一组满足上述条件的测量值。
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100 000]) —— Kirill 做的测量次数。
第二行包含一个整数序列 #cf_span[x1, x2, ..., xn] (#cf_span[ - 100 000 ≤ xi ≤ 100 000]) —— Kirill 的测量值。保证 #cf_span[x1, x2, ..., xn] 中最大值与最小值的差不超过 #cf_span[2]。
第一行输出可能的最小相等测量值个数。
第二行输出 #cf_span[n] 个整数 #cf_span[y1, y2, ..., yn] —— Anya 应该写出的值。你可以按任意顺序输出这些整数。注意：Anya 的值中的最小值不应小于 Kirill 值中的最小值，Anya 的值中的最大值不应大于 Kirill 值中的最大值。
如果有多个答案，输出任意一个即可。
在第一个例子中，Anya 可以将她的测量结果写为零。此时平均值等于 Kirill 测量值的平均值，且只有两个相等的测量值。
在第二个例子中，Anya 必须写两个 #cf_span[100] 和一个 #cf_span[101]（顺序任意），因为这是使平均值等于 Kirill 平均值的唯一可能。因此，所有三个测量值都相等。
在第三个例子中，相等测量值的个数为 #cf_span[5]。
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100 000]) —— Kirill 做的测量次数。第二行包含一个整数序列 #cf_span[x1, x2, ..., xn] (#cf_span[ - 100 000 ≤ xi ≤ 100 000]) —— Kirill 的测量值。保证 #cf_span[x1, x2, ..., xn] 中最大值与最小值的差不超过 #cf_span[2]。
## Output
第一行输出可能的最小相等测量值个数。第二行输出 #cf_span[n] 个整数 #cf_span[y1, y2, ..., yn] —— Anya 应该写出的值。你可以按任意顺序输出这些整数。注意：Anya 的值中的最小值不应小于 Kirill 值中的最小值，Anya 的值中的最大值不应大于 Kirill 值中的最大值。如果有多个答案，输出任意一个即可。
[samples]
## Note
在第一个例子中，Anya 可以将她的测量结果写为零。此时平均值等于 Kirill 测量值的平均值，且只有两个相等的测量值。在第二个例子中，Anya 必须写两个 #cf_span[100] 和一个 #cf_span[101]（顺序任意），因为这是使平均值等于 Kirill 平均值的唯一可能。因此，所有三个测量值都相等。在第三个例子中，相等测量值的个数为 #cf_span[5]。
Let $ n \in \mathbb{N} $, $ n \geq 1 $, and let $ x_1, x_2, \dots, x_n \in \mathbb{Z} $ be given such that $ \max_i x_i - \min_i x_i \leq 2 $.
Define:
- $ m = \min_i x_i $,
- $ M = \max_i x_i $,
- $ \mu = \frac{1}{n} \sum_{i=1}^n x_i $ (the mean of Kirill’s measurements).
Anya must choose integers $ y_1, y_2, \dots, y_n \in \mathbb{Z} $ such that:
1. $ \frac{1}{n} \sum_{i=1}^n y_i = \mu $,
2. $ m \leq \min_i y_i \leq \max_i y_i \leq M $,
3. The number of equal values among $ y_1, \dots, y_n $ is minimized.
Let $ S = \{ m, m+1, \dots, M \} $. Since $ M - m \leq 2 $, we have $ |S| \in \{1, 2, 3\} $.
Let $ a, b, c \in \mathbb{Z}_{\geq 0} $ denote the counts of $ m $, $ m+1 $, $ m+2 $ in Anya’s sequence, respectively. Then:
- $ a + b + c = n $,
- $ a \cdot m + b \cdot (m+1) + c \cdot (m+2) = n \mu $.
Substitute $ \mu = \frac{1}{n} \sum x_i $, so the second equation becomes:
$$
a m + b(m+1) + c(m+2) = \sum_{i=1}^n x_i
$$
$$
\Rightarrow m(a + b + c) + b + 2c = \sum x_i
$$
$$
\Rightarrow m n + b + 2c = \sum x_i
\Rightarrow b + 2c = \sum x_i - m n
$$
Let $ D = \sum x_i - m n $. Then:
$$
b + 2c = D, \quad a = n - b - c
$$
We seek non-negative integers $ a, b, c $ satisfying the above, and minimizing $ \max(a, b, c) $ (i.e., minimizing the maximum frequency — which corresponds to minimizing the number of equal measurements).
Let $ k = \max(a, b, c) $. Minimize $ k $ over all integer solutions $ (a,b,c) \in \mathbb{Z}_{\geq 0}^3 $ to:
- $ b + 2c = D $,
- $ a = n - b - c \geq 0 $.
Then output:
- First line: $ k $
- Second line: $ a $ copies of $ m $, $ b $ copies of $ m+1 $, $ c $ copies of $ m+2 $ (in any order)
API Response (JSON)
{
"problem": {
"name": "C. Laboratory Work",
"description": {
"content": "Anya and Kirill are doing a physics laboratory work. In one of the tasks they have to measure some value _n_ times, and then compute the average value to lower the error. Kirill has already made his ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF931C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Anya and Kirill are doing a physics laboratory work. In one of the tasks they have to measure some value _n_ times, and then compute the average value to lower the error.\n\nKirill has already made his ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Anya 和 Kirill 正在进行一项物理实验。在其中一项任务中，他们需要测量某个值 #cf_span[n] 次，然后计算平均值以减小误差。\n\nKirill 已经完成了他的测量，得到了以下整数值：#cf_span[x1], #cf_span[x2], ..., #cf_span[xn]。重要的是，这些值彼此接近，即最大值与最小值的差 *至多为 #cf_span[2]*。\n\nAnya 不想进行测量...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ n \\in \\mathbb{N} $, $ n \\geq 1 $, and let $ x_1, x_2, \\dots, x_n \\in \\mathbb{Z} $ be given such that $ \\max_i x_i - \\min_i x_i \\leq 2 $.\n\nDefine:\n- $ m = \\min_i x_i $,\n- $ M = \\max_i x_i $,\n- $ ...",
"is_translate": false,
"language": "Formal"
}
]
}