B. Mike and strings

Codeforces

IDCF798B

Time2000ms

Memory256MB

Difficulty—

brute forcedpstrings

English · Original

Chinese · Translation

Formal · Original

Mike has _n_ strings _s_1, _s_2, ..., _s__n_ each consisting of lowercase English letters. In one move he can choose a string _s__i_, erase the first character and append it to the end of the string. For example, if he has the string "_coolmike_", in one move he can transform it into the string "_oolmikec_". Now Mike asks himself: what is minimal number of moves that he needs to do in order to make all the strings equal? ## Input The first line contains integer _n_ (1 ≤ _n_ ≤ 50) — the number of strings. This is followed by _n_ lines which contain a string each. The _i_\-th line corresponding to string _s__i_. Lengths of strings are equal. Lengths of each string is positive and don't exceed 50. ## Output Print the minimal number of moves Mike needs in order to make all the strings equal or print - 1 if there is no solution. [samples] ## Note In the first sample testcase the optimal scenario is to perform operations in such a way as to transform all strings into "_zwoxz_".

Mike 有 #cf_span[n] 个字符串 #cf_span[s1, s2, ..., sn]，每个字符串均由小写英文字母组成。在一次操作中，他可以选择一个字符串 #cf_span[si]，将其第一个字符删除并附加到该字符串的末尾。例如，如果他拥有字符串 "_coolmike_"，一次操作后可以将其变为 "_oolmikec_"。现在 Mike 自问：他最少需要多少次操作，才能使所有字符串变得相等？第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 50]) —— 字符串的数量。接下来是 #cf_span[n] 行，每行包含一个字符串。第 #cf_span[i] 行对应字符串 #cf_span[si]。所有字符串长度相等，且每个字符串的长度为正数，不超过 #cf_span[50]。请输出 Mike 为使所有字符串相等所需的最少操作次数，若无解则输出 #cf_span[ - 1]。在第一个测试用例中，最优方案是执行操作，使得所有字符串变为 "_zwoxz_"。 ## Input 第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 50]) —— 字符串的数量。接下来是 #cf_span[n] 行，每行包含一个字符串。第 #cf_span[i] 行对应字符串 #cf_span[si]。所有字符串长度相等，且每个字符串的长度为正数，不超过 #cf_span[50]。 ## Output 请输出 Mike 为使所有字符串相等所需的最少操作次数，若无解则输出 #cf_span[ - 1]。 [samples] ## Note 在第一个测试用例中，最优方案是执行操作，使得所有字符串变为 "_zwoxz_"。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of strings, with $ 1 \leq n \leq 50 $. Let $ S = \{s_1, s_2, \dots, s_n\} $ be a set of strings, each of length $ \ell \in \mathbb{Z}^+ $, $ \ell \leq 50 $, over the alphabet of lowercase English letters. A *move* on string $ s_i $ consists of rotating it left by one character: $ s_i = c_1c_2\dots c_\ell \mapsto c_2\dots c_\ell c_1 $. Let $ R(s) = \{ s^{(k)} \mid k \in \{0, 1, \dots, \ell-1\} \} $ denote the set of all cyclic rotations of string $ s $, where $ s^{(k)} $ is the string obtained by $ k $ left rotations. **Constraints** 1. $ 1 \leq n \leq 50 $ 2. All strings in $ S $ have equal length $ \ell $, $ 1 \leq \ell \leq 50 $ **Objective** Find the minimum total number of moves required to transform all strings in $ S $ into the same string $ t $, where $ t \in \bigcap_{i=1}^n R(s_i) $. If no such $ t $ exists, output $ -1 $. Otherwise, compute: $$ \min_{t \in \bigcap_{i=1}^n R(s_i)} \sum_{i=1}^n \min\{ k \in \{0, 1, \dots, \ell-1\} \mid s_i^{(k)} = t \} $$

Samples

Input #1

4
xzzwo
zwoxz
zzwox
xzzwo

Output #1

Input #2

2
molzv
lzvmo

Output #2

Input #3

3
kc
kc
kc

Output #3

Input #4

3
aa
aa
ab

Output #4

\-1

API Response (JSON)

{
  "problem": {
    "name": "B. Mike and strings",
    "description": {
      "content": "Mike has _n_ strings _s_1, _s_2, ..., _s__n_ each consisting of lowercase English letters. In one move he can choose a string _s__i_, erase the first character and append it to the end of the string. ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF798B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mike has _n_ strings _s_1, _s_2, ..., _s__n_ each consisting of lowercase English letters. In one move he can choose a string _s__i_, erase the first character and append it to the end of the string. ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Mike 有 #cf_span[n] 个字符串 #cf_span[s1, s2, ..., sn]，每个字符串均由小写英文字母组成。在一次操作中，他可以选择一个字符串 #cf_span[si]，将其第一个字符删除并附加到该字符串的末尾。例如，如果他拥有字符串 \"_coolmike_\"，一次操作后可以将其变为 \"_oolmikec_\"。\n\n现在 Mike 自问：他最少需要多少次操作，才能使所有字符串...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of strings, with $ 1 \\leq n \\leq 50 $.  \nLet $ S = \\{s_1, s_2, \\dots, s_n\\} $ be a set of strings, each of length $ \\ell \\in \\mathbb{Z}^+ $, $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments