Paper Boat

View as PDF
Submit solution
Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

After a long day hanging out with her crab fans, Saba is getting ready to return to the lighthouse on a small paper boat, sailing across the sea. Wanting to see Saba one last time before nightfall, the crabs decide to line up along her sailing route to say goodbye. Since the number of Saba's fans has already surpassed a million, the crabs need to spread out enough so that Saba can sail home safely.

The sailing route is modeled as a grid with ~k~ rows and ~2^{60}~ columns. The rows are numbered from ~0~ to ~k - 1~ from top to bottom, and the columns are numbered from ~0~ to ~2^{60} - 1~, starting from the shore. The shore lies before column ~0~, and Saba's house is just beyond column ~2^{60} - 1~. With this in mind, the crabs have coordinated the following plan:

  • Two numbers ~l~ and ~r~ are chosen, such that ~0 \le l \le r < 2^{60}~;

  • For each column ~i~ from ~l~ to ~r~, a crab will stand at the ~j~-th row if and only if the ~j~-th right-most bit of ~i~ is ~0~ (that is, ~\left\lfloor \frac{i}{2^j} \right\rfloor~ is even);

  • No crabs will stand in any other cells of the grid.

Saba must navigate through her fans to reach home as follows.

  • Starting from the shore, Saba can choose one of the empty cells in the ~0~-th column to place her boat.

  • Saba can reach home if she manages to move to an empty cell in the ~(2^{60} - 1)~-th column.

  • The boat can move from one cell to another if they share a side.

  • The boat cannot leave the grid.

  • And because it is extremely fragile, the boat will break if it ends up in the same cell as one of her fans.

image

Illustration for the first test case: ~l = 10~, ~r = 14~, ~k = 4~. Saba can return home safely.

Seeing how devoted her fans are, Saba is moved! However, she's famously bad at math, so she isn't sure whether she can make it home safely. Help Saba determine if there is a safe path home, given the crabs' arrangement.

Input

The first line contains a positive integer ~t~ (~1 \leq t \leq 10\,000~) – the number of test cases.

The first and only line of each test case contains 3 numbers ~l~, ~r~, ~k~ (~0 \leq l \leq r < 2^{60}~, ~1 \leq k \leq 60~) – the range of the columns that the crabs will stand on, and the number of rows.

Output

For each test, print a line containing ~\mathtt{YES}~ if there exists a path for Saba to safely reach home, or ~\mathtt{NO}~ otherwise.

Scoring

The total score for this problem is ~500~.

Sample Input 1

6
10 14 4
52 54 7
100 200 60
999999999999999999 1000000000000000000 1
6 6 1
15 29 3

Sample Output 1

YES
YES
NO
NO
NO
NO

Notes

The first test case has been explained through the illustration in the problem statement.

In the second test case: ~l = 52~, ~r = 54~, ~k = 7~. Below is an illustration of the positions of the crabs and how Saba moves through:

image

In the remaining test cases, all paths home must pass through at least one crab, so there is no way for Saba to move home safely.

Comments

Please read the guidelines before commenting.


  • 2
    vominhmanh10  commented on Oct. 15, 2025, 1:36 p.m. ← edit 8

    mò ra được công thức do mô phỏng bằng nháp nhưng không biết giải thích sao, nhưng đến một giá trị nào đó cua sẽ cản hoàn toàn một đoạn, ví dụ cột 32 thì bị chắn 5 hàng đầu, cột 64 bị chắn 6 hàng đầu cột 2^n bị chắn n hàng, ta dùng công thức với mỗi hàng để xác định có ra được không và ra kết quả. Cụ thể tại hàng j(0 <= j < k):
    l // (1 << j) % 2 == 0 bị chắn đúng j hàng nên không qua hàng j được bỏ qua
    nếu không thì l + (1 << j) - l % (1 << j) - 1 sẽ xét nếu có thể đi qua r tại j + 1 được lập tức in "YES", ngược lại duyệt hết mà ko có là "NO"

    import sys
data = sys.stdin.readlines()
t = int(data[0])

for i in range(1, t + 1):
    l, r, k = map(int, data[i].split())
    for j in range(k):
        if (l // (1 << j)) % 2 == 0:
            continue

        ans = l + (1 << j) - l % (1 << j) - 1
        if ans >= r:
            print('YES')
            break
    else:
        print('NO')

  • 0
    quannguv  commented on Oct. 14, 2025, 12:28 a.m.

    bài này theo mình thì khá khó cho người mới


  • -22
    sb_anhtuan  commented on Oct. 7, 2025, 3:28 a.m.

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