CSES - Josephus Queries | Truy vấn Josephus

Xem PDF

Điểm: 1500 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Trong một trò chơi có \(n\) đứa trẻ (đánh số \(1,2,…, n\)) trong một vòng tròn. Trong trò chơi, cứ mỗi hai đứa trẻ thì đứa trẻ sau sẽ bị loại khỏi vòng tròn, cho đến khi không còn đứa trẻ nào.
Nhiệm vụ của bạn là xử lý \(q\) truy vấn có dạng: "Khi có \(n\) đứa trẻ thì đứa trẻ thứ \(k\) sẽ bị loại bỏ là ai?"

Input

  • Dòng đầu tiên là \(q\): số lượng truy vấn.
  • \(q\) dòng, mỗi dòng chứa 2 số \(n\)\(k\): số đứa trẻ và thứ tự bị loại bỏ của đứa trẻ.

Output

  • \(q\) dòng: đáp án của mỗi truy vấn.

Constraints

  • \(1 \leq q \leq 10^5\)
  • \(1 \leq k \leq n \leq 10^9\)

Example

Sample input

4
7 1
7 3
2 2
1337 1313

Sample output

2
6
1
1107


Bình luận


  • 0
    N7hoatt 8:34 a.m. 30 Tháng 8, 2023

    Một trò chơi gồm \(n\) đứa trẻ (được đánh số từ \(1,2,3,\dots,n\)) đứng thành vòng tròn. Trong trò chơi, cứ mỗi hai đứa trẻ thì đứa trẻ thứ hai sẽ bị loại cho đến khi không còn đứa trẻ nào.

    Hãy thực hiện \(q\) truy vấn có dạng: "Với \(n\) đứa trẻ thì đứa trẻ thứ \(k\) bị loại là ai?"

    Input

    • Dòng đầu tiên gồm chứa một số nguyên \(q\): số lượng truy vấn.
    • \(q\) dòng tiếp theo biểu diễn các truy vấn. Mỗi dòng gồm hai số nguyên \(n\)\(k\): số lượng đứa trẻ và thứ tự đứa trẻ bị loại.

    Output

    • In \(q\) số nguyên: đáp án của mỗi truy vấn.

    Constraints

    • \(1 \leq q \leq 10^5\).
    • \(1 \leq k \leq n \leq 10^9\).

    Example

    Test

    Input
    4
    7 1
    7 3
    2 2
    1337 1313
    Output
    2
    6
    1
    1107
    Note

    • 1
      mondellbit09 2:23 p.m. 7 Tháng 11, 2022

      512k thấy hẹo wá (vì thấy ở cses họ cho 512mb)