問題一覧 > 通常問題

No.456 Millions of Submits!

レベル : / 実行時間制限 : 1ケース 4.500秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-9}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 61
作問者 : はむこはむこ / テスター : りあんりあん
5 ProblemId : 1451 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-12-11 10:11:25

問題文

競技プログラマは有史以来、幾百万の提出をしてきた。
Atcoderでは100万以上の提出がなされ、そのうち$m$個が多項式計算量のアルゴリズムだったという。

調査によると、$i$番目に提出されたプログラムは、
正の入力サイズ$n$に対して、計算時間が$n^{a_i} \log^{b_i} n$秒かかるという(nは整数とは限らない。logは自然対数)。
また、$i$番目の提出は、実際には$t_i$秒かかったこともわかっている。

各提出は、入力サイズnに対して解かれたという。考えられるnのうち、最大のnを求めよ。

入力

m
a_1 b_1 t_1
...
a_m b_m t_m

$1 \leq m \leq 1000000$、整数。
$0 \leq a_i, b_i \leq 10$、整数。
全ての$i$について、$a_i$と$b_i$のどちらかは$0$ではない。
$0.1 \leq t_i \leq 10$、小数点以下第4桁まで与えられる(小数点以下第5桁以上は与えられない)。

出力

全部で$m$行、$i$行目に$i$番目の提出に走らせたサイズ$n$のうち、最大の$n$を出力せよ。
誤差は$10^{-9}$まで許容される。最後に改行せよ。

出力サイズ制限のため、小数点以下12桁より多く出すと、OLE(Output Limit Exceed)する可能性がある。
小数点以下12桁以内で答えを出力することを勧める。

NOTE

高速な言語を利用することを推奨する。C++とC#で通ることは確認している。
出力サイズの仕様上最後のケースのジャッジに非常に時間が掛かる可能性がありますのでご了承ください。

サンプル

サンプル1
入力
3
2 0 9.0000
1 1 10.0000
0 1 2.0000
出力
3
5.728925565387
7.389056098933

1行目は、$n^2 = 9$なので、$n=3$です。
2行目は、$n \log n = 10$です。これは唯一の解を$n \fallingdotseq 5.728925565387$に持ちます。
3行目は、$\log n = 2$なので、$n=e^2 \fallingdotseq 7.389056098933$です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。