p179.cpp
======================
#include <iostream>
#include <string>
using namespace std;

string nextSequence(string s) {
    int n = s.length();

    int i = n - 2;
    while(i >= 0 && s.substr(i, 2) == "()") {
        i -= 2;
    }

    if(i < 0) {
        return "No solution";
    }

    while(i >= 0 && s[i] == ')') {
        i--;
    }
    if(i < 0) {
        return "No solution";
    }

    s[i] = ')';

    int open = 0, close = 0;
    for(int j = 0; j <= i; j++) {
        if(s[j] == '(') {
            open++;
        } else {
            close++;
        }
    }

    int remainingOpen = n / 2 - open;
    int remainingClose = n / 2 - close;

    string result = s.substr(0, i + 1);
    for(int j = 0; j < remainingOpen; j++) {
        result += '(';
    }
    for(int j = 0; j < remainingClose; j++) {
        result += ')';
    }

    return result;
}

int main() {
    string s;
    cin >> s;
    cout << nextSequence(s) << endl;
    return 0;
}

=================
statement.txt
======================
179. Brackets light
time limit per test: 0.25 sec.
memory limit per test: 131072 KB
input: standard
output: standard



There is a correct brackets sequence. It's length doesn't exceed 10000 symbols.
Your task is to find next (in lexicographic order) correct brackets sequence with the same length. You may assume that '(' < ')'.

Input
The first line of the input contains correct brackets sequence. There are only '(' and ')' symbols in the input.

Output
Write sought sequence in the single line of the output or 'No solution' if solution doesn't exist.

Sample test(s)

Input
(())()

Output
()(())
Author:	Stanislav Angelyuk
Resource:	Saratov ST team Spring Contest #1
Date:	18.05.2003






=================
