1714D.md (3134B)
1 Source: https://codeforces.com/problemset/problem/1714/D 2 3 D. Color with Occurrences 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given some text $t$ and a set of $n$ strings $s_1, s_2, \dots, s_n$. 22 23 In one step, you can choose any occurrence of any string $s_i$ in the text $t$ and color the corresponding characters of the text in red. For example, if $t=\texttt{bababa}$ and $s_1=\texttt{ba}$, $s_2=\texttt{aba}$, you can get $t=\color{red}{\texttt{ba}}\texttt{baba}$, $t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba}$ or $t=\texttt{bab}\color{red}{\texttt{aba}}$ in one step. 24 25 You want to color all the letters of the text $t$ in red. When you color a letter in red again, it stays red. 26 27 In the example above, three steps are enough: 28 29 * Let's color $t[2 \dots 4]=s_2=\texttt{aba}$ in red, we get $t=\texttt{b}\color{red}{\texttt{aba}}\texttt{ba}$; 30 * Let's color $t[1 \dots 2]=s_1=\texttt{ba}$ in red, we get $t=\color{red}{\texttt{baba}}\texttt{ba}$; 31 * Let's color $t[4 \dots 6]=s_2=\texttt{aba}$ in red, we get $t=\color{red}{\texttt{bababa}}$. 32 33 Each string $s_i$ can be applied any number of times (or not at all). Occurrences for coloring can intersect arbitrarily. 34 35 Determine the minimum number of steps needed to color all letters $t$ in red and how to do it. If it is impossible to color all letters of the text $t$ in red, output -1. 36 37 Input 38 39 The first line of the input contains an integer $q$ ($1 \le q \le 100$) —the number of test cases in the test. 40 41 The descriptions of the test cases follow. 42 43 The first line of each test case contains the text $t$ ($1 \le |t| \le 100$), consisting only of lowercase Latin letters, where $|t|$ is the length of the text $t$. 44 45 The second line of each test case contains a single integer $n$ ($1 \le n \le 10$) — the number of strings in the set. 46 47 This is followed by $n$ lines, each containing a string $s_i$ ($1 \le |s_i| \le 10$) consisting only of lowercase Latin letters, where $|s_i|$ — the length of string $s_i$. 48 49 Output 50 51 For each test case, print the answer on a separate line. 52 53 If it is impossible to color all the letters of the text in red, print a single line containing the number -1. 54 55 Otherwise, on the first line, print the number $m$ — the minimum number of steps it will take to turn all the letters $t$ red. 56 57 Then in the next $m$ lines print pairs of indices: $w_j$ and $p_j$ ($1 \le j \le m$), which denote that the string with index $w_j$ was used as a substring to cover the occurrences starting in the text $t$ from position $p_j$. The pairs can be output in any order. 58 59 If there are several answers, output any of them. 60 61 Example 62 63 Input 64 65 ``` 66 6 67 68 bababa 69 70 2 71 72 ba 73 74 aba 75 76 caba 77 78 2 79 80 bac 81 82 acab 83 84 abacabaca 85 86 3 87 88 aba 89 90 bac 91 92 aca 93 94 baca 95 96 3 97 98 a 99 100 c 101 102 b 103 104 codeforces 105 106 4 107 108 def 109 110 code 111 112 efo 113 114 forces 115 116 aaaabbbbcccceeee 117 118 4 119 120 eeee 121 122 cccc 123 124 aaaa 125 126 bbbb 127 ``` 128 129 Output 130 131 ``` 132 3 133 2 2 134 1 1 135 2 4 136 -1 137 4 138 1 1 139 2 6 140 3 3 141 3 7 142 4 143 3 1 144 1 2 145 2 3 146 1 4 147 2 148 4 5 149 2 1 150 4 151 3 1 152 4 5 153 2 9 154 1 13 155 ``` 156 157 Note 158 159 The first test case is explained in the problem statement. 160 161 In the second test case, it is impossible to color all the letters of the text in red.