Flow God và n em gái

Xem PDF
Tác giả:
cuom1999
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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 
3
3 5
0 1 2
2 4
3 3
4 0
0 0 0 0
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.

Bình luận


  • 1
    SPyofgame    8:47 p.m. 14 Tháng 6, 2020 ← đã chỉnh sửa

    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

    C++
    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;
}