#XMOJ10142. 百万次提交

百万次提交

说明

时间限制:3 Sec 内存限制:256 MB 输入文件:submission.in 输出文件:submission.out

xmoj 上的提交次数超过了 100 万次,其中有 $m$ 个是多项式计算量的算法。

据调查,第 $i$ 个提交的程序,对于正的输入规模 $n$,其计算时间为 $n^{a_i} (\ln n)^{b_i}$ 秒($n$ 不一定是整数,$\ln n=\log_{e} n$ 表示自然对数)。此外,已知第 $i$ 个提交实际耗时为 $t_i$ 秒。  

每个提交都被认为是针对输入规模 $n$ 解决了问题。请找出所有可能的 $n$ 中最大的那个 $n$。

输入格式

第 1 行包含整数 \(m\)。

接下来 \(m\) 行,每行包含三个值 \(a_i\)、\(b_i\)、\(t_i\),分别表示:

- \(a_i\)、\(b_i\):整数,满足 \(0 \leq a_i, b_i \leq 10\),且 \(a_i\) 和 \(b_i\) 不同时为 $0$。

- \(t_i\):实数,范围为 \(0.1 \leq t_i \leq 10\),精确到小数点后 $4$ 位(即不会给出小数点后第 $5$ 位及以后的数字)。

输出格式

总共 $m$ 行,对于第 $i$ 行,输出第 $i$ 个提交所运行的规模 $n$ 中最大的那个值。

允许的误差为 $10^{-9}$ 以内。建议将答案控制在小数点后 $12$ 位以内输出。

样例

样例 1

3
2 0 9.0000
1 1 10.0000
0 1 2.0000

3
5.728925565387
7.389056098933

样例说明:

第 11 行:因为 (n^2 = 9),所以 (n = 3)。

第 $2$ 行:\(n \log_{e} n = 10\),其唯一解约为 \(n \fallingdotseq 5.728925565387\)。

第 $3$ 行:因为 \(\log_{e} n = 2\),所以 \(n = e^2 \fallingdotseq 7.389056098933\)。

数据范围

对于 20% 的数据,\(m \leq 10\)。

对于 40% 的数据,\(m \leq 100\)。

对于 60% 的数据,\(m \leq 1000\)。

对于 80% 的数据,\(m \leq 100000\)。

对于 100% 的数据,\(1 \leq m \leq 1000000\)。

对于所有 \(i\),\(a_i\) 和 \(b_i\) 不同时为 $0$。

\(t_i\) 的输入格式保证为最多 $4$ 位小数(例如可能为 $0.1$、$1.0005$ 等)。