Cho một chữ số từ mỗi số nguyên liên tiếp K khôi phục dãy số

Question

Một loạt các số nguyên dương liên tiếp N liên tiếp bắt đầu từ X được ghi lại. Sau đó, chính xác một chữ số từ mỗi số được chọn và được viết theo cùng thứ tự. Chúng ta cần tìm số X nhỏ nhất mà chuỗi chữ số được thỏa mãn.

N và chuỗi chữ số được cung cấp làm đầu vào. Tôi đã cố gắng tìm một số hiểu biết toán học nhưng thất bại. N có thể lớn tới 10^5.

Nói cách khác, đã cho và mảng A có độ dài N chứa chữ số, chúng ta cần tìm một mảng B có độ dài N chứa số nguyên dương liên tiếp (B [i + 1] = B [i] + 1) số đó Một [i] có thể được tìm thấy trong số B [i] và B [0] là nhỏ nhất có thể. (Không có số nào trong B chứa số 0 đứng đầu).

Ví dụ: nếu được cho trước là 9, 2, 1, 2, 2 thì X nhỏ nhất là 19 (19, 20, 21, 22, 23).

Ví dụ khác: nếu đưa ra 9 8 9 1 0 thì trình tự như vậy sẽ là 97 98 99 100 101. Xem bạn có thể tìm thấy các chữ số đó trong chuỗi đã cho với số tương ứng trong chuỗi này. Và 97 là số khởi đầu nhỏ nhất có thể (1097 cũng đủ nhưng không phải là số nhỏ nhất).

Bất kỳ gợi ý nào về cách tiếp cận vấn đề này và loại vấn đề này sẽ hữu ích.

Answer 1

Dưới đây là một thuật toán O(N^2), có thể hoặc không đủ tốt, vì bạn không liên kết vấn đề ban đầu, do đó yêu cầu chi tiết không xác định.

Tôi giả sử N = 100000 trong phần sau.

For every y in [0, 100000): 
    Consider the case that B[0] = 100000 * x + y for some x. 
    This will be equivalent to requiring that x contains some of the digits in [0, 10), 
    and that x + 1 contains some of the digits in [0, 10), 
    from which a smallest x can easily be found (or pre-computed). 
    (But the special case x = 0 needs further attention, problem of leading zero.) 
Find the maximun of all 100000 * x + y found above, which is the answer. 

Có tối ưu hóa thêm, với ý tưởng tương tự (ví dụ: thay vì xem năm chữ số cuối, người ta có thể xem ba số cuối, v.v.). Nhưng tôi sẽ không đăng các chi tiết này ngay bây giờ.

Answer 2

Đây là cách bạn muốn tự giải quyết ví dụ đầu tiên:

Ví dụ: 9, 2, 1, 2, 2

→ Những con số có 5 chữ số trở xuống.

9, 2

9 và 2 là khác nhau, và không liên tiếp → họ đang ở vị trí khác nhau:

9****, *2*** 

9, 2, 1

1 có thể theo sau 9, nhưng chỉ khi chúng ở vị trí thấp nhất (un của nó):

****9, 2***0, 2***1 
9****, *2***, **1** 

9, 2, 1, 2

2 có thể làm theo 9 và/hoặc 1, nhưng chỉ ở vị trí thấp nhất (đơn vị); nó cũng có thể là ở vị trí tương tự như trước đó 2, nhưng không phải ở vị trí thấp nhất:

****9, 2***0, ****1, ****2 
****9, 2***0, ****1, 2***2 
****9, 2***0, ****1, *2**2 
****9, 2****, *1***, ****2 
9****, *2***, ****1, ****2 
9****, *2***, **1**, *2*** 
9****, *2***, **1**, ***2* 

9, 2, 1, 2, 2

2 có thể là trong cùng một vị trí như một hoặc cả hai của 2 nhân trước đó, nhưng không phải ở vị trí thấp nhất (đơn vị):

****9, 2***0, ****1, ****2, 2***3 min. 2 digits 19, 20, 21, 22, 23 
****9, 2***0, ****1, ****2, *2**3 min. 3 digits 
****9, 2***0, ****1, 2***2, 2***3 min. 2 digits 19, 20, 21, 22, 23 
****9, 2***0, ****1, 2***2, *2**3 min. 3 digits 
****9, 2***0, ****1, *2**2, 2***3 min. 3 digits 
****9, 2***0, ****1, *2***, **2*3 min. 4 digits 
****9, 2***0, *1**1, ****2, 2***3 min. 3 digits 
****9, 2***0, *1**1, ****2, **2*3 min. 4 digits 
9****, *2***, ****1, ****2, *2**3 min. 3 digits 
9****, *2***, ****1, ****2, **2*3 min. 4 digits 
9****, *2***, **1**, *2***, *2*** min. 3 digits 
9****, *2***, **1**, *2***, ***2* min. 4 digits 
9****, *2***, **1**, ***2*, *2*** min. 4 digits 
9****, *2***, **1**, ***2*, ****2 min. 5 digits 

---

Chìa khóa để hạn chế số lượng khả năng cố gắng là tất nhiên để theo dõi đầy hứa hẹn nhất (tức là số thấp nhất của chữ số) đường dẫn đầu tiên, như chúng ta sẽ làm cho ví dụ thứ hai:

Ví dụ: 9, 8, 9, 1, 0

→ Những con số có 5 chữ số trở xuống.

9, 8

8 chỉ có thể là ở một vị trí khác nhau từ 9:

9****, *8*** min. 2 digits 

9, 8, 9

9 có thể ở vị trí tương tự (không thấp nhất) là 9, hoặc cùng vị trí (thấp nhất) là 8:

9****, 98***, 9**** min. 2 digits 
9***7, ****8, ****9 min. 2 digits 

9, 8, 9, 1

1 không thể ở vị trí giống như bất kỳ các chữ số khác:

9****, 98***, 9****, **1** min. 3 digits 
9***7, ****8, ****9, *1**0 min. 3 digits 

9, 8, 9 , 1, 0

0 có thể đến sau một hoặc cả hai 9, nhưng không ở vị trí thấp nhất:

9****, 98***, 9****, **1**, 0**** min. 3 digits 97, 98, 99, 100, 101 
9***7, ****8, ****9, *1**0, 0***1 min. 3 digits 97, 98, 99, 100, 101 

---

Vì vậy, một thuật toán có thể sẽ là:

• Đối với mỗi chữ số mới, kiểm tra xem nó có thể làm theo bất kỳ các chữ số trước, và trong đó các vị trí (1 → 2 có thể xảy ra ở mọi vị trí, nhưng 1 3 hoặc 1 → x → x → 4 chỉ ở vị trí thấp nhất; 1 → 1 có thể xảy ra ở bất kỳ vị trí nào nhưng vị trí thấp nhất).
• Kiểm tra các đường dẫn hứa hẹn nhất trước tiên, ví dụ: nếu một chữ số mới có thể ở cùng vị trí với chữ số trước đó.
• Nếu chữ số mới không thể theo bất kỳ chữ số nào trước đó, thì chỉ xem xét vị trí bổ sung (tức là số chữ số tối thiểu trong giải pháp tăng).
• Nếu bạn chỉ tìm thấy các giải pháp lớn, quay lại và chọn một con đường có vẻ ít hứa hẹn hơn vào thời điểm đó.

Tôi không chắc chắn làm thế nào bạn có thể biết rằng giải pháp nhỏ nhất đã được tìm thấy khi bạn bắt đầu quay lại. Nếu bạn tìm thấy giải pháp có số n, thì có thể bạn nên kiểm tra tất cả các giải pháp có số n để chắc chắn.