「from y to y」Codeforces 849C From Y to Y【思维】

from y to y

C. from y to y

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

From beginning till end, this message has been waiting to be conveyed.

For a given unordered multiset of n lowercase English letters ("multi" means that a letter may APPear more than once), we treat all letters as strings of length 1, and repeat the following operation n - 1 times:

Remove any two elements s and t from the set, and add their concatenation s + t to the set.

The cost of such operation is defined to be $\text{[math]}$ , where f(s, c) denotes the number of times character cappears in string s.

Given a non-negative integer k, construct any valid non-empty set of no more than 100 000 letters, such that the Minimum accumulative cost of the whole process is exactly k. It can be shown that a solution always exists.

Input

The first and only line of input contains a non-negative integer k (0 ≤ k ≤ 100 000) — the required minimum cost.

Output

Output a non-empty string of no more than 100 000 lowercase English letters — any multiset satisfying the requirements, concatenated to be a string.

Note that the printed string doesn't need to be the final concatenated string. It only needs to represent an unordered multiset of letters.

examples

input

output

abababab

input

output

codeforces

Note

For the multiset {'a', 'b', 'a', 'b', 'a', 'b', 'a', 'b'}, one of the ways to complete the process is as follows:

{"ab", "a", "b", "a", "b", "a", "b"}, with a cost of 0;
{"aba", "b", "a", "b", "a", "b"}, with a cost of 1;
{"abab", "a", "b", "a", "b"}, with a cost of 1;
{"abab", "ab", "a", "b"}, with a cost of 0;
{"abab", "aba", "b"}, with a cost of 1;
{"abab", "abab"}, with a cost of 1;
{"abababab"}, with a cost of 8.

The total cost is 12, and it can be proved to be the minimum cost of the process.

题目大意：

一个字符串的计算价值的方式是：一开始字符串是每个字符一组，然后每次合并两个字符组，合并一个字符组的价值是：

$\text{[math]}$

这里S,T是选择的两个字符组，F（s，c）表示的是字符组S中，出现c这个字符的次数。

我们知道计算方式是多重的，我们现在取总值最小的那个方法。

现在给你一个最小价值k，让你构造一个不超过1e5长度的字符串

思路：

①我们知道，如果我们希望一个字符串的总价值最小，我们肯定是要从左到右依次合并的。

②那么我们如果一个字符串中有x个a的话，那么对应这些字符a贡献的价值是：（x*(x-1)）/2；

那么每种字符出现的位子就已经无所谓了。

③那么对应我们发现，输入的值不大，那么对应我们暴力走一下就行，具体参考代码。

Ac代码：

#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int nowsum=0;
        for(int i=1;i<=26;i++)
        {
            int pos=100;
            for(int j=1;j<=100;j++)
            {
                if(nowsum+j*(j-1)/2>n)
                {
                    pos=j-1;
                    break;
                }
            }
            for(int j=1;j<=pos;j++)printf("%c",i+'a'-1);
            nowsum+=(pos*(pos-1))/2;
            if(nowsum==n)break;
        }
        printf("\n");
    }
}

Codeforces 849C From Y to Y【思维】

from y to y

相关阅读

栏目导航

推荐阅读

热门阅读