← 返回题目列表

AtCoder · tenka1_2014_final_c

C. 音序器

中文机器翻译题面 查看原题

問題文

A、T、G、C 中的任意一个字符以及每个 1 字符对应的通配符(.)构成的字符串模式 N 。

1 每个模式最多 1 只能包含一个通配符。

包含所有给定模式作为子字符串的字符串 X 中最短的长度是多少,吉野君。


入力

输入是按以下格式从标准输入给出的。

N
S1
S2
:
SN
  • 1第 行表示模式数量 N(1 \leq N \leq 12) 。 表示
  • 2从行 N 行包含i第几个模式 Si 。 表示
  • Si 的长度 |Si| 是 您也可以写 1 \leq |Si| \leq 600 很满意。
  • Si 由 A、T、G、C 中的任意字符或通配符(.)组成。
  • Si 中包含的通配符数量最多为 1 字符。

部分点

  • 如果所给模式中所有模式都不包含通配符且答对的情况,将作为部分分数给出 60 分。

出力

输出最短的字符串 X 的长度 1 行。在输出末尾添加换行符。


入力例1

2
TAG
GAT

出力例1

5

输出最短的字符串 X 是 您也可以写 TAGAT或 至少GATAG。


入力例2

4
AA.
TAT
ATTAC.
TA.T

出力例2

9

输出最短的字符串 X 是 您也可以写 AATTACTAT 。