Phân tích

Làm thế nào để biết một số không hạnh phúc? Bạn có thể biết nếu nó rơi vào một chu kỳ khi áp dụng quy trình được mô tả trong đề bài. Dưới đây là một ví dụ trong hệ cơ số 10:

42 → 20 → 4 → 16 → 37 → 58 → 89 → 145 → 42 repeated

Ở đây, \(x \to y\) biểu thị \(y\) là số tiếp theo nếu chúng ta áp dụng quy trình lên \(x\). Bắt đầu từ bất kỳ số nào, nếu bạn áp dụng quy trình, cuối cùng bạn sẽ đạt đến 1 hoặc rơi vào một trong những chu kỳ đó.

Nhưng điều đó có thực sự đúng không? Một người đọc cẩn thận có thể hỏi: Liệu quy trình có thể tiếp tục tạo ra các số mới mãi mãi mà không bao giờ rơi vào chu kỳ? Hãy nhìn vào chu kỳ của 42: Trước khi bạn gặp lại 42, các con số nhảy xung quanh mà không có quy luật rõ ràng.

Hóa ra điều này không bao giờ có thể xảy ra: chỉ có hữu hạn các chu kỳ như vậy và chúng đều có độ dài hữu hạn. Thực tế, trong hệ cơ số 10, đây là chu kỳ duy nhất! Tất cả các số tham gia vào một chu kỳ như vậy phải tương đối nhỏ. Thật vậy, khi bạn bắt đầu với một số lớn (ví dụ 99999..9999), việc áp dụng quy trình sẽ dẫn đến các số nhỏ dần đi rất nhanh. Người ta có thể dễ dàng chứng minh rằng, trong bất kỳ hệ cơ số \(B\) nào, có một ngưỡng \(H\) cỡ \(O(B^3)\) sao cho bất kỳ số nào lớn hơn \(H\) sẽ có số kế tiếp nhỏ hơn nó.

Một câu hỏi khác là: Với một tập hợp các hệ cơ số, liệu có tồn tại một số hạnh phúc trong tất cả chúng không? Chúng tôi không biết câu trả lời cho câu hỏi đó một cách tổng quát, nhưng dựa trên tính toán, chúng tôi biết những số như vậy tồn tại cho tất cả các hệ cơ số lên đến 10. Mặt khác, nếu bạn cảm nhận rằng tính chất một số là hạnh phúc bằng cách nào đó là ngẫu nhiên và bằng cách nào đó độc lập giữa các hệ cơ số khác nhau, thì bạn có thể tin rằng hạnh phúc đa cơ số là hiếm, và mật độ của các số như vậy giảm theo hàm mũ với số lượng hệ cơ số. Trong bài toán của chúng ta, số hạnh phúc nhỏ nhất cho đầu vào (2, 3, 4, 5, 6, 7, 8, 9, 10) là 11814485; con số này vừa đủ để tìm kiếm bằng vét cạn.

Cách cài đặt

Trong quá trình tính toán, một mẹo hiển nhiên là lưu bộ nhớ đệm (cache) cho cặp \((x, B)\), xem \(x\) có hạnh phúc trong hệ cơ số \(B\) hay không, để chúng ta tránh việc phải đi theo chuỗi nhảy hoặc các chu kỳ mỗi lần. Chúng ta chỉ cần làm điều này cho các giá trị nhỏ của \(x\) -- ví dụ tất cả \(x \le 1000\) là quá đủ -- vì bất kỳ số nguyên 32-bit nào lớn hơn 10000 đều trở nên nhỏ hơn 1000 chỉ sau một bước.

Vì hệ cơ số tối đa là 10, người ta có thể nhận ra rằng chỉ có \(2^9 - 10 = 502\) đầu vào phân biệt có thể có. Vậy tại sao chúng ta không tính toán trước tất cả chúng? Điều này thực tế có thể nhanh hơn việc giải từng bộ test một, nếu chúng ta giải các tập hợp nhỏ trước. Đối với một tập hợp \(S\) các hệ cơ số, chúng ta không cần bắt đầu tìm kiếm từ 2; chúng ta có thể bắt đầu từ đáp án của bất kỳ tập con \(S' \subset S\) nào, vì một số hạnh phúc trong tất cả các hệ cơ số từ \(S\) thì ít nhất cũng phải hạnh phúc trong tất cả các hệ cơ số từ \(S'\).

Nếu bạn thấy cài đặt của mình vẫn chưa đủ nhanh, hãy chạy chương trình của bạn trong khi đang giải các bài tập khác. Chỉ có 502 trường hợp đầu vào có thể xảy ra. Giải tất cả chúng, tạo danh sách các câu trả lời, và sau đó bắt đầu quá trình nộp bài; chỉ cần đừng quên bạn cũng cần nộp cả chương trình (dù chậm) đã tạo ra danh sách đó. Đây là lý do tại sao chúng tôi có một ghi chú đặc biệt ở cuối đề bài.

Độ phức tạp

Độ phức tạp phụ thuộc vào số lượng hệ cơ số và giá trị của số hạnh phúc nhỏ nhất tìm được. Việc sử dụng cache và tính toán trước giúp giảm đáng kể thời gian thực thi, đưa bài toán về mức có thể giải quyết được trong giới hạn thời gian.

Thông tin thêm

Bài viết Wikipedia: Happy Numbers

Dựa trên phân tích chính thức của Google Code Jam.