AT_ttpc2023_f N^a (log N)^b
题目描述
对于正整数 $N$，函数 $F(N)$ 以一个符号串 $F$ 给出，符号串 $F$ 满足如下 [BNF 表记](https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%83%E3%82%AB%E3%82%B9%E3%83%BB%E3%83%8A%E3%82%A6%E3%82%A2%E8%A8%98%E6%B3%95) 中 `` 符号的定义。
```
::= | "+"
::= | "*"
::= "N" | "N^" | "log(" ")" | "log(" ")^" | "(" ")"
::= |
::= |
::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
::= "0" |
```
每个记号含义如下：
- `N`：表示 $N$
- `+`：加法 $+$
- `*`：乘法 $\times$
- `log`：自然对数 $\log$
- `(`, `)`：括号，括号内的内容优先于加法 `+` 和乘法 `*` 计算
- `^`：乘方运算符，优先级高于加法 `+` 和乘法 `*`
`` 表示十进制整数，保证 $1 \leq \text{} \leq 10^9$。其中 `"log(" ")^" ` 表示 $ \left(\log(\text{})\right)^{\text{}} $。
例如，下列字符串可以作为 `` 符号：
- `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)))$。
相反，下列字符串不是 `` 符号：
- `(log(N)+N)^2`
- 在 `` 内不允许 `"(" ")^" ` 形式。
- `(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$ 的正整数，$F(N)$ 都有定义。
令极限
\[
\lim_{N \to \infty} \frac{F(N)}{N^a (\log N)^b}
\]
能够收敛于有限值（包括 $0$）的所有非负整数对 $(a,b)$ 的集合记为 $S$。请输出 $S$ 的**字典序最小的对**。
即，假设非负整数对 $(a, b)$ 属于 $S$，并且对于任意 $(a', b') \in S$，满足如下之一：
- $a < a'$
- $a = a'$ 且 $b \le b'$
则 $(a, b)$ 是 $S$ 的字典序最小对。
可以证明 $S$ 非空且其字典序最小的对存在。
输入格式
输入通过标准输入给出：
> $F$
输出格式
请输出 $S$ 的字典序最小的对 $(a, b)$，以空格分隔。
说明/提示
## 部分分
- 对于附加约束“$F$ 不包含部分字符串 `log`”的数据集，若正确解答，则可获得 $30$ 分。
## 样例解释 1
$F(N) = N \times \log(N^2) \times \log(N) + N + (\log(N^1+N))^2 \times N$。
此时使得极限收敛到有限值的非负整数对 $(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
$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
$F(N) = \left(((N))\times N^{234567890}+N^2\right)$。本组数据满足部分分约束。
# 数据范围
- $F(N)$ 表达式为题目中给出的 BNF 记法 `` 符号的字符串
- $1 \leq |F| \leq 10^5$
由 ChatGPT 5 翻译