Решение задачи Интересные конкурсы с Codeforces

С пояснением   Просмотров: 23


Напомним, что скобочная последовательность называется правильной, если путем вставки в неё символов «+» и «1» можно получить из неё корректное математическое выражение. Например, последовательности «(())()», «()» и «(()(()))» — правильные, в то время как «)(», «(()» и «(()))(» — нет.

Учительница дала классу, в котором учится Дмитрий, очень странное задание — она попросила каждого из учеников придумать последовательность произвольной длины, состоящую только из открывающих и закрывающих скобок. После этого все ученики по очереди называли придуманные ими последовательности. Когда очередь дошла до Димы, он внезапно понял, что у всех его одноклассников получились правильные скобочные последовательности, а получилась ли у него правильная скобочная последовательность, он не знал.

Дима подозревает, что он просто прослушал слово «правильная» в постановке задания, поэтому хочет срочно исправить ситуацию — для этого он решил немного изменить свою последовательность. А именно, он решил произвольное число раз (возможно, нулевое) выполнить операцию перемешивания.

Для выполнения одной операции перемешивания Дима выбирает произвольный подотрезок (подстроку) последовательности и произвольным образом переставляет все символы на нём. Такая операция занимает ровно l наносекунд, где l — длина подотрезка, который Дима выбрал для перемешивания. Легко заметить, что при этом число открывающих скобок не меняется, равно как и число закрывающих. Например, для «))((» он может выбрать подотрезок «)(» и перемешать символы в нём, получив «)()(» (эта операция потребует 2 наносекунды).

Уже совсем скоро подойдёт очередь Димы называть свою последовательность, поэтому он обратился за помощью к вам. Помогите ему определить минимальное время, за которое он может сделать свою последовательность правильной, или определите, что сделать это невозможно.

Код

#include <bits/stdc++.h>

using namespace std;

int main()
{
    char a;
    int  ans = 0, r = 0, s;
    cin >> s;
    for(int i = 0; i < s; ++i){
        cin >> a;
        if(a == '(')
            ++r;
        else{
            --r;
            if(r < 0)
                ++ans;
        }
    }
    if(!r) // if(l == 0)
        cout << ans * 2;
    else
        cout << -1;
    return 0;
}

         

Администратор Photo Автор: Администратор


Очевидно, что если число открывающих не равно числу закрывающих, то раз описанная операция не меняет их количество, получить правильную последовательность будет невозможно. Если же их число равно, можно взять всю строку и переставить в ней за n символы так, чтобы строка стала ПСП, например, «((((…))))».

Обозначим нашу последовательность за s[1]…s[n]. Тогда пусть pi — префиксный баланс на первых i символах, то есть разность между количеством открывающих и закрывающих.

Рассмотрим такой индекс i, что что bal[i]−1≤0, bal[i]<0, либо bal[i]−1<0, bal[i]≤0. Тогда, если символ s[i] не будет участвовать ни в одном перемешивании, то итоговая строка будет иметь i-й или i−1-й префиксный баланс отрицательным. Значит, как минимум символы с такими индексами i обязаны участвовать в хотя бы одной операции. Покажем далее, как использовать их и только их.

Изобразим данную скобочную последовательность как ломанную. Она будет начинаться в точке с координатами (0,0), заканчиваться в точке с координатами (2n,0), i-й вектор этой ломанной будет равен (+1,+1), если si= ( и (+1,−1) иначе. Тогда описанные выше индексы i, которые обязаны участвовать в хотя бы одной операции — это в точности все отрезки ниже линии x=0. Чтобы сделать последовательность правильной, все последовательные отрезки таких скобок развернём задом наперёд. Нетрудно видеть, что последовательность станет правильной.


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться