Nhà bạn An có một két bạc có khóa và mở bằng dãy số; két có ba phím 1, 2, 3. Bạn An đã đặt mật khẩu để mở két là một dãy có 3 chữ số, mỗi chữ số thuộc tập {1, 2, 3}. Nhưng do đã lâu không sử dụng két nên bạn ấy đã quên mất mật khẩu để mở.
Bạn hãy giúp bạn An tìm ra dãy số có độ dài ngắn nhất để bạn An ấn theo dãy số đó thì chắc chắn mở được két bạc. Biết rằng nếu ba chữ số được ấn gần nhất trùng với mật khẩu thì két bạc sẽ kêu tiếng tit và khi đó An có thể mở két.
giai duoc cau nay cho100k
Đặt tên các bộ ba lần lượt là A, B, ... như sau:
111 (A), 112 (B), 113 (C), 121 (D), 122 (E), 123 (F), 131 (G), 132 (H), 133 (I), 211 (J), 212 (K), 213 (L), 221 (M), 222 (N), 223 (O), 231 (P), 232 (Q), 233 (R), 311 (S), 312 (T), 313 (U), 321 (V), 322 (X), 323 (Y), 331 (Z), 332 (W), 333 (@)
Ta cần tìm dãy ngắn nhất chứa tất cả 27 bộ ba trên. Để tìm được dãy như vậy, ta sắp xếp lại các bộ ba trên sao cho hai chữ số cuối của bộ ba trước trùng với hai chữ số đầu của bộ ba sau. Một ví dụ là:
111 (A) , 112 (B), 121 (D), 211 (J), 113 (C), 131 (G), 312 (T), 122 (E), 221 (M), 212 (K), 123 (F), 231 (P), 313 (U), 132 (H), 321 (V), 213 (L), 133 (I), 332 (W), 322 (X), 222 (N), 223 (O), 232 (Q), 323 (Y), 233 (R), 333 (@), 331 (Z), 311 (S)
Sau đó loại bỏ 2 chữ số trùng nhau của các bộ ba kề nhau:
111, 112, 121, 211, 113, 131, 312, 122, 221, 212, 123, 231, 313, 132, 321, 213, 133, 332, 322, 222, 223, 232, 323, 233, 333, 331, 311
Cuối cùng ta được dãy 29 chữ số sau chứa tất cả các bộ ba có thể có của mật khẩu ba chữ số:
11121131221231321332223233311