Trò Chơi Josephus - LQDOJ: Le Quy Don Online Judge

• 
• Trang chủ
• Giới thiệu Máy chấm Đề xuất ý tưởng Đề xuất bài tập Đề xuất kỳ thi Công cụ Báo cáo tiêu cực Báo cáo lỗi Quiz

Tiếng Việt

Tiếng Việt English

Đăng nhập

Đăng ký

Trò chơi Josephus

Xem PDF Nộp bài Tất cả bài nộp Các bài nộp tốt nhất Tác giả: PhanDinhKhoi Dạng bài greedy (tham lam), math (toán học), divide and conquer (chia để trị), recursion (đệ quy) Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 640M Input: bàn phím Output: màn hình

Trò chơi Josephus được thể hiện như sau:

• \(n\) người (được đánh số từ \(1\) đến \(n\)) được xếp lần lượt trên vòng tròn.
• Trong quá trình trò chơi diễn ra, "người thứ hai" sẽ lần lượt bị đưa ra khỏi vòng tròn cho đến khi chỉ còn một người.

\(q\) câu hỏi: Bạn được cho trước số nguyên dương \(n\), tìm số thứ tự của người cuối cùng.

Minh họa

• \(n=5\)

• \(n=6\)

• \(n=7\)

• \(n=13\)

Input

• Dòng đầu chứa 2 số nguyên dương \(q\) - là số câu hỏi.
• \(q\) dòng tiếp theo mỗi dòng chứa hai số nguyên dương \(n\).

Output

• \(q\) dòng, mỗi dòng chứa số thứ tự của người cuối cùng.

Constants

• \(1 \leq q \leq 10\) và \(1 \leq n \leq 10^9\)

Example

Test 1

Input 4 5 6 7 13 Output 3 5 7 11

Bình luận (21)

Gần nhất Gần nhất Xa nhất Điểm Tải bình luận...