问题 D: Parentheses

时间限制: 1 Sec 内存限制: 128 MB

提交 状态 题面

题目描述

Dave loves strings consisting only of ‘(‘ and ‘)’. Especially, he is interested in balanced strings. Any balanced strings can be constructed using the following rules:

A string “()” is balanced.

Concatenation of two balanced strings are balanced.

If T is a balanced string, concatenation of ‘(‘, T, and ‘)’ in this order is balanced. For example, “()()” and “(()())” are balanced strings. “)(” and “)()(()” are not balanced strings.

Dave has a string consisting only of ‘(‘ and ‘)’. It satises the followings:

You can make it balanced by swapping adjacent characters exactly A times.

For any non-negative integer B (B<A), you cannot make it balanced by B swaps of adjacent characters.

It is the shortest of all strings satisfying the above conditions.

Your task is to compute Dave’s string. If there are multiple candidates, output the minimum in lexicographic order. As is the case with ASCII, ‘(‘ is less than ‘)’.

输入

The input consists of a single test case, which contains an integer A (1≤A≤109).

输出

Output Dave’s string in one line. If there are multiple candidates, output the minimum in lexicographic order.

样例输入

1

样例输出

)(

提示

There are infinitely many strings which can be balanced by only one swap. Dave’s string is the shortest of them.

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int a;
    cin>>a;
    int n=int((sqrt (1ll*8*a)-1)*1.0/2);
    int m=n+1;
    if(a==1) {
        printf (")(\n");
    }
    else if(a==2) {
        printf (")()(\n");
    }
    else {
        int cnt=a-n*(n+1)/2;
        int sum=m*2;
        int cnta=m,cntb=m;
        for(int i=1;i<=cnt;i++) printf (")"),sum--,cnta--;
        printf ("(");
        cntb--;
        while (cnta--) {
            printf (")");
        }
        while (cntb--) {
            printf ("(");
        }
        printf ("\n");
    }
    return 0;
}