{"problem":{"name":"B. String Typing","description":{"content":"You are given a string _s_ consisting of _n_ lowercase Latin letters. You have to type this string using your keyboard. Initially, you have an empty string. Until you type the whole string, you may p","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF954B"},"statements":[{"statement_type":"Markdown","content":"You are given a string _s_ consisting of _n_ lowercase Latin letters. You have to type this string using your keyboard.\n\nInitially, you have an empty string. Until you type the whole string, you may perform the following operation:\n\n*   add a character to the end of the string.\n\nBesides, **at most once** you may perform one additional operation: copy the string and append it to itself.\n\nFor example, if you have to type string _abcabca_, you can type it in 7 operations if you type all the characters one by one. However, you can type it in 5 operations if you type the string _abc_ first and then copy it and type the last character.\n\nIf you have to type string _aaaaaaaaa_, the best option is to type 4 characters one by one, then copy the string, and then type the remaining character.\n\nPrint the minimum number of operations you need to type the given string.\n\n## Input\n\nThe first line of the input containing only one integer number _n_ (1 ≤ _n_ ≤ 100) — the length of the string you have to type. The second line containing the string _s_ consisting of _n_ lowercase Latin letters.\n\n## Output\n\nPrint one integer number — the minimum number of operations you need to type the given string.\n\n[samples]\n\n## Note\n\nThe first test described in the problem statement.\n\nIn the second test you can only type all the characters one by one.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"给你一个由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]。你需要使用键盘输入这个字符串。\n\n最初，你有一个空字符串。在输入完整个字符串之前，你可以执行以下操作：\n\n此外，*最多一次*，你可以执行一个额外的操作：复制当前字符串并将其追加到自身后面。\n\n例如，如果你需要输入字符串 _abcabca_，你可以通过逐个输入所有字符，在 #cf_span[7] 次操作内完成。但如果你先输入字符串 _abc_，然后复制它，再输入最后一个字符，你可以在 #cf_span[5] 次操作内完成。\n\n如果你需要输入字符串 _aaaaaaaaa_，最佳方案是先逐个输入 #cf_span[4] 个字符，然后复制字符串，再输入剩余的字符。\n\n请输出输入给定字符串所需的最少操作次数。\n\n输入的第一行仅包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）— 你需要输入的字符串的长度。第二行包含由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]。\n\n请输出一个整数 —— 输入给定字符串所需的最少操作次数。\n\n题目描述中的第一个测试用例。\n\n在第二个测试用例中，你只能逐个输入所有字符。\n\n## Input\n\n输入的第一行仅包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）— 你需要输入的字符串的长度。第二行包含由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]。\n\n## Output\n\n请输出一个整数 —— 输入给定字符串所需的最少操作次数。\n\n[samples]\n\n## Note\n\n题目描述中的第一个测试用例。\n在第二个测试用例中，你只能逐个输入所有字符。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the target string.  \nLet $ s = s_1 s_2 \\dots s_n $ be the target string over the alphabet of lowercase Latin letters.  \n\nLet $ k \\in \\{0, 1\\} $ indicate whether the copy operation is used ($ k = 1 $) or not ($ k = 0 $).  \n\nFor a given $ k $, let $ i \\in \\{1, \\dots, n\\} $ be the length of the prefix typed manually before the copy operation (if used).  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 100 $  \n2. $ s_i \\in \\{a, b, \\dots, z\\} $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. If $ k = 1 $, then $ 1 \\leq i \\leq \\lfloor n/2 \\rfloor $ and $ s_{1:i} = s_{i+1:2i} $ (the prefix of length $ i $ must equal the next $ i $ characters).  \n\n**Objective**  \nMinimize the total number of operations:  \n$$\n\\min_{k \\in \\{0,1\\}} \\min_{\\substack{i \\in \\{1,\\dots,n\\} \\\\ \\text{if } k=1: s_{1:i} = s_{i+1:2i}}} \\left( i + k + \\max(0, n - 2i) \\right)\n$$  \nwhere:  \n- $ i $: number of manual character insertions before copy (if used),  \n- $ k $: 1 if copy is used, else 0,  \n- $ \\max(0, n - 2i) $: number of manual insertions after copy.  \n\nThe minimum value of this expression over all valid $ k $ and $ i $ is the answer.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF954B","tags":["implementation","strings"],"sample_group":[["7\nabcabca","5"],["8\nabcdefgh","8"]],"created_at":"2026-03-03 11:00:39"}}