'A' String

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 5.0s
Memory limit: 64M

Problem types

Given an integer X, construct a string S (1 \leq |S| \leq 10^5) with only the characters a and b that has exactly X substrings that contain the character a.

If there are multiple solutions, you may print any.

Input Specification

The first and only line will contain an integer X\ (0 \leq X \leq 10^9).

Output Specification

You are to print one line, containing a string that satisfies the conditions outlined in the problem statement.


It may be useful to know that the number of substrings of a string of length N is \frac{N(N+1)}{2}.


Subtask 1 (80%)

X \leq 55

Subtask 2 (10%)

X \leq 250

Subtask 3 (10%)

No further constraints.

Sample Input 1


Sample Output 1


Explanation for Sample 1

bab contains 6 substrings: b,a,b,ba,ab, and bab. 4 of these substrings contain the character a.

Sample Input 2


Sample Output 2


Explanation for Sample 2

bbaba contains 15 substrings: b, b, a, b, a, bb, ba, ab, ba, bba, bab, aba, bbab, baba, bbaba. 11 of these substrings contain the character a.


There are no comments at the moment.