HSG THPT Thanh Hóa 2022 - EQLARRAY

View as PDF
Submit solution
Points: 0.25 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: EQLARRAY.INP
Output: EQLARRAY.OUT
Author:
bedao
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho ~2~ dãy số nguyên ~a~, ~b~ đều gồm ~n~ phần tử. Ban đầu tất cả các phần tử của dãy ~a~ đều bằng ~0~. Cần biến dãy ~a~ thành dãy ~b~ bằng cách thực hiện một số lần thao tác sau:

  • Chọn ra ~k~ phần tử của dãy ~a~ và tăng mỗi phần tử thêm ~1~ đơn vị.

Yêu cầu: Kiểm tra xem có thể biến dãy ~a~ thành dãy ~b~ được hay không?

Input

Từ tệp văn bản EQLARRAY.INP gồm nhiều test có cấu trúc như sau:

  • Dòng đầu tiên của tệp chứa số nguyên dương ~Q~ là số test ~(1 \le Q \le 1000)~.

  • Tiếp theo là các test có cấu trúc như sau: Dòng đầu tiên của mỗi test chứa hai số nguyên dương ~n~ và ~k~ ~(1 \le k \le n \le 10^5)~.

  • Dòng thứ hai của mỗi test chứa dãy số nguyên ~b~ (~1 \le b_i \le 10^9, i = 1 \div n~).

Ràng buộc: Tổng các số ~n~ trong tất cả các test không vượt quá ~10^6~.

Output

Ghi ra tệp văn bản EQLARRAY.OUT với mỗi test, in kết quả trên một dòng, in "YES" nếu dãy ~a~ có thể biến thành dãy ~b~ và "NO" nếu ngược lại.

Sample Input 1

2
5 3
1 2 3 4 5
3 2
1 1 4

Sample Output 1

YES
NO

Comments

Please read the guidelines before commenting.


  • 0
    2024_VoBaoNam  commented on Nov. 9, 2024, 1:51 p.m.

    Đọc test cái phải mất 10p mới hiểu đề =)))


  • 8
    YugiHackerKhongCopCode  commented on March 25, 2024, 1:50 p.m.

    Bài y hệt tương tự: Free Contest 115 - TWOEARRAY


  • -5
    phongnq424  commented on Feb. 1, 2024, 11:49 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 1
      Lilinta  commented on Feb. 1, 2024, 2:03 p.m.

      Code của bạn bị tràn số khi tính tổng và gtln*k. Bạn có thể thay int thành long long nhé.


  • 1
    quandeptrai123  commented on Jan. 29, 2024, 4:07 p.m.

    hướng giải bài này là như nào ạ?


    • 24
      SunRise  commented on Feb. 2, 2024, 2:14 p.m.

      Spoil

      Nhận xét: Gọi s là tổng các phần tử trong mảng b

      Nhận xét 1: do b được tạo nên bởi hữu hạn lần k vậy nên s sẽ chia hết cho k, nếu không chia hết thì chắc chắn không thể tạo nên dãy b từ dãy a

      Nhận xét 2: dễ thấy để biến từ dãy a thành dãy b sẽ cần s / k lần

      Vậy nên phần tử lớn nhất dãy a có thể tạo được là s / k, nếu s / k bé hơn phần tử lớn nhất của dãy b thì cũng không tạo được dãy b từ dãy a


      • -1
        xuanquanna  commented on Sept. 29, 2024, 2:01 p.m.

        include<bits/stdc++.h>

        using namespace std;

        define ll long long

        define nmax 100004

        ll a[nmax]; int main() { ios::syncwithstdio(0); cin.tie(0);cout.tie(0); freopen("EQLARRAY.inp","r",stdin); freopen("EQLARRAY.out","w",stdout); ll n , t, s = 0, k , m = -1e18; cin >> t; while(t--){ m = -1e18; cin >> n >> k; for (int i =1; i <= n; i++){ cin >> a[i]; s+=a[i]; m = max(m , a[i]); } if (m <= s/k and s%k == 0){ cout << "YES" << endl; } else cout << "NO" << endl; } } code như này sao lại sai v ae