{"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 lowercase Latin letters, and it is allowed to change characters only to lowercase Latin letters too.\n\n## Input\n\nFirst line of input contains string _s_, consisting only of lowercase Latin letters (1 ≤ |_s_| ≤ 1000, |_s_| denotes the length of _s_).\n\nSecond line of input contains integer _k_ (1 ≤ _k_ ≤ 26).\n\n## Output\n\nPrint single line with a minimum number of necessary changes, or the word «_impossible_» (without quotes) if it is impossible.\n\n[samples]\n\n## Note\n\nIn the first test case string contains 6 different letters, so we don't need to change anything.\n\nIn 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_'}.\n\nIn the third test case, it is impossible to make 7 different letters because the length of the string is 6.","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[s] 的长度）。\n\n输入的第二行包含整数 #cf_span[k]（#cf_span[1 ≤ k ≤ 26]）。\n\n请输出一行，包含所需的最少更改次数，或在不可能时输出单词 «_impossible_»（不含引号）。\n\n在第一个测试用例中，字符串包含 #cf_span[6] 个不同的字母，因此无需更改任何字符。\n\n在第二个测试用例中，字符串包含 #cf_span[4] 个不同的字母：#cf_span[{'a', 'h', 'o', 'y'}]。为了获得 #cf_span[5] 个不同的字母，需要将一个 #cf_span['o'] 更改为字符串中未出现的某个字母，例如 #cf_span[{'b'}]。\n\n在第三个测试用例中，由于字符串长度为 #cf_span[6]，因此不可能得到 #cf_span[7] 个不同的字母。\n\n## Input\n\n输入的第一行包含字符串 #cf_span[s]，仅由小写拉丁字母组成（#cf_span[1 ≤ |s| ≤ 1000]，#cf_span[|s|] 表示 #cf_span[s] 的长度）。第二行包含整数 #cf_span[k]（#cf_span[1 ≤ k ≤ 26]）。\n\n## Output\n\n请输出一行，包含所需的最少更改次数，或在不可能时输出单词 «_impossible_»（不含引号）。\n\n[samples]\n\n## Note\n\n在第一个测试用例中，字符串包含 #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] 个不同的字母。","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 $ d = |\\{ c \\in \\Sigma \\mid c \\text{ appears in } s \\}| $ be the number of distinct letters currently in $ s $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 1000 $  \n2. $ 1 \\leq k \\leq 26 $\n\n**Objective**  \nFind the minimum number of character changes required so that the resulting string contains at least $ k $ distinct letters, or determine that it is impossible.\n\n- If $ k > n $, output \"impossible\".  \n- Otherwise, if $ d \\geq k $, output $ 0 $.  \n- Otherwise, output $ k - d $ (since each change can introduce at most one new distinct letter, and we need $ k - d $ additional distinct letters).","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF844A","tags":["greedy","implementation","strings"],"sample_group":[["yandex\n6","0"],["yahoo\n5","1"],["google\n7","impossible"]],"created_at":"2026-03-03 11:00:39"}}