← 返回题目列表

AtCoder · kupc2016_f

F. 速度求解

中文机器翻译题面 查看原题

问题陈述

京都大学的大猩猩数学很好。 他们目前正在尝试解决问题,以找到包含两个函数的表达式的值, _ , ^。 这些函数中的每一个都采用两个输入值。 _ 函数返回两个输入值中较小的一个, ^ 函数返回较大者。 大猩猩知道表达式中的整数是非负数并且小于或等于 99, 但直到他们读到一个终结符号才能找出表达式的长度 ? 表示表达式的结束。每个表达式包含的字符数小于或等于1000,但他们甚至不知道这个事实。 艾,一只聪明的大猩猩,注意到即使他们不读整个表达式,她也可能知道表达式的值。

例如,

假设您从左侧阅读以下句子。

^(41,3)?

当你读到第六个字符时,也就是读到下面的表达式时,

^(41,3

你可以判断函数的第二个输入值是否是 3 或之间的整数 30 和 39,结果是 41.

由于艾想比其他大猩猩更早地解决问题,她决定解决问题时从左侧读取尽可能少的字符。 对于每个表达式,找到表达式的值以及 Ai 需要读取才能知道该值的最小字符数。

约束

  • 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),打印表达式的值以及测试用例 Ai 需要读取的字符数 i 以空格分隔。


示例输入 1

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

示例输出 1

4 5
99 4
0 3
3 2
  • 对于第一个测试用例,当你读到第五个字符时,即当你读到 _(4,5,你会知道该值为 4.
  • 对于第二个测试用例,当读到第四个字符时,即读到 ^(99,你会知道该值为 99.
  • 对于第三个测试用例,当读到第三个字符时,即读到 _(0,你会知道该值为 0.
  • 对于第四个测试用例,您不会知道该值是 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

22 18
0 3
99 4
30 17
41 17
3 14
4 15