CF1368B Codeforces Subsequences
Karl likes Codeforces and subsequences. He wants to find a string of lowercase English letters that contains at least subsequences codeforces. Out of all possible strings, Karl wants to find a shortest one.
Formally, a codeforces subsequence of a string is a subset of ten characters of that read codeforces from left to right. For example, codeforces contains codeforces a single time, while codeforcesisawesome contains codeforces four times: codeforcescisawesome, codeforcecsiscawesome, codeforcecsisawescome, codeforccesisawescome.
Help Karl find any shortest string that contains at least ccodeforces subsequences.
Input
The only line contains a single integer .
Output
Print a shortest string of lowercase English letters that contains at least ccodeforces subsequences. If there are several such strings, print any of them.
Examples
input
1 | 1 |
output
1 | codeforces |
input
1 | 3 |
output
1 | codeforcesss |
Translation
找到包含 个形如 codeforces 子序列的最短字符串 ,若有多个可行方案,输出任意一个。
Idea
贪心地想,显然我们发现形如 ccccooddddfffoorrrcccceess 的情况下肯定是最优的,这样构造非常节省需要添加的字母个数。codeforces 一个 个字母,不妨设第 个位置的字母在 中连续出现次数为 ,那么包含的 codeforces 子序列个数有 ;题目要求 ,且 尽量小。
由均值不等式 ,当且仅当 时取等号。我们的任务是使得 尽量平均。不妨先取 ,然后根据条件 ,不断试探,依次将 增加 ,直到满足条件。
Code
1 | /****************************************************************** |