F - 早解き

コンテスト時間: 2016-10-02 13:00:00+0900 ~ 2016-10-02 18:00:00+0900 (300分)

F - 早解き解説

実行時間制限: 1 sec / メモリ制限: 256 MB

配点 : 150 点

問題文

京都大学で飼育されているゴリラ達は数学が得意である。彼らは今、 2 つの関数 _、 ^ を含む式の値を求める問題を解いている。これらの関数は 2 入力関数であり、 _ 関数は入力の小さい方の値を、 ^ 関数は大きい方の値を出力する。ゴリラ達は、式の中に現れる整数が 0 以上 99 以下であることは知っているが、式の長さは終端を表す記号 ? を読むまでわからない。それぞれの式に含まれる文字数は 1000 文字以下であるが、そのことも知らない。優等生ゴリラのアイちゃんは、式を全て読まなくても式の値がわかることがあることに気づいた。

例えば、

^(41,3)?

という式を左から順に読んでいくと、 6 文字目まで読んだ時点、つまり

^(41,3

まで読んだ時点で、関数の2番目の入力が3 もしくは 30 以上 39 以下であることがわかるため、式の値は 41 であることが確定する。

アイちゃんは他のゴリラより早く問題を解きたいので、先頭から１文字ずつ読んでいき、式の値が分かった時点でその問題を読むのをやめることにした。それぞれの式について、式の値とアイちゃんが読む必要のある文字数の最小値を求めよ。

制約

1 \leq Q \leq 200
それぞれの式に含まれる文字数は 1000 以下である。

入力

入力は複数のテストケースからなり、以下の形式で標準入力から与えられる。

Q
statement_1
...
statement_Q

各 statement_i (1 \leq i \leq Q) は、以下の BNF の形式で与えられる。

<statement> ::= <expression> ?
<expression> ::= (^ | _)  ( <expression> , <expression> ) | <number> 
<number> :: = 0 | 1 | 2 | ... | 98 | 99

出力

出力は Q 行からなる。 i (1 \leq i \leq Q) 行目には i 番目のテストケースにおける式の値と、読む必要のある文字数の最小値を空白区切りで出力せよ。

入力例1

4
_(4,51)?
^(99,_(3,67))?
_(0,87)?
3?

出力例1

1 番目の例では、 5 文字目を読んだ時点、つまり _(4,5 の時点で式の値が 4 であるとわかる。
2 番目の例では、 4 文字目を読んだ時点、つまり ^(99 の時点で式の値が 99 であるとわかる。
3 番目の例では、 3 文字目を読んだ時点、つまり _(0 の時点で式の値が 0 であるとわかる。
4 番目の例では、終端記号を読み込むまで式の値が 3 であるとわからない。

入力例2

7
_(23,^(_(22,40),4))?
_(0,99)?
^(99,_(^(19,2),5))?
_(^(43,20),^(30,29))?
^(_(20,3),_(50,41))?
^(_(20,3),_(3,41))?
^(_(20,3),_(4,41))?

出力例2

Score : 150 points

Problem Statement

Gorillas in Kyoto University are good at math. They are currently trying to solve problems to find the value of an expression that contains two functions, _ , ^. Each of these functions takes two input values. _ function returns the smaller of the two input values and ^ function returns the larger. Gorillas know that integers in the expression are non-negative and less than or equal to 99, but can not find out the length of the expression until they read a terminal symbol ? that represents the end of the expression. The number of characters included in each expression is less than or equal to 1000, but they do not even know this fact. Ai, a smart gorilla, noticed that she may be able to know the value of the expression even if they don't read the whole expression.

For example,

Assume you read the following sentence from the left.

^(41,3)?

When you read the sixth character, that is, when you read the following expression,

^(41,3

you can tell the second input value of the funcion is whether 3 or an integer between 30 and 39, and the value turns out 41.

Since Ai wants to solve problems earlier than other gorillas, she decided to solve the problems such that she reads as fewer characters as possible from the left. For each expression, Find the value of the expression and the minimum number of characters Ai needs to read to know the value.

Constraints

1 \leq Q \leq 200
The number of characters each expression contains is less than or equal to 1000.

Input

The input consists of multiple test cases and is given from Standard Input in the following format:

Q
statement_1
...
statement_Q

Each statement_i (1 \leq i \leq Q) is given in the following BNF format.

<statement> ::= <expression> ?
<expression> ::= (^ | _)  ( <expression> , <expression> ) | <number> 
<number> :: = 0 | 1 | 2 | ... | 98 | 99

Output

Output consists of Q lines. On line i (1 \leq i \leq Q), print the value of the expression and the number of character Ai needs to read for the test case i separated by space.

Sample Input 1

4
_(4,51)?
^(99,_(3,67))?
_(0,87)?
3?

Sample Output 1

For the first test case, when you read the fifth character, that is, when you read _(4,5, you will know the value is 4.
For the second test case, when you read the fourth character, that is, when you read ^(99, you will know the value is 99.
For the third test case, when you read the third character, that is, when you read _(0, you will know the value is 0.
For the fourth test case, you will not know the value is 3 untill you read the terminal symbol.

Sample Input 2

7
_(23,^(_(22,40),4))?
_(0,99)?
^(99,_(^(19,2),5))?
_(^(43,20),^(30,29))?
^(_(20,3),_(50,41))?
^(_(20,3),_(3,41))?
^(_(20,3),_(4,41))?

Sample Output 2

出典

KUPC2016