← 返回题目列表

AtCoder · ttpc2023_f

F. N的a次方乘以log N的b次方

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

配点 : 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
  • + :加法 +
  • * :乘法 \times
  • log : 自然対数 \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^1000000001
  • N^02
  • N^0
  • N^N
  • 2
  • log(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) 。该情况满足部分分约束。