配点 : 100 点
問題文
正整数 N 关于的函数 F(N) 接下来的 BNF 表示法 可以得到第 <expr> 符号遵循的字符串 F 。
<expr> ::= <term> | <expr> "+" <term>
<term> ::= <factor> | <term> "*" <factor>
<factor> ::= "N" | "N^" <number> | "log(" <expr> ")" | "log(" <expr> ")^" <number> | "(" <expr> ")"
<number> ::= <non_zero_digit> | <non_zero_digit> <digit_string>
<digit_string> ::= <digit> | <digit> <digit_string>
<non_zero_digit> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<digit> ::= "0" | <non_zero_digit>
符号分别表示以下含义。
N: N+:加法 +*:乘法 \timeslog: 自然対数 \log(,):括号,但加法+或乘法*比...先计算^:幂运算,但加法+或乘法*比...先计算
<number> 表示十进制整数, 1 以上 10^9 保证不超过以下。 "log(" <expr> ")^" <number> 是
您也可以写 (\log( \text{<expr>} ))^{ \text{<number>} } 。
例如,以下的字符串是 <expr> 符号。
N+log(N)*N- N + \log(N) \times N 。
N^1+N^2+log(N)+log(N)^1000000000- N^1 + N^2 + \log(N) + (\log(N))^{1000000000} 。
N*(N+(log(N+N)^2*N))+(((N)))- N \times (N + (\log(N+N))^2 \times N) +(((N))) 。
(log((N)))- (\log((N))) 。
另外,以下的字符串是 <expr> 符号。
(log(N)+N)^2<factor>中, 输出"(" <expr> ")^" <number>不会使用。
(log(N))^2(N)N(N^1000000001N^02N^0N^N2log(3)N-log(N)log(N)/N
正整数 N 根据情况 F(N) 不一定会被定义,但可以证明,对于任何输入,所有满足某个正整数 N_0 存在, 由 N \geq N_0 的正整数 N 在 F(N) 都可以被定义。
因此,极限
\[ \lim_{N \to \infty} \frac{F(N)}{N^a(\log N)^b} \]
收敛到有限值( 0 包括在内)的非负整数 (a, b) 的所有组合的集合为 S 。 S 可以得到第字典序最小的组合请输出
其中,非负整数的组合 (a, b) 是 在 S 的字典序最小组合是指, (a, b) 是 在 S 属于,并且进一步 S 属于的任意组合 (a', b') 我们假设以下任意一种情况成立。
- a < a'
- a = a' 和 b \le b'
在这里, S 不是空集,并且可以证明 S 的字典序最小组合存在。
制約
- 関数 F(N) 作为问题中所示的 BNF 表示法的
<expr>符号遵循的字符串 F 给出 - 1 \leq |F| \leq 10^5
部分点
- 额外约束“F 作为子字符串不包含
log”的数据集时,正确答案是 30 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
F
出力
S 字典序最小的组合 (a, b) 以空格分隔。
入力例 1
N*log(N^2)*log(N)+N+log(N^1+N)^2*N
出力例 1
1 2
F(N) = N \times \log(N^2) \times \log(N) + N + (\log(N^1+N))^2 \times N 。
此时,题目中所示的极限收敛到有限值的非负整数组 (a, b) 是 您也可以写 (a, b) = (1, 2), (1, 3), (2, 0) 等等。对于这些,极限如下。
\[ \lim_{N \to \infty} \frac{F(N)}{N^1 (\log N)^2} = 3 \]
\[ \lim_{N \to \infty} \frac{F(N)}{N^1 (\log N)^3} = 0 \]
\[ \lim_{N \to \infty} \frac{F(N)}{N^2 (\log N)^0} = 0 \]
0 请注意,它也应是有限值。另一方面,例如 (a, b) = (1, 1) 对于
\[ \lim_{N \to \infty} \frac{F(N)}{N^1 (\log N)^1} = \infty \]
,它不会收敛到有限值。
满足条件的所有组合的集合 S 中 找出满足 (a, b) = (1, 2) 可以证明是字典序最小的。这个情况不满足部分点的约束。
入力例 2
N*log(log(N))
出力例 2
1 1
F(N) = N \times \log( \log(N)) 。 (a, b) = (1, 1) 反对
\[ \lim_{N \to \infty} \frac{F(N)}{N^1 (\log N)^1} = 0 \]
并收敛到有限值。
满足条件的所有组合的集合 S 中 找出满足 (a, b) = (1, 1) 可以证明是字典序最小的。这个情况不满足部分点的约束。
入力例 3
(((N))*N^234567890+N^2)
出力例 3
234567891 0
F(N) = \left(((N))\times N^{234567890}+N^2\right) 。该情况满足部分分约束。