Modest Substrings
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
You are given two integers $l$ and $r$.
Let's call an integer $x$ modest, if $l \le x \le r$.
Find a string of length $n$, consisting of digits, which has the largest possible number of substrings, which make a modest integer. Substring having leading zeros are not counted. If there are many answers, find lexicographically smallest one.
If some number occurs multiple times as a substring, then in the counting of the number of modest substrings it is counted multiple times as well.
The first line contains one integer $l$ ($1 \le l \le 10^{800}$).
The second line contains one integer $r$ ($l \le r \le 10^{800}$).
The third line contains one integer $n$ ($1 \le n \le 2\,000$).
In the first line, print the maximum possible number of modest substrings.
In the second line, print a string of length $n$ having exactly that number of modest substrings.
If there are multiple such strings, print the lexicographically smallest of them.
Input
The first line contains one integer $l$ ($1 \le l \le 10^{800}$).
The second line contains one integer $r$ ($l \le r \le 10^{800}$).
The third line contains one integer $n$ ($1 \le n \le 2\,000$).
Output
In the first line, print the maximum possible number of modest substrings.
In the second line, print a string of length $n$ having exactly that number of modest substrings.
If there are multiple such strings, print the lexicographically smallest of them.
1
10
3
1
11
3
12345
12346
6
3
101
5
111
1
012345
Note
In the first example, string «101» has modest substrings «1», «10», «1».
In the second example, string «111» has modest substrings «1» ($3$ times) and «11» ($2$ times).
动态规划选讲（一）
- Status
- Done
- Rule
- IOI
- Problem
- 5
- Start at
- 2023-10-28 7:30
- End at
- 2023-10-28 17:30
- Duration
- 10 hour(s)
- Host
-
梁泽贤 (liangzexian)
- Partic.
- 12