Flow God và n em gái

Points: 200 (partial)

Time limit: 1.0s

Memory limit: 256M

Input: stdin

Output: stdout

Author:

cuom1999

Problem type

Flow God có $n$ em gái. Sau khi cùng các em làm việc nhà trong ngày sinh nhật của mình, Flow God và các em gái được bố mẹ thưởng kẹo. Mức thưởng được xét dựa trên năng lực: Làm ít ăn ít, làm nhiều ăn nhiều. Em gái thứ $i$ được thưởng $a_i$ viên kẹo, còn Flow God được thưởng $x$ viên kẹo.

Flow God rất rộng lượng nhưng các em gái thì không. Nói cách khác, Flow God có thể đem kẹo của mình cho các em nhưng các em gái thì chỉ nhận kẹo mà không bao giờ chia sẻ cho ai khác. Là một người con trung thành với lý tưởng Xã Hội Chủ Nghĩa, Flow God muốn số kẹo của mọi người phải bằng nhau. Để thực hiện điều đó, anh có thể lấy vài viên kẹo của mình cho vài em gái. Flow God tự hỏi liệu mình có thể làm mọi người bình đẳng được không?

Input

Dòng đầu tiên chứa một số nguyên dương $t$ , số trường hợp mà Flow God cần giúp đỡ (Flow God có nhiều nhóm em gái khác nhau ...)

Với mỗi trường hợp:

Dòng đầu tiên chứa $2$ số nguyên $n, x$
Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, ..., a_n$

Output

In ra $t$ dòng, mỗi dòng chứa đáp số cho trường hợp tương ứng. In ra "YES" nếu Flow God có thể đạt được ước nguyện làm cho thế giới bình đẳng, "NO" nếu ngược lại.

Constraints

$t \leq 10^5$
$1 \leq n \leq 10^5, 0 \leq x \leq 10^9$
$0 \leq a_i \leq 10^9$
Tổng các số $n$ trong một input không vượt quá $10^5$

Scoring

Subtask $1$ ( $30\%$ số điểm): $a_1=a_2=...=a_n=0$ .
Subtask $2$ ( $30\%$ số điểm): $a_1=a_2=...=a_n$ .
Subtask $3$ ( $40\%$ số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

Output

YES
NO
YES

Note

Trong trường hợp đầu tiên, Flow God có thể cho em gái thứ nhất $2$ viên kẹo, em gái thứ hai $1$ viên kẹo. Cuối cùng, mọi người đều có $2$ viên kẹo.

Comments

1
SPyofgame commented on 8:47 p.m. 14 jun, 2020 ← edited →
Spoiler Alert

Solve

Gọi ( $mx$ ) là hằng số chỉ số lượng viên kẹo lớn nhất một em gái có được

Đầu tiên mình sẽ phát kẹo sao cho ( $n + 1$ ) em gái đều nhận ( $mx$ ) viên kẹo $= (mx) * (n + 1)$

Trước đó đã có một lượng ( $sum$ ) viên kẹo

Sau khi phát thì số viên kẹo còn lại là $(new_k) = (k) - (mx) * (n + 1) + (sum)$ viên

Nếu $(new_k) < 0$ (tức là không đủ viên để phát) -> "NO"

Thử phát tiếp ( $new_k$ ) viên kẹo còn lại cho ( $n + 1$ ) người.

Vì mọi người phải bình đẳng nên nếu $(new_k) = (m) * (n + 1)$ thì mọi người đều có $(mx) + (m)$ viên kẹo

$(new_k) % (n + 1) = 0$ thì in "YES" không thì in "NO"

Reference AC code | $O(n \times q)$ time | $O(1)$ auxiliary space | Math

int query() { int n = readInt(); ll k = readInt(); ll sum = 0; int mx = 0; for (int i = 0; i < n; ++i) { int x = readInt(); mx = max(mx, x); sum += x; } k -= 1LL * mx * (n + 1) - sum; if (k < 0) return cout << "NO\n", 0; cout << (k % (n + 1) == 0 ? "YES\n" : "NO\n"); return 0; }