Truy vấn Josephus

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $n$ đứa trẻ đứng thành vòng tròn, đánh số từ $1$ đến $n$ theo chiều kim đồng hồ. Chúng chơi trò loại dần: bắt đầu từ đứa số $1$ , cứ mỗi đứa thứ hai sẽ bị loại — tức là đứa số $2$ bị loại đầu tiên, rồi đứa số $4$ , rồi $6$ , và cứ tiếp tục theo vòng tròn cho đến khi tất cả đều bị loại.

Với mỗi truy vấn gồm $n$ và $k$ , hãy cho biết đứa trẻ nào bị loại ở vị trí thứ $k$ .

Dữ liệu vào

Dòng đầu: số nguyên $q$ — số truy vấn.
$q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $n$ và $k$ .

Dữ liệu ra

In $q$ số nguyên, mỗi số trên một dòng — đứa trẻ bị loại ở vị trí thứ $k$ trong vòng tròn $n$ người.

Ràng buộc

$1 \leq q \leq 10^{5}$
$1 \leq k \leq n \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 7 1 7 3 2 2 1337 1313	2 6 1 1107	Với $n = 7$ : lần lượt bị loại là $2, 4, 6, 1, 5, 3, 7$ . Vị trí $1$ là $2$ , vị trí $3$ là $6$ . Với $n = 2$ : loại $2$ trước, rồi $1$ , nên vị trí $2$ là $1$ .

Bình luận

Không có bình luận tại thời điểm này.