Exchange Gems

View as PDF

Submit solution


Points: 0.10 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

You are playing the most popular MMO game at the moment. The in-game currency is gems, divided into ~n~ levels. Currently, you have ~a_i~ gems at level ~i~. To buy the most expensive equipment in the game, you need to pay ~b_i~ gems at level ~i~.

The game has a gem exchange system that allows you to:

  • Exchange ~2~ gems at level ~i~ for ~1~ gem at level ~i+1~ (with ~1 \le i < n~).

  • Exchange ~1~ gem at level ~i~ for ~2~ gems at level ~i-1~ (with ~1 < i \le n~).

Determine if there is any way to exchange gems to have enough gems at each level to buy the equipment using zero or many exchanges.

Input

The input consists of multiple test cases. The first line of the input contains a positive integer ~t~ (~1 \le t \le 10\,000~) which is the number of test cases. The description of each test case is as follows.

The first line contains an integer ~n~ (~1 \le n \le 2 \cdot 10^5~) — the number of gem levels.

The second line contains ~n~ integers ~a_1, a_2, \ldots, a_n~ (~0 \le a_i \le 10^9~) — the number of gems you have at each level.

The third line contains ~n~ integers ~b_1, b_2, \ldots, b_n~ (~0 \le b_i \le 10^9~) — the number of gems required at each level.

The sum of ~n~ in all test cases is guaranteed not to exceed ~2 \cdot 10^5~.

Output

For each test case, print "YES" if there is a way to exchange gems to have enough gems at each level, or "NO" otherwise.

Scoring

Subtask Score Constraints
1 ~500~ ~n \le 20~
2 ~500~ No additional constraints
Total ~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

In the first test case, you can:

  • Exchange ~1~ gem at level ~2~ for ~2~ gems at level ~1~. The number of gems you have at each level becomes ~[3, 0, 4, 5]~.

  • Exchange ~1~ gem at level ~3~ for ~2~ gems at level ~2~. The number of gems you have at each level becomes ~[3, 2, 3, 5]~.

Now, you have enough gems at each level.

In the second test case, you only have ~1~ gem at level ~1~, so you cannot perform any gem exchange. Therefore, you cannot have enough gems at level ~2~ as required.

In the third test case, you already have enough gems at each level from the beginning.

In the fourth test case, the system has only ~1~ gem level, so you cannot perform any gem exchange, and you also do not have enough gems at level ~1~ as required.


Comments

Please read the guidelines before commenting.



  • 4
    khai05  commented on June 5, 2024, 8:36 p.m. edited

    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  commented on June 3, 2024, 7:17 a.m.

    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


    • 7
      anle82917  commented on June 4, 2024, 11:43 a.m. edit 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;

      }