Đổi ngọc

Đ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

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

7

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;

}