Đổi ngọc

Xem dạng PDF
Gửi bài giải
Điểm: 0,10 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Tác giả:
vnoicup
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bạn đang chơi trò chơi MMO thịnh hành nhất hiện tại. Hệ thống tiền tệ của game là ngọc, được chia làm ~n~ cấp độ. Hiện tại, bạn đang có ~a_i~ viên ngọc ở cấp độ ~i~. Để mua món trang bị đắt tiền nhất trong game hiện giờ, bạn cần trả ~b_i~ viên ngọc ở cấp độ ~i~.

Trò chơi có hệ thống đổi ngọc, cho phép bạn:

  • Đổi ~2~ viên ngọc ở cấp độ ~i~ để lấy ~1~ viên ngọc ở cấp độ ~i+1~ (với ~1 \le i < n~).

  • Đổi ~1~ viên ngọc ở cấp độ ~i~ để lấy ~2~ viên ngọc ở cấp độ ~i-1~ (với ~1 < i \le n~).

Hãy cho biết có cách đổi ngọc nào giúp bạn có đủ số ngọc cần có ở mỗi cấp độ để mua trang bị bằng cách đổi ngọc không hay nhiều lần hay không.

Input

Mỗi test gồm nhiều test case. Dòng đầu tiên của bộ dữ liệu chứa số nguyên dương ~t~ (~1 \le t \le 10\,000~) là số lượng test case. Mô tả của mỗi test case như sau.

Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 2 \cdot 10^5~) — số lượng cấp độ ngọc.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~0 \le a_i \le 10^9~) — số viên ngọc bạn đang có ở mỗi cấp độ.

Dòng thứ ba chứa ~n~ số nguyên ~b_1, b_2, \ldots, b_n~ (~0 \le b_i \le 10^9~) — số viên ngọc cần có ở mỗi cấp độ.

Dữ liệu đảm bảo rằng tổng ~n~ trong tất cả các test case không quá ~2 \cdot 10^5~.

Output

Với mỗi test case, hãy in ra "YES" nếu tồn tại cách đổi ngọc để đạt đủ số ngọc cần có ở mỗi cấp độ, hoặc in ra "NO" trong trường hợp ngược lại.

Scoring

Subtask Điểm Ràng buộc
1 ~500~ ~n \le 20~
2 ~500~ Không có ràng buộc gì thêm
Tổng ~1000~

Sample Input 1

4
4
1 1 4 5
3 1 2 3
2
1 0
0 1
3
1 1 1
1 1 1
1
1
100

Sample Output 1

YES
NO
YES
NO

Notes

Trong test case đầu tiên, bạn có thể:

  • Đổi ~1~ viên ngọc cấp ~2~ để lấy ~2~ viên ngọc cấp ~1~. Số ngọc bạn có ở từng cấp độ trở thành ~[3, 0, 4, 5]~.

  • Đổi ~1~ viên ngọc cấp ~3~ để lấy ~2~ viên ngọc cấp ~2~. Số ngọc bạn có ở từng cấp độ trở thành ~[3, 2, 3, 5]~.

Lúc này, bạn đã có đủ số lượng ngọc cần có ở mỗi cấp độ.

Trong test case thứ hai, bạn chỉ có ~1~ viên ngọc cấp ~1~, nên bạn không thể thực hiện bất kì phép đổi ngọc nào. Do đó, bạn không thể có đủ lượng ngọc cấp ~2~ được yêu cầu.

Trong test case thứ ba, ngay từ đầu bạn đã có đủ số ngọc cần có ở mỗi cấp độ.

Trong test case thứ tư, hệ thống chỉ có đúng ~1~ cấp độ ngọc nên bạn không thể thực hiện bất kì phép đổi ngọc nào, đồng thời bạn cũng không có đủ lượng ngọc cấp ~1~ được yêu cầu.

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 4
    khai05  đã bình luận lúc 5, Tháng 6, 2024, 20:36 ← chỉnh sửa

    nếu a[i]-b[i]>=0 , bạn có thể lấy phần dư của nó /2 thì lúc đó a[i+1] sẽ có thêm (a[i]-b[i])/2;

    cũng tương tự với trường hợp với a[i]-b[i]<0 thì bạn phải lấy số ngọc của a[i+1] bù cho lúc ấy a[i+1] sẽ mất (a[i]-b[i]-1)/2

    đến cuối bạn kiểm tra nếu a[n]-b[n]<0 thì "NO" ngược lại thì "YES"


  • -1
    melondepchai  đã bình luận lúc 3, Tháng 6, 2024, 7:17

    Bài này xử lý số nguyên lớn như nào vậy mọi người, em đọc solution vẫn không hiểu


    • 8
      anle82917  đã bình luận lúc 4, Tháng 6, 2024, 11:43 ← sửa 32

      Bài này mình có cách giải không cần dùng số nguyên lớn nè. !!!!!!!!!!!!!!!!!!!!!!!!!!!!SPOILER :

      Dồn tất cả giá trị sang a[n] hay :

      a[i+1]+=a[i]/2

      a[i]=a[i]%2

      Khi đó chỉ cần chạy giật lùi từ n đến 1

      Rồi lấy a[i] - b[i] . Nếu còn dư thì dồn xuống a[i-1] ( a[i-1]+=a[i]*2)

      Đến đây sẽ bị tràn số dò tăng theo cấp số nhân

      Phần này mình sẽ lập luận như sau :

      Nếu a[i]>= 2 * 10 ^ 9

      Do giới hạn b[i] <= 10 ^ 9

      ==> a[i] - b[i] >= 10 ^ 9

      Và a[i] - b[i] chính là phần dư để dồn xuống a[i-1]

      Hay a[i-1] += (a[i]-b[i])*2

      Khi đó a[i-1] >= 2 * 10 ^ 9

      Tương tự a[i-1] giống a[i] , cho nên nó từ vị trí a[i] >= 2 * 10 ^ 9 thì các giá trị j <= i luôn có a[j] > = 2 * 10 ^ 9

      Và b[j] < = 10 ^ 9 , cho nên a[j] >= b[j].

      Vì vậy nếu a[i] >= 2 * 10 ^ 9 , thì ta không cần xét tiếp nữa

      Ngoài ra , có thể dùng unsigned int có thể chứa 4 * 10 ^ 9 thay vì long long cũng được

      Code :

      include <bits/stdc++.h>

      using namespace std;

      typedef long long ll;

      int main(){

      iosbase::syncwith_stdio(0);

      cin.tie(0);

      cout.tie(0);

      ll t; cin >> t;

      while(t--){

      ll n;

      cin >> n;

      vector<ll>a(n+1),b(n+1);

      for(ll i=1;i<=n;i++)

      cin >> a[i];

      for(ll i=1;i<=n;i++)

      cin >> b[i];

      for(ll i=1;i<n;i++){

      a[i+1]+=a[i]/2;

      a[i]=a[i]%2;

      }

      bool check=true;

      for(ll i=n;i>=1;i--){

      if(a[i] < b[i])

      check=false;

      if(a[i]>=2 * 1e9)

      break;

      a[i]-=b[i];

      a[i-1]+=a[i]*2;

      }

      if(check)

      cout << "YES\n";

      else

      cout << "NO\n";

      }

      return 0;

      }