题目描述

题目链接

A. From Y to Y
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard 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 , where f(s, c) denotes the number of times character c appears 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
12
output
abababab
input
3
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.

题解

题意：对于字符串s和字符c， f(s, c)表示c在s中出现的次数， 若将c合并到s中， 则花费f(s, c)，要求求一个字符串， 是的合并后的最小话费恰好等于k。
思路：可以发现， 只有一种字符的字符串s， 若他的长度为n， 则花费 n * (n - 1) / 2。这点是非常重要的， 啧啧啧， 奇妙的题， 发现这个规律就好办了， 这里我用到了二分。 若对我使用的二分有疑问， 请看这篇博客

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;

#define esp 1e-6
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 1e4 + 5;
const int M = 1e9 + 5;
const int mod = 998244353;

int binary_search(int a[], int low, int high, int key){ // 二分查找第一个小于等于key的值得下标
    int m;
    while(low < high){
        m = low + (high - low + 1) / 2; //从后往前， 向上取整
        if (a[m] <= key)
            low = m;
        else
            high = m - 1; // 后往前， 改变的是high
    }
    if(a[low] <= key)
        return low;
    return -1;
}
int sum[N];
int main(){
    for (int i = 0; i <= 150; i++){
        sum[i] = i * (i - 1) / 2;
    }// 打表
    int k, cnt;
    cin >> k;
    for (int i = 'a'; i <= 'z'; i++){
        cnt = binary_search(sum, 0, 150, k);
        for (int j = 1; j <= cnt; j++)
            printf("%c", i);
        k -= sum[cnt];
        if (k == 0)
            break;
    }

    return 0;
}
1
恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan