{"problem":{"name":"G1. Family Farm I","description":{"content":"*Note that there are two versions of this problem. Read the input section for more details.* Rays Rais (short for Ray's Raisins) has been a big name in family owned raisin business around the area fo","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CFG1"},"statements":[{"statement_type":"Markdown","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, $k$ will always either be 0 or 1.*\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## Input\n\nThe 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, $k$ will always either be 0 or 1.*Furthermore, it is guaranteed that $| s_i | < = 10^5$ for all $i$.\n\n## Output\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[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"*请注意，本题有两个版本。请阅读输入部分以获取更多细节。*\n\nRays Rais（简称 Ray's Raisins）长期以来一直是当地家族经营的葡萄干生意中的知名品牌。事实上，自创立以来，它的名称已经更改过几次！\n\n当你查阅古老的商业记录时，你了解到 Rays Rais 实际上是由一位名叫 Ray 的人创立的，他最初以自己的名字命名公司：Rays。但“Rays”这个名字并不清楚该公司销售什么，于是他决定将名称重复一次，得到“Rays Rays”，其中第二个“Rays”本意是 Raisins 的缩写。\n\n随着时间推移，人们越来越不清楚第二个“Rays”是代表 Raisins，因此最终被改为“Rais”，这在几年内引起了一些混乱，人们需要适应新名称。\n\n事实证明，许多家族企业都采取了类似的方式逐步更名：他们会对公司名称应用以下两种操作之一：\n\n当你研究这些名称时，你很快意识到企业倾向于避免更改名称，因为这会让顾客感到困惑！\n\n目前，你正试图拼凑出你最喜爱的葡萄干企业名称随时间的变化过程，但部分细节已丢失；事实上，你只知道他们使用过的一些名称以及使用的时间。给定这份名称列表，你能确定该企业为符合你观察到的名称序列，最少可能执行了多少次操作吗？\n\n输入的第一行包含一个整数 $1 lt.eq n lt.eq 20$，表示你记录的名称数量。\n\n接下来 $n$ 行，第 $i + 1$ 行包含一个名称 $s_i$，仅由小写拉丁字母组成。保证对于所有 $2 lt.eq i lt.eq n$，存在一个整数 $k gt.eq 0$，使得 $| s_(i + 1) | = 2^k | s_i |$。*在本题版本中，$k$ 始终为 0 或 1。*\n\n此外，保证对所有 $i$，都有 $| s_i | < = 10^5$。\n\n请输出一个整数，表示该企业为使其名称随时间依次为 $s_1$, $s_2$, ...，所执行的最少操作次数。\n\n## Input\n\n输入的第一行包含一个整数，$1 lt.eq n lt.eq 20$，表示你记录的名称数量。接下来 $n$ 行，第 $i + 1$ 行包含一个名称 $s_i$，仅由小写拉丁字母组成。保证对于所有 $2 lt.eq i lt.eq n$，存在一个整数 $k gt.eq 0$，使得 $| s_(i + 1) | = 2^k | s_i |$。*在本题版本中，$k$ 始终为 0 或 1。*此外，保证对所有 $i$，都有 $| s_i | < = 10^5$。\n\n## Output\n\n请输出一个整数，表示该企业为使其名称随时间依次为 $s_1$, $s_2$, ...，所执行的最少操作次数。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of recorded names.  \nLet $ S = (s_1, s_2, \\dots, s_n) $ be a sequence of strings, where each $ s_i $ consists of lowercase Latin letters.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 20 $  \n2. For all $ 1 \\le i < n $, $ |s_{i+1}| = |s_i| $ or $ |s_{i+1}| = 2 \\cdot |s_i| $  \n3. $ |s_i| \\le 10^5 $ for all $ i $  \n\n**Operations**  \nTwo allowed operations on a string $ s $:  \n- **Double**: Replace $ s $ with $ s + s $ (concatenation with itself).  \n- **Half**: If $ |s| $ is even, replace $ s $ with its first half, i.e., $ s[1 : |s|/2] $.  \n\n**Objective**  \nFind the minimum total number of operations (Double or Half) required to transform $ s_1 \\to s_2 \\to \\cdots \\to s_n $, such that each transition $ s_i \\to s_{i+1} $ is achieved by exactly one operation.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CFG1","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}