CCC '01 S5 - Post's Correspondence Problem - Olympiads Online Judge

CCC '01 S5 - Post's Correspondence Problem

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 256M

Problem types

Canadian Computing Competition: 2001 Stage 1, Senior #5

Let $A$ $A$ and $B$ $B$ be two sequences of non-empty strings:

$\displaystyle \begin{align*} A &= (a_1, a_2, \dots, a_n) \\ B &= (b_1, b_2, \dots, b_n) \end{align*}$ $\begin{aligned} A & = (a_{1}, a_{2}, \dots, a_{n}) \\ B & = (b_{1}, b_{2}, \dots, b_{n}) \end{aligned}$

Let $m$ $m$ be a positive integer. Does there exist a sequence of integers $i_1, i_2, \dots, i_k$ $i_{1}, i_{2}, \dots, i_{k}$ such that $m > k > 0$ $m > k > 0$ and $a_{i_1} a_{i_2} \dots a_{i_k} = b_{i_1} b_{i_2} \dots b_{i_k}$ $a_{i_{1}} a_{i_{2}} \dots a_{i_{k}} = b_{i_{1}} b_{i_{2}} \dots b_{i_{k}}$ ?

For example, if $A = (a, abaaa, ab)$ $A = (a, a b a a a, a b)$ and $B = (aaa, ab, b)$ $B = (a a a, a b, b)$ , then the required sequence of integers is $(2, 1, 1, 3)$ $(2, 1, 1, 3)$ giving $abaaaaaab = abaaaaaab$ $a b a a a a a a b = a b a a a a a a b$ .

Input Specification

The first two lines of input will contain $m$ $m$ and $n$ $n$ respectively, and $m \times n \le 40$ $m \times n \leq 40$ . The next $2n$ $2 n$ lines contain in order the elements of $A$ $A$ followed by the elements of $B$ $B$ . Each string is at most $20$ $20$ characters.

Output Specification

If a solution exists, print $k$ $k$ on a line by itself, followed by the integer sequence in order, one element per line. Otherwise, print a single line containing No solution..

Sample Input 1

Copy

7
3
a
abaaa
ab
aaa
ab
b

Sample Output 1

Copy

Sample Input 2

Copy

10
3
abc
def
ghi
bcd
efg
hia

Sample Output 2

Copy

No solution.

Comments

0

jeffthemonster200 commented 66 days ago ← edited →

tallinn

0

tallinn commented 75 days ago

jeffthemonster200