Exchange Gems
View as PDFYou 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
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
Bài này mình có cách giải không cần dùng số nguyên lớn nè. !!!!!!!!!!!!!!!!!!!!!!!!!!!!SPOILER :