A. Diversity

Codeforces

IDCF844A

Time1000ms

Memory256MB

Difficulty—

greedyimplementationstrings

English · Original

Chinese · Translation

Formal · Original

Calculate the minimum number of characters you need to change in the string _s_, so that it contains at least _k_ different letters, or print that it is impossible. String _s_ consists only of lowercase Latin letters, and it is allowed to change characters only to lowercase Latin letters too. ## Input First line of input contains string _s_, consisting only of lowercase Latin letters (1 ≤ |_s_| ≤ 1000, |_s_| denotes the length of _s_). Second line of input contains integer _k_ (1 ≤ _k_ ≤ 26). ## Output Print single line with a minimum number of necessary changes, or the word «_impossible_» (without quotes) if it is impossible. [samples] ## Note In the first test case string contains 6 different letters, so we don't need to change anything. In the second test case string contains 4 different letters: {'_a_', '_h_', '_o_', '_y_'}. To get 5 different letters it is necessary to change one occurrence of '_o_' to some letter, which doesn't occur in the string, for example, {'_b_'}. In the third test case, it is impossible to make 7 different letters because the length of the string is 6.

计算需要更改字符串 #cf_span[s] 中的最少字符数，使得其中至少包含 #cf_span[k] 个不同的字母，或判断这是不可能的。字符串 #cf_span[s] 仅由小写拉丁字母组成，且只能将字符更改为小写拉丁字母。输入的第一行包含字符串 #cf_span[s]，仅由小写拉丁字母组成（#cf_span[1 ≤ |s| ≤ 1000]，#cf_span[|s|] 表示 #cf_span[s] 的长度）。输入的第二行包含整数 #cf_span[k]（#cf_span[1 ≤ k ≤ 26]）。请输出一行，包含所需的最少更改次数，或在不可能时输出单词 «_impossible_»（不含引号）。在第一个测试用例中，字符串包含 #cf_span[6] 个不同的字母，因此无需更改任何字符。在第二个测试用例中，字符串包含 #cf_span[4] 个不同的字母：#cf_span[{'a', 'h', 'o', 'y'}]。为了获得 #cf_span[5] 个不同的字母，需要将一个 #cf_span['o'] 更改为字符串中未出现的某个字母，例如 #cf_span[{'b'}]。在第三个测试用例中，由于字符串长度为 #cf_span[6]，因此不可能得到 #cf_span[7] 个不同的字母。 ## Input 输入的第一行包含字符串 #cf_span[s]，仅由小写拉丁字母组成（#cf_span[1 ≤ |s| ≤ 1000]，#cf_span[|s|] 表示 #cf_span[s] 的长度）。第二行包含整数 #cf_span[k]（#cf_span[1 ≤ k ≤ 26]）。 ## Output 请输出一行，包含所需的最少更改次数，或在不可能时输出单词 «_impossible_»（不含引号）。 [samples] ## Note 在第一个测试用例中，字符串包含 #cf_span[6] 个不同的字母，因此无需更改任何字符。在第二个测试用例中，字符串包含 #cf_span[4] 个不同的字母：#cf_span[{'a', 'h', 'o', 'y'}]。为了获得 #cf_span[5] 个不同的字母，需要将一个 #cf_span['o'] 更改为字符串中未出现的某个字母，例如 #cf_span[{'b'}]。在第三个测试用例中，由于字符串长度为 #cf_span[6]，因此不可能得到 #cf_span[7] 个不同的字母。

**Definitions** Let $ s \in \Sigma^* $ be a string over $ \Sigma = \{a, b, \dots, z\} $, with $ |s| = n $. Let $ k \in \mathbb{Z} $ be the target number of distinct lowercase Latin letters. Let $ d = |\{ c \in \Sigma \mid c \text{ appears in } s \}| $ be the number of distinct letters currently in $ s $. **Constraints** 1. $ 1 \leq n \leq 1000 $ 2. $ 1 \leq k \leq 26 $ **Objective** Find the minimum number of character changes required so that the resulting string contains at least $ k $ distinct letters, or determine that it is impossible. - If $ k > n $, output "impossible". - Otherwise, if $ d \geq k $, output $ 0 $. - Otherwise, output $ k - d $ (since each change can introduce at most one new distinct letter, and we need $ k - d $ additional distinct letters).

Samples

Input #1

yandex
6

Output #1

Input #2

yahoo
5

Output #2

Input #3

google
7

Output #3

impossible

API Response (JSON)

{
  "problem": {
    "name": "A. Diversity",
    "description": {
      "content": "Calculate the minimum number of characters you need to change in the string _s_, so that it contains at least _k_ different letters, or print that it is impossible. String _s_ consists only of lowerc",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF844A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Calculate the minimum number of characters you need to change in the string _s_, so that it contains at least _k_ different letters, or print that it is impossible.\n\nString _s_ consists only of lowerc...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "计算需要更改字符串 #cf_span[s] 中的最少字符数，使得其中至少包含 #cf_span[k] 个不同的字母，或判断这是不可能的。\n\n字符串 #cf_span[s] 仅由小写拉丁字母组成，且只能将字符更改为小写拉丁字母。\n\n输入的第一行包含字符串 #cf_span[s]，仅由小写拉丁字母组成（#cf_span[1 ≤ |s| ≤ 1000]，#cf_span[|s|] 表示 #cf_span...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\Sigma^* $ be a string over $ \\Sigma = \\{a, b, \\dots, z\\} $, with $ |s| = n $.  \nLet $ k \\in \\mathbb{Z} $ be the target number of distinct lowercase Latin letters.\n\nLet $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments