Trò chơi Josephus
Xem PDF
Đ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
13Output
3
5
7
11
Bình luận
tội mấy thằng lính ở vị trí chẵn ghê :-((
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
bài này mình không xem test dc ạ?
Bạn Long kb với mình đi bạn
Mình chưa thấy
kb voi mk di
cai nay em bieets roofi aj
viết thử các th từ 1->8 ta sẽ thấy nếu n=2^k thì người 1 luôn thắng, nếu n+1 thì người thứ 1+2,... => ct tổng quát sẽ là 2*(n-2^k)+1 trong đó k là số mũ lớn nhất để 2^k<=n