TopCoder

Thumb qz2vnqoblj6vp6q
miku
https://chino.taipei

User's AC Ratio

92.3% (24/26)

Submission's AC Ratio

60.5% (26/43)

Tags

Description

「有時候,遇見一株美麗的樹的心情無法確切形容,但我知道我必是非常的歡喜。如此生活的微末細枝,激盪我心情的能量卻是相當巨大的。」

──王家祥《遇見一株樹》

樹有許多美麗的性質,為了多觀察、並且紀錄我們遇過的樹,我們決定利用一種括弧表示法來記錄一棵樹。這樣一來,不僅節省了空間,整理起來也很方便。例如你看到了一棵這樣子的樹:


我們可以把它化簡為:
(*(**)(*))
其中每一個'*'號都代表著一片葉子,一對括弧代表一個樹枝的分叉點。

為了將各式各樣的樹做妥善的分類以利保管,我們得先知道每棵樹具有什麼樣子的性質。
例如上圖當中的樹,我們可以知道該樹有4片葉子,而且深度為3(depth = 3),並且是一棵三元樹(3-ary tree),原因是該樹當中的每個點最多分岔出三顆子樹。

給你一棵樹,請你回答出該樹的葉子個數、深度以及此樹為一棵幾元樹。

Input Format

輸入檔可能包含多筆測試資料,每一筆資料佔一列代表一棵樹。你可以假設所有測試資料當中的樹都是合法表示的,一棵樹當中不會有空白的出現。每棵樹的長度不會超過100,000個字元。

Output Format

對於每筆測試資料請輸出三個數值,依序是葉子個數、深度以及此樹為幾元樹。

Sample Input

*
((((((*))))))
(*******)
(*(**)(*))

Sample Output

1 1 0
1 7 1
7 2 7
4 3 3

Hints

Problem Source

原TIOJ1106 / 經典問題練習。Problem Setter: tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536