No.457 (^^*)
タグ : / 解いたユーザー数 162
作問者 :
butsurizuki
/ テスター :
はむこ
Note
This problem was created as the problem for day 8 of Advent Calendar Contest Advent Calendar 2016.
Problem Statement
(^^*) is an emoticon devised by b-san.
(^^*) comes in two types: left-facing and right-facing.
(^^*) is left-facing, and
(*^^) is right-facing.
You are a sorcerer who transmutes (^^*)s.
You can transmute (^^*)s from a string $S$ consisting only of '(','^','*',')' according to the following rules.
Choose any '(' (the $a$-th character of $S$) and any ')' (the $e$-th character of $S$) in $S$. Then,
・if there are '^' (the $b$-th character of $S$), '^' (the $c$-th character of $S$), and '*' (the $d$-th character of $S$) between them ($a < b < c < d < e$), one left-facing "(^^*)",
・if there are '*' (the $b$-th character of $S$), '^' (the $c$-th character of $S$), and '^' (the $d$-th character of $S$) between them ($a < b < c < d < e$), one right-facing "(*^^)"
can be transmuted.
The same character may be used any number of times, but from one combination of '(' and ')' you can transmute at most one left-facing and one right-facing emoticon each.
(That is, you cannot transmute multiple emoticons of the same facing with the same combination of $a$ and $e$.)
We denote the order of a combination as $(a,b,c,d,e)$.
For example,
- from
(*^^*), taking (1,3,4,5,6) gives (^^*), and
(1,2,3,4,6) gives (*^^), so one of each can be transmuted. - from
(*^^*^^*), taking (1,3,4,5,9) gives one (^^*), and
taking (1,2,3,6,9) gives one (*^^) as well. - from
((*^^), only (*^^) can be transmuted, and two of them [two by choosing (1,3,4,5,6) and (2,3,4,5,6)].
Find the maximum number of left-facing emoticons and the maximum number of right-facing emoticons that can be transmuted.
Input
$S$
The string $S$ is given on one line.
・Constraints
$S$ is a string consisting only of '(','^','*',')'
$1 \le |S| \le 10000$ (where $|S|$ is the length of the string $S$)
Output
Print the number of left-facing emoticons and the number of right-facing emoticons in this order on one line, separated by a space.
A newline is required at the end of the output.
Sample
Sample 1
Input
(*^^*)
Output
1 1
This is the first example in the problem statement.
Sample 2
Input
(*^^*^^*)
Output
1 1
This is the second example in the problem statement.
Sample 3
Input
((*^^)
Output
0 2
This is the third example in the problem statement.
Sample 4
Input
((^^*))
Output
4 0
Sample 5
Input
(*^^)*(^^*)
Output
2 2
Sample 6
Input
(
Output
0 0
Inputs with fewer than 5 characters are also possible.
Sample 7
Input
)^^)^^))^*)^^)^(^())^^(*^^)())(*^^)*^*^*)*^^())*((^^^(^^^^^(^^^^^((^^)^(())^**((*(*^((*^)(*^))*(^^^(
Output
87 102
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。