Vòng loại tín hiệu Josephus

Bối cảnh

Trong một mạng thử nghiệm có n thiết bị được đánh số từ 1 đến n theo vòng tròn. Hệ thống bắt đầu tại thiết bị 1 và lặp lại quy tắc: đếm k thiết bị còn hoạt động (tính cả vị trí hiện tại), thiết bị thứ k bị loại; sau đó việc đếm tiếp tục từ thiết bị kế tiếp còn lại. Quá trình dừng khi chỉ còn một thiết bị. Nhiệm vụ là xác định số thứ tự của thiết bị sống sót.

Mô phỏng trực tiếp việc xóa phần tử trong vòng tròn thường đòi hỏi cấu trúc dữ liệu hoặc thao tác dịch mảng phức tạp, trong khi ở Module 04 bạn chưa học STL. Bài toán Josephus có một recurrence rất đẹp. Nếu gọi J(n,k) là vị trí sống sót 0-based trong vòng n phần tử, thì sau khi một phần tử bị loại, vòng còn n-1 phần tử có cùng cấu trúc nhưng hệ tọa độ bị xoay. Kết quả được ánh xạ ngược bằng công thức J(n,k) = (J(n-1,k) + k) % n, với base J(1,k)=0. Sau khi tính xong, cộng 1 để trở lại đánh số 1-based.

Đây là bài Advanced theo phong cách thi thuật toán: thử mô phỏng dễ sa vào chi tiết, còn nhận ra recurrence sẽ biến bài thành vài dòng recursion O(n).

Đây cũng là ví dụ điển hình cho việc "đổi hệ tọa độ" trong thuật toán. Sau khi phần tử thứ k bị loại, ta có thể tưởng tượng vòng tròn mới được đánh số lại từ 0 đến n-2 bắt đầu ngay sau vị trí bị loại. Bài toán nhỏ hơn được giải trong hệ mới; công thức modulo chỉ có nhiệm vụ đưa vị trí sống sót trở về hệ đánh số của vòng cũ. Nếu hiểu được phép đổi hệ này, recurrence sẽ trở nên tự nhiên thay vì là một công thức phải học thuộc.

Yêu cầu

1. Đọc n và k.
2. Dùng recurrence Josephus với chỉ số 0-based.
3. Base case J(1,k)=0.
4. Không mô phỏng xóa phần tử bằng STL.
5. In vị trí sống sót theo chỉ số 1-based.

Yêu cầu tổ chức code

Bắt buộc dùng recurrence recursion; không dùng vector/list.

Online Judge chấm output. Giảng viên có thể review source code để xác nhận học viên dùng đúng recursion và không vượt prerequisite.

Input

Một dòng gồm hai số nguyên dương n k.

Output

Một số nguyên từ 1 đến n.

Ràng buộc

1 ≤ n ≤ 5000, 1 ≤ k ≤ 10^9.

Ví dụ 1

Input

7 3

Output

4

Giải thích

Với n=7, k=3, recurrence tính từ bài toán nhỏ nhất: J(1)=0; J(2)=(0+3)%2=1; J(3)=(1+3)%3=1; tiếp tục lần lượt cho n=4..7 thu được vị trí 0-based cuối cùng là 3. Đổi về đánh số thiết bị 1-based bằng cách cộng 1, ta được thiết bị số 4, nên output là 4.

Ví dụ 2

Input

1 10

Output

1

Giải thích

Khi n=1, ngay từ đầu chỉ có một thiết bị nên không cần thực hiện vòng loại. Base case Josephus trả vị trí 0-based là 0; cộng 1 thành số thứ tự thiết bị 1. Giá trị k=10 không ảnh hưởng vì không có vòng loại nào diễn ra. Output là 1.

Thông tin học tập

• Module: M04
• Buổi: B14
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: recursion, Josephus recurrence, index transformation, modulo, recursion vs simulation insight
• Giới hạn kiến thức: B01-B14
• Time limit: 2 second(s)
• Memory limit: 256 MB
• Point: 100