TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

97.4% (113/116)

Submission's AC Ratio

53.3% (130/244)

Tags

Description

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

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

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


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

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

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

Input Format

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

Output Format

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

Sample Input 1

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

Sample Output 1

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

Hints

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1