SPOJ: Xáo trộn thẻ

Question

Gần đây tôi đã bắt đầu giải các câu hỏi về thẩm phán trực tuyến. Tôi đang mắc kẹt trong this question in SPOJ:

Dưới đây là một thuật toán cho shuffling thẻ N:

1. Các thẻ được chia thành cọc bằng K, trong đó K là một yếu tố của N.
2. Đáy N/Thẻ K thuộc về cọc 1 theo cùng thứ tự (vì vậy thẻ đáy của cọc .initial là thẻ đáy của cọc 1).
3. Thẻ N/K tiếp theo từ dưới cùng thuộc về cọc 2, v.v.
4. Bây giờ thẻ trên cùng của cọc xáo trộn là thẻ hàng đầu của cọc 1. Thẻ tiếp theo là thẻ đầu của đống 2, ..., thẻ thứ K của cọc xáo trộn là thẻ đầu của đống K. Sau đó, (K + 1) th thẻ là thẻ mà bây giờ là ở trên cùng của đống 1, (K + 2) nd là thẻ mà bây giờ là ở trên cùng của đống 2 và như vậy.

Ví dụ, nếu N = 6 và K = 3, thứ tự của một cỗ bài "ABCDEF" (từ trên xuống dưới) khi xáo trộn một lần sẽ thay đổi thành "ECAFDB".

Cho N và K, số lượng shuffles tối thiểu cần thiết sau đó cọc được khôi phục theo thứ tự ban đầu là bao nhiêu?

---

Tôi đã thử mô phỏng nhưng vượt quá giới hạn thời gian. Có phương trình toán học nào không?

Answer 1

Có, có giải pháp toán học cho vấn đề này.

Trước tiên hãy để tôi bắt đầu với một số mẹo về cách tiếp cận vấn đề như vậy và sau đó tôi sẽ đưa ra một số mẹo về giải pháp thực tế. Tôi sẽ không hoàn thành nó để vẫn còn một số thách thức còn lại.

Vì vậy: cách tiếp cận các vấn đề như vậy? Những gì bạn đã làm thực sự là một khởi đầu tốt. Viết một mô phỏng và chạy nó chống lại một số trường hợp nhỏ. Mô phỏng nên khá nhanh ở đó. Bây giờ bạn có thêm một số giá trị. Viết chúng xuống trên một mảnh giấy và bắt đầu nhìn chằm chằm vào chúng. Bạn có fro dụ nếu K = x và N = y thì kết quả là z và nhiều cặp như vậy. Hãy thử tìm một số công thức. Tập trung vào bộ ba có giá trị cố định cho x, cho y hoặc cho z. Họ có đặc điểm gì chung? Và cứ thế. Bạn nhìn chằm chằm và thường bạn sẽ có một ý tưởng sáng sủa sau một thời gian :)

Bây giờ: một số mẹo về vấn đề cụ thể này. Thực hiện một lần lặp lại việc xáo trộn và ghi chú nơi mỗi thẻ đi. Ví dụ thẻ 1 đi vào vị trí 3 thẻ 3 đi vào vị trí 2 và như vậy. Lưu ý rằng một số chuỗi sẽ được hình thành theo cách này - ví dụ trong ví dụ n = 6, k = 3, chúng ta có một chuỗi có chiều dài 6: 1-> 3-> 2-> 6-> 4-> 5-> 1 . Bây giờ tính toán độ dài của tất cả các chuỗi (mỗi thẻ sẽ thuộc về một chuỗi chính xác) và cố gắng tìm câu trả lời phụ thuộc vào độ dài này như thế nào.

Hy vọng điều này là đủ để giúp bạn giải quyết vấn đề.

EDIT: xem xét các ràng buộc mô phỏng ngay cả một lần lặp lại có thể rất chậm. Nếu đó là trường hợp, sau khi bạn đã làm những gì tôi khuyên trong mẹo thứ hai của tôi hãy thử tính toán độ dài của chuỗi mà không thực sự phải mô phỏng một shuffle