Bài toán Josephus

Xem dạng PDF

Gửi bài giải

Điểm: 100,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C++, Python
Bài toán Josephus
Mô tả và yêu cầu

Có N người ngồi thành vòng tròn, đánh số từ 1 đến N . Bắt đầu từ người số 1,
ta đếm theo kim đồng hồ đến K; người đang được đếm thứ K sẽ bị loại khỏi vòng
và vòng tiếp tục từ người ngay sau người bị loại. Quá trình lặp lại cho đến khi chỉ
còn một người. Hỏi chỉ số người còn lại cuối cùng (theo đánh số ban đầu) là bao
nhiêu?
Yêu cầu: Tìm số (chỉ số) người còn sống cuối cùng sau khi thực hiện quá trình
loại theo quy tắc trên.

Dữ liệu vào

Một dòng chứa hai số nguyên dương N và K (cách nhau bởi dấu cách).

Dữ liệu ra

In ra một số nguyên — chỉ số (theo đánh số từ 1) của người còn lại cuối cùng.
Nếu đề yêu cầu thêm, có thể in thêm thứ tự các người bị loại (từ người bị loại trước
đến sau).

Ví dụ
INPUT                       OUTPUT                            Giải thích
 7 3                              4                          Loại theo thứ tự: 3, 6, 2, 7, 5, 1
                                                             → người số 4 là người còn lại

Tải PDF gốc


Bình luận

Hãy đọc nội quy trước khi bình luận.


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