{"raw_statement":[{"iden":"statement","content":"*Note that there are two versions of this problem. Read the input section for more details.*\n\nRays Rais (short for Ray's Raisins) has been a big name in family owned raisin business around the area for a long time. So long, in fact, that apparently their name has been changed a few times since its creation!\n\nAs you read through ancient business records, you learn that Rays Rais was actually created by a man named Ray, who originally named the company after himself: Rays. But it wasn't very clear what a business named Rays sold, so he decided to double the name to get \"Rays Rays\", where the second Rays was supposed to be short for Raisins.\n\nAs time passed, it wasn't very clear that the second \"Rays\" was supposed to stand for Raisins, so it was eventually changed to \"Rais\", which caused a bit of confusion for a couple years as people adjusted to the new name.\n\nTurns out, lots of family businesses did a similar thing to slowly rename their business. Namely, they would apply one of two operations to their business name: \n\nAs you study these names, you quickly realize that businesses tended to avoid changing their name, as it would get confusing for their customers!\n\nCurrently, you are trying to piece together the name of your favorite raisin business over time, but some of the details are missing; in fact, you only know of some of the names they've used, and when they were in use. Given this list of names, can you determine the minimum number of operations the business could've performed that would be consistent with the names you observe?\n\nThe first line of input contains a single integer, $1 <= n <= 20$, the number of names you've recorded.\n\nThen, $n$ lines follow, with the $i + 1$th line containing a name $s_i$, consisting of only lowercase Latin letters. It is guaranteed that for all $2 <= i <= n$, there exists an integer $k >= 0$ for which $| s_{i + 1} | = 2^k | s_i |$. *In this version of the problem, there is no constraint on $k$.*\n\nFurthermore, it is guaranteed that $| s_i | < = 10^5$ for all $i$.\n\nOutput a single integer, the minimum number of operations the business could've performed so that its name over time would appear as $s_1$, then $s_2$, and so forth.\n\n"},{"iden":"input","content":"The first line of input contains a single integer, $1 <= n <= 20$, the number of names you've recorded.Then, $n$ lines follow, with the $i + 1$th line containing a name $s_i$, consisting of only lowercase Latin letters. It is guaranteed that for all $2 <= i <= n$, there exists an integer $k >= 0$ for which $| s_{i + 1} | = 2^k | s_i |$. *In this version of the problem, there is no constraint on $k$.*Furthermore, it is guaranteed that $| s_i | < = 10^5$ for all $i$."},{"iden":"output","content":"Output a single integer, the minimum number of operations the business could've performed so that its name over time would appear as $s_1$, then $s_2$, and so forth."},{"iden":"examples","content":"Input2\nrays\nraysrais\nOutput2\nInput4\na\nbb\ncccc\ndddddddd\nOutput10\n"}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"自从在_Iceberg Corporation_获得工作后，_Rami_ 一直忽视他的任务，转而玩一款名为_Grid Crash_的新游戏。该游戏在一个大小为 $n \\\\times m$ 的网格 $G$ 上进行。网格中的每个单元格要么有一种颜色，要么是*空的*。\\n\\n最初，网格中的每个单元格 $(i, j)$ 包含某种颜色 $c_{(i, j)}$。整个网格最多包含 4 种不同的颜色。\\n\\n游戏规则如下：\\n\\n现在，_Rami_ 希望以*最少*的步数完成游戏。请帮助他。\\n\\n输出一个整数 $r$：赢得游戏所需的最少步数。\\n\\n保证网格中包含的*不同颜色不超过* 4 种。\\n\\n以下示例展示了一个在 3 步内解决第一个游戏（测试用例 1）的移动序列。可以证明这是最优的：\\n\\n\"},{\"iden\":\"input\",\"content\":\"第一行包含两个整数 $1 \\\\leq n, m \\\\leq 5$：网格的维度。接下来的 $n$ 行，每行包含 $m$ 个字符 $c_{(i, j)} \\\\in \\\\{\\\\mathtt{A}, \\\\dots, \\\\mathtt{Z}\\\\}$：表示网格的第 $(i, j)$ 个单元格。\"},{\"iden\":\"output\",\"content\":\"输出一个整数 $r$：赢得游戏所需的最少步数。\"},{\"iden\":\"examples\",\"content\":\"输入\\n5 5\\nBWBBB\\nWWBWW\\nBWBWB\\nBWBBB\\nWWWWW\\n输出\\n3\\n\\n输入\\n5 5\\nRRRRR\\nGGRBB\\nRRRRR\\nARRRA\\nARRRA\\n输出\\n4\\n\\n输入\\n5 5\\nGGGGG\\nGRRRR\\nGGGGG\\nGRRRR\\nGGGGG\\n输出\\n2\\n\"},{\"iden\":\"note\",\"content\":\"保证网格中包含的*不同颜色不超过* 4 种。以下示例展示了一个在 $3$ 步内解决第一个游戏（测试用例 1）的移动序列。可以证明这是最优的：   \"}]}","sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G $ be an $ n \\times m $ grid, where each cell $ (i, j) $ has a color $ c_{i,j} \\in C $, and $ |C| \\leq 4 $.  \nLet $ C = \\{c_1, c_2, \\dots, c_k\\} $ be the set of distinct colors in $ G $, with $ k \\leq 4 $.  \n\nA *move* consists of selecting a color $ c \\in C $ and changing the color of the entire connected component containing a specified cell (e.g., top-left corner $ (1,1) $) to $ c $.  \n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 50 $  \n2. The grid contains at most 4 distinct colors.  \n3. The game starts with initial coloring $ c_{i,j} $ for all $ (i,j) $.  \n4. The goal is to make the entire grid monochromatic.  \n\n**Objective**  \nFind the minimum number of moves required to turn the entire grid into a single color, starting from the connected component containing $ (1,1) $, where each move recolors that component to any color in $ C $.","simple_statement":null,"has_page_source":false}