Flow God và n em gái

View as PDF

Submit solution


Points: 200 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
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
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.


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