P7996 [WFOI - 01] Coins (coin)

In front of you there is a row of $n$ **piles** of coins in a line. Coins in the **same pile** have the same face value; denote the face value of the $i$-th pile by $a_i$. The **number of coins in each pile** is the same, denoted by $x$. Now you are given the face value $a_i$ of each pile. You need to determine a **positive integer** $x$ such that the variance of the **total amount of money in each pile** is closest to a **positive integer** $k$. Definition of **“closest”** between two numbers: the absolute value of their difference is minimal. Variance definition: $s ^ 2 = \cfrac{(a_1 - \bar x)^2 + (a_2 - \bar x) ^ 2 + \cdots + (a_n - \bar x) ^ 2}{n}$, where $\bar x$ represents the average of $x$.

The first line contains two integers $n,k$. The second line contains $n$ integers. The $i$-th integer is $a_i$, meaning the face value of the $i$-th pile is $a_i$.

Output one **positive integer** on one line, representing the value of $x$ that satisfies the requirement. If there are multiple answers, output the smallest one. If no matter what value $x$ takes the variance is always $0$, output one line `No answer!`.

**[Sample $\#1$ Explanation]** When $x=3$, the amount of money in the $i$-th pile is $3\times a_i$. These amounts are $21,6,12,18,9,21,30$. The variance of these amounts is approximately $58.78$. It can be proven that when $x=3$, the variance is closest to $47$. **[Sample $\#2$ Explanation]** It can be found that no matter what value $x$ takes, the variance will be $0$, so output `No answer!`. **[Constraints]** **This problem uses bundled Subtask testdata.** Subtask ID | $n,\forall a_i\le$ | $k\le$ | $\footnotesize\texttt{Number of test points}$ | :-: | :-: | :-: | :-: **Subtask #0 $(20\texttt{pts})$** | $10^3$ | $10^9$| $6$ | **Subtask #1 $(25\texttt{pts})$** | $10^5$ | $10^{12}$| $6$ | **Subtask #2 $(25\texttt{pts})$** | $10^5$ | $10^{18}$| $6$ | **Subtask #3 $(30\texttt{pts})$** | $7\times10^6$ | $3\times 10^{18}$| $6$ | For $100\%$ of the testdata, $1\le n,\forall a_i\le7\times10^6$, $1\le k\le3\times10^{18}$. Let the variance of the original array $a$ be $p$. Then the testdata satisfies $p=0$ or $p\in[0.25,\ 2^{63}-1]$. **[Hint]** The input size of this problem is large. Please use a suitable input method. Here we recommend a [fast input template](https://www.luogu.com.cn/paste/bcfvgxr7). For $\texttt{C/C++}$, you can also use `scanf` to read input. To avoid precision issues, $\texttt{C/C++}$ users are advised to use type $\texttt{double}$, and it is not recommended to use `eps`. Translated by ChatGPT 5