Trò chơi Josephus
View as PDF
Points:
1600 (p)
Time limit:
1.0s
Memory limit:
640M
Input:
stdin
Output:
stdout
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
Comments
tội mấy thằng lính ở vị trí chẵn ghê :-((
This comment is hidden due to too much negative feedback. Click here to view it.
This comment is hidden due to too much negative feedback. Click here to view it.
This comment is hidden due to too much negative feedback. Click here to view it.
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