Problem H
Talnalás
Languages
en
is
Anna is now heading home and has to open the combination lock. She does this by rotating the disks, each one step at a time, such that the selected digits end up being a specific passcode. But Anna is very superstitious and has $m$ lucky numbers. After each step she wants to make sure the currently selected number is a lucky number, because otherwise it brings bad luck.
Given the currently selected digits, the passcode for the lock and the list of Anna’s lucky numbers, help her find in what order she should rotate the disks to open the lock, making sure that the digits displayed are always a lucky number after each step. Since Anna is in a rush, she wants to do this in the minimum number of steps possible.
Input
The first line of the input contains two integers $n$ and $m$ ($1 \leq n, m$), the number of disks on the lock and the number of lucky numbers. The second line of the input contains an $n$-digit number, where the $i$-th digit denotes the currently selected digit on the $i$-th disk of the combination lock. The third line of the input contains an $n$-digit number where the $i$-th digit is the digit that needs to be selected on the $i$-th disk to open the lock. Finally there are $m$ lines, each with an $n$-digit number which are Anna’s lucky numbers. The initial state and the passcode are both guaranteed to be lucky numbers.
You can assume that the initial state and the passcode are different.
Output
Print a single line containing the integer $k$, the minimum number of steps Anna needs to open the lock given the constraints above. Then print $k+1$ lines, each with an $n$-digit numbers, where the first contains the initial state of the lock and the following $k$ lines show the selected digits on the lock after each step in your solution. The final number must then be the passcode of the lock.
If there are multiple solutions, you can print any one of them. If there is no solution just print a single line containing “Neibb”.
Scoring
|
Group |
Points |
Constraints |
|
1 |
9 |
$n = 1$, $m \leq 10$ |
|
2 |
14 |
$n = 2$, $m \leq 100$ |
|
3 |
17 |
$n = 3$, $m \leq 10^3$ |
|
4 |
20 |
$n = 5$, $m \leq 10^5$ |
|
5 |
12 |
$n = 50$, $m \leq 10$ |
|
6 |
10 |
$n = 50$, $m \leq 20$ |
|
7 |
18 |
$n = 50$, $n\cdot m \leq 10^5$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
4 5 1234 1337 1236 2234 1336 1235 0234 |
4 1234 1235 1236 1336 1337 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1 8 2 8 1 9 6 4 5 3 0 7 |
4 2 1 0 9 8 |
| Sample Input 3 | Sample Output 3 |
|---|---|
8 4 85362837 63812736 13248765 89816432 85362838 81234876 |
Neibb |
