No.457 (^^*)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / タグ : / 解いたユーザー数 62
作問者 : butsuri_0523butsuri_0523 / テスター : はむこはむこ

4 ProblemId : 1414 / 出題時の順位表

Note

この問題はAdvent Calendar Contest Advent Calendar 2016の8日目の問題として作られました。

問題文

(^^*)はbさんが考えついた顔文字です。
(^^*)には左向きと右向きの2種類があります。

(^^*)が左向きで、
(*^^)が右向きです。
あなたは(^^*)たちを錬成する魔術師です。

あなたは'(','^','*',')'のみからなる文字列$S$から次のルールで(^^*)を錬成することができます。
$S$のうち任意の'('($S$の$a$文字目)、')'($S$の$e$文字目)を選び、
・間に'^'($S$の$b$文字目)、'^'($S$の$c$文字目)、'*'($S$の$d$文字目)($a < b < c < d < e$)があれば左向きの"(^^*)"が1つ、
・間に'*'($S$の$b$文字目)、'^'($S$の$c$文字目)、'^'($S$の$d$文字目)($a < b < c < d < e$)があれば右向きの"(*^^)"が1つ
錬成できます。

同じ文字は何度でも使用可能ですが、一つの'('')'の組み合わせから錬成出来るのは左向き、右向きそれぞれ1つです。
(つまり,同じ向きで$a$と$e$が同じ組み合わせのものを複数は錬成できません。)
組み合わせの順序を$(a,b,c,d,e)$とおくことにする。

例えば、

  • (*^^*)なら(1,3,4,5,6) と取ることにより (^^*)が、
    (1,2,3,4,6)から(*^^)がそれぞれ1つずつ錬成できます。
  • (*^^*^^*)なら (1,3,4,5,9) と取ることにより(^^*)は1つ、
    (1,2,3,6,9) と取ることにより (*^^)も1つ錬成できる
  • ((*^^)なら錬成できるのは(*^^)のみ2つ[(1,3,4,5,6) , (2,3,4,5,6) を選択して2つ]です。
(一例であるため、他に取り方は存在する)

錬成出来る左向きの最大数と右向きの最大数を求めてください。

入力

$S$

文字列$S$が1行に与えられます。
・制約
$S$は'(','^','*',')'のみからなる文字列
$1 \le |S| \le 10000$(但し$|S|$は文字列$S$の長さ)

出力

左向きの数と右向きの数をこの順に1行に空白区切りで出力してください。
出力の最後に改行が必要です。

サンプル

サンプル1
入力
(*^^*)
出力
1 1

問題文の1つめの例です。

サンプル2
入力
(*^^*^^*)
出力
1 1

問題文の2つめの例です。

サンプル3
入力
((*^^)
出力
0 2

問題文の3つめの例です。

サンプル4
入力
((^^*))
出力
4 0

サンプル5
入力
(*^^)*(^^*)
出力
2 2

サンプル6
入力
(
出力
0 0

そもそも5文字に満たない入力も考えられます。

サンプル7
入力
)^^)^^))^*)^^)^(^())^^(*^^)())(*^^)*^*^*)*^^())*((^^^(^^^^^(^^^^^((^^)^(())^**((*(*^((*^)(*^))*(^^^(
出力
87 102

提出ページヘ