ThangA3
23-12-2011, 10:13
Đếm người strên vòng tròn
Josephus
Trong một cuộc chơi, có n người tham gia. n người đứng trên 1 vòng tròn , mỗi người mang 1 số hiệu từ 1 đến n. Việc đếm bắt đầu từ người thứ nhất, qua người thứ 2,.. thứ 3..đến thứ k, thì người thứ k bước ra khỏi vòng tròn. Và lại bắt đầu đếm lại từ người thư nhất. Trò chơi kết thúc khi trên vòng tròn chỉ còn lại 1 người. đây là người thắng cuộc.
Yêu Cầu
cho trước n, k. Xác định người thắng cuộc.
Giới hạn
n<= 100 000
k<= 2000 000 ( đếm nhiều hơn 1 vòng)
time limit 1s/test
INPUT 2 số n,k
OUTPUT số hiệu ban đầu của người thắng cuộc
vd
input
100000
123456
output
12243
Josephus
Trong một cuộc chơi, có n người tham gia. n người đứng trên 1 vòng tròn , mỗi người mang 1 số hiệu từ 1 đến n. Việc đếm bắt đầu từ người thứ nhất, qua người thứ 2,.. thứ 3..đến thứ k, thì người thứ k bước ra khỏi vòng tròn. Và lại bắt đầu đếm lại từ người thư nhất. Trò chơi kết thúc khi trên vòng tròn chỉ còn lại 1 người. đây là người thắng cuộc.
Yêu Cầu
cho trước n, k. Xác định người thắng cuộc.
Giới hạn
n<= 100 000
k<= 2000 000 ( đếm nhiều hơn 1 vòng)
time limit 1s/test
INPUT 2 số n,k
OUTPUT số hiệu ban đầu của người thắng cuộc
vd
input
100000
123456
output
12243