#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
样例说明:
第 行:因为 (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$ 等)。
相关
在下列比赛中: