B. String Typing

Codeforces

IDCF954B

Time1000ms

Memory256MB

Difficulty—

implementationstrings

English · Original

Chinese · Translation

Formal · Original

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 perform the following operation: * add a character to the end of the string. Besides, **at most once** you may perform one additional operation: copy the string and append it to itself. For 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. If 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. Print the minimum number of operations you need to type the given string. ## Input The 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. ## Output Print one integer number — the minimum number of operations you need to type the given string. [samples] ## Note The first test described in the problem statement. In the second test you can only type all the characters one by one.

给你一个由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]。你需要使用键盘输入这个字符串。最初，你有一个空字符串。在输入完整个字符串之前，你可以执行以下操作：此外，*最多一次*，你可以执行一个额外的操作：复制当前字符串并将其追加到自身后面。例如，如果你需要输入字符串 _abcabca_，你可以通过逐个输入所有字符，在 #cf_span[7] 次操作内完成。但如果你先输入字符串 _abc_，然后复制它，再输入最后一个字符，你可以在 #cf_span[5] 次操作内完成。如果你需要输入字符串 _aaaaaaaaa_，最佳方案是先逐个输入 #cf_span[4] 个字符，然后复制字符串，再输入剩余的字符。请输出输入给定字符串所需的最少操作次数。输入的第一行仅包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）— 你需要输入的字符串的长度。第二行包含由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]。请输出一个整数 —— 输入给定字符串所需的最少操作次数。题目描述中的第一个测试用例。在第二个测试用例中，你只能逐个输入所有字符。 ## Input 输入的第一行仅包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）— 你需要输入的字符串的长度。第二行包含由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]。 ## Output 请输出一个整数 —— 输入给定字符串所需的最少操作次数。 [samples] ## Note 题目描述中的第一个测试用例。在第二个测试用例中，你只能逐个输入所有字符。

**Definitions** Let $ n \in \mathbb{Z} $ be the length of the target string. Let $ s = s_1 s_2 \dots s_n $ be the target string over the alphabet of lowercase Latin letters. Let $ k \in \{0, 1\} $ indicate whether the copy operation is used ($ k = 1 $) or not ($ k = 0 $). For a given $ k $, let $ i \in \{1, \dots, n\} $ be the length of the prefix typed manually before the copy operation (if used). **Constraints** 1. $ 1 \leq n \leq 100 $ 2. $ s_i \in \{a, b, \dots, z\} $ for all $ i \in \{1, \dots, n\} $ 3. 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). **Objective** Minimize the total number of operations: $$ \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) $$ where: - $ i $: number of manual character insertions before copy (if used), - $ k $: 1 if copy is used, else 0, - $ \max(0, n - 2i) $: number of manual insertions after copy. The minimum value of this expression over all valid $ k $ and $ i $ is the answer.

Samples

Input #1

7
abcabca

Output #1

Input #2

8
abcdefgh

Output #2

API Response (JSON)

{
  "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 p...",
      "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] 次操作内完成。但...",
      "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\\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments