問題一覧 > 通常問題

No.3144 Parentheses Modification and Rotation (01 Ver.)

レベル : / AI推定難易度 : 925 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 74
作問者 : nauclhlt / テスター : naniwazu
お気に入りにしたユーザー ProblemId : 12136 / 自分の提出
問題文最終更新日: 2025-05-15 08:29:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 467 (順位表) の他の問題:

Note

This problem has almost the same setting as Problem H. Only the constraints on $R, M$ differ. In this problem, $R=0, M=1$.

You can get AC by submitting a solution to Problem H as is.

Problem Statement

Definition of a balanced parenthesis sequence

A string $X$ is a balanced parenthesis sequence if it satisfies the following.

  • $X$ can be made into the empty string by repeating, $0$ or more times, the operation of deleting () contained in $X$ as a substring

For example, ()(()) and ()()()() are balanced parenthesis sequences, but ))(( and )()()( are not balanced parenthesis sequences.


There is a string $S$ of length $N$. Here, $S$ consists of ( and ).

nauclhlt is trying to turn $S$ into a balanced parenthesis sequence by repeating the following operation $0$ or more times.

Operation

  • Choose either a type $1$ or a type $2$ operation and perform it $1$ time.
    • Type $1$: Rotate $S$ to the right. Strictly speaking, replace $S$ with the string obtained by concatenating, in this order, the $N$-th character of $S$ and the string formed by taking the $1$-st through $N-1$-th characters of $S$. This operation costs $R$
    • Type $2$: Choose an integer $i$ satisfying $1\leq i\leq N$ and a character $c\in \lbrace $ ( $,$ ) $\rbrace$, and replace the $i$-th character of $S$ with $c$. This operation costs $M$

Determine whether nauclhlt can turn $S$ into a balanced parenthesis sequence by the operations, and if it is possible, find the minimum possible total cost.

Input

$N$
$S$
$R\ M$
  • $1\leq N\leq 10^5$
  • $S$ is a string of length $N$ consisting of ( and )
  • $N$ is an integer
  • $R=0, M=1$

Output

If it is possible to turn $S$ into a balanced parenthesis sequence, let $m$ be the minimum total cost, and print it on $1$ line in the following format.

$m$

If it is impossible, print -1.

$-1$

Print a newline at the end.

Sample

Sample 1
Input
6
)()()(
0 1
Output
0

For example, operating as follows turns $S$ into a balanced parenthesis sequence with a total cost of $0$.

  • Perform a type $1$ operation. $S$ becomes ()()()

Note that there may be multiple sequences of operations that achieve the optimal solution.

Sample 2
Input
4
)))(
0 1
Output
1

Example of a sequence of operations:

  • Perform a type $1$ operation. $S$ becomes ()))
  • Choose $i=3, c=$( and perform a type $2$ operation. This costs $1$, and $S$ becomes ()()
Sample 3
Input
6
(())((
0 1
Output
1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。