nqson xào bài 3
Submit solution
Points:
3 (partial)
Time limit:
1.0s
Memory limit:
977M
Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG
nqson có 1 bộ bài có n lá bài. Mỗi lá bài của bộ bài đó dược đánh 1 con số làn lượt từ 1 đến n. Mỗi lượt nqson sẽ thực hiện 2 việc sau:
- bốc một lá ở dưới đáy bộ bài và bỏ lên đầu
- bốc một lá ở dưới đáy bộ bài và bỏ lá đó ra khỏi bộ bài
Hãy cho biết lá bài cuối cùng nqson bỏ ra khỏi bộ bài.
Ví dụ: nqson có các lá \(1, 2, 3, 4\):
Bước 1: nqson bốc lá bài dưới đáy bỏ lên đầu, bộ bài trở thành 2, 3, 4, 1.
Sau đó bỏ lá 2 dưới đáy, bộ bài trở thành 3, 4, 1
Bước 2: nqson bốc lá bài dưới đáy bỏ lên đầu, bộ bài trở thành 4, 1, 3.
Sau đó bỏ lá 4 dưới đáy, bộ bài trở thành 1, 3
Bước 3: nqson bốc lá bài dưới đáy bỏ lên đầu, bộ bài trở thành 3, 1.
Sau đó bỏ lá 3 dưới đáy, bộ bài trở thành 1
Bước 4: nqson bốc lá bài dưới đáy bỏ lên đầu, bộ bài trở thành 1.
Sau đó bỏ lá 1 dưới đáy, không còn lá nào trong bộ bài\(\to\) lá bài cuối cùng nqson rút ra khỏi bộ bài là \(1\).
Đầu vào
Dòng đầu tiên chứa một số tự nhiên \(n\).
Đầu ra
In ra lá bài cuối cùng mà nqson bỏ ra khỏi bộ bài
Giới hạn
\(1 \le n \le 10^{18}\)
Ví dụ 1
Đầu vào:
4Đầu ra:
1
Comments
Josephus problem numberphile
Các bạn có thể xem hướng dẫn giải (Read editorial trong tiếng anh) cho bài này.
:),update