Có một bài toán đặt ra như sau: "Cho N người đứng thành vòng tròn và số M (ở đây cho dễ ta sẽ giả sử M < N). Bắt đầu từ người số 1, anh ta sẽ đếm 1, người bên phải anh ta đếm 2, ... cho tới người đếm M sẽ tự động bước ra khỏi vòng tròn đó và người bên phải anh ta tiếp tục đếm lại 1 ... Cứ thế cho tới khi vòng không còn người nào. Câu hỏi đặt ra là ai là người ra khỏi vòng cuối cùng ?"
Bằng một ít suy nghĩ có lẽ ta sẽ tìm ra ngay các trả lời cho câu hỏi này. Chẳng hạn, bạn có thể "giả lập" trò chơi trên với một dãy số nguyên từ 1 đến N và số M, thực hiện bỏ từng số cho đến khi nào dãy chỉ còn một số và đó chính là kết quả. Như vậy bạn phải chạy N "vòng" (vì mỗi "vòng" bỏ một số) và mỗi "vòng" bạn phải đếm qua M người. Như vậy với cách giả lập trò chơi bạn mất M x N thao tác đếm.
Thực chất lí do mà mình viết bài này vì ... thực sự quá (?) sung sướng khi bắt gặp trên VNOI một cách giải mới có thể đưa số lần tính toán giảm xuống rất nhiều (MlogN). Ta thử ví dụ một trò chơi với N = 8 và M = 5 nhé:
Đầu tiên ta có:
1 2 3 4 5 6 7 8
Với những số không bị bỏ đi và nằm phía trước số bị bỏ, đem chúng cho vào phía sau (thì coi như trò chơi mới với dãy gồm N - 1 người)
6 7 8 9 10 11 12
Tiếp tục:
11 12 13 14 15 16
16 17 18 19 20
21 22 23 24 25
26 27 28 29 30
...
Bạn sẽ chú ý tới 3 dòng cuối cùng (và một số dòng ở dưới đó). Hãy suy nghĩ một chút sẽ biết tại sao lại làm như vậy. Chỉ là hợp thức hóa vấn đề phát sinh này thôi, không có gì quan trọng cả. Điều quan trọng ở đây là, trong dãy số mới, các số bị bỏ đi bao giờ cũng là k x M và số bị bỏ đi cuối cùng chính là M x N. Ta sẽ tìm hiểu số mang thứ tự M x N trong dãy mới kia sẽ tương ứng với người mang thứ tự bao nhiêu ở dãy 1..N ban đầu, và đó sẽ là kết quả.
Một nhận xét, các số M x k luôn bị bỏ đi,và M x k + r (0 < r < M) sau một lần chuyển sẽ chuyển lên vị trí N + (M - 1) x k + r. Cho phép mình giải thích cái công thức kia một chút. Tại sao số M x k + r sẽ trở thành số N + (M - 1) x k + r sau một phép "chuyển ra sau" ? Giả sử bạn đang xóa số M x k, thì đương nhiên phía trước đó nhất định phải còn lại M - 1 số (xem ví dụ), bạn chuyển M - 1 số đó ra sau (đương nhiên là sau số N), như vậy bạn bỏ qua bao nhiêu lần M thì cũng chuyển bấy nhiêu lần M - 1 ra sau, đó là lí do tại sao ta có cái công thức đấy.
Như vậy ta có vị trí cuối cùng là M x N và công thức chuyển vị trí (M x k + r) thành (N + (M - 1) x k + r), ta sẽ tìm cách chuyển về cho tới khi vị trí tính được nhỏ hơn N là xong.
Cách chuyển như thế nào ? Giả sử vị trí hiện tại là P, ta có:
Như vậy ta có vị trí cuối cùng là M x N và công thức chuyển vị trí (M x k + r) thành (N + (M - 1) x k + r), ta sẽ tìm cách chuyển về cho tới khi vị trí tính được nhỏ hơn N là xong.
Cách chuyển như thế nào ? Giả sử vị trí hiện tại là P, ta có:
P = N + (M - 1) x k + r
Do đó:
P - n - 1 = (M - 1) x k + (r - 1)
Suy ra:
k = [(P - n - 1) / (M - 1)] và P + k - N = M x k + r
Do đó vị trí trước sẽ là:
M x k + r = Ptrước = Psau + [(Psau - n - 1)/(M - 1)] - N
Tính vị trí trước như thế cho tới khi nào nó nhỏ hơn hoặc bằng N thì dừng. Đó chính là vị trí ban đầu của M x N.
Code của mình:
var
p, n, q, nn, m, mm: qword;
BEGIN
read(n, m); p := m * n; nn := n + 1; mm := m - 1;
while p > n do p := p + (p - nn) div mm - n;
write(p);
END.
p, n, q, nn, m, mm: qword;
BEGIN
read(n, m); p := m * n; nn := n + 1; mm := m - 1;
while p > n do p := p + (p - nn) div mm - n;
write(p);
END.
Một vài chú ý nhỏ:
+ Code trên là code mình đã tối ưu hết cỡ (tránh tính lại n + 1, m - 1)
+ Trong một biểu thức tính, nếu mà các hạng tử khác kiểu (longint và qword, ...), thì máy tính sẽ phải chuyển về cùng kiểu rồi mới tính, do đó chậm hơn để cùng kiểu luôn.
+ Mình viết bài này nhằm cung cấp tri thức và chia sẻ kinh nghiệm, không phải để chơi. Do đó, nếu bạn vào chỉ để copy code gửi lên máy chấm để lấy điểm thì các bạn hiểu, đó không phải là công sức của các bạn, các bạn không xứng đáng nhận lấy con điểm 100 đó. Thân ái.
