相信大家知道最後一天 day-5 的程式競賽是團體賽了,而如果在這種競賽裡有一題是關於程式競賽團體賽的問題,那麼這一題就可以叫作「程式競賽團體賽中的程式競賽團體賽問題」。你猜的沒錯!這一題就是一題有關於程式競賽團體賽的問題。
你和其他兩個小夥伴組隊,參加了一個團體的程式競賽。這個程式競賽有 $N$ 題,因為你們特別電,你們的目標不僅是拿第一,還要破台(解出所有題目)。而如果其他隊伍也解出所有題目了,那就要比 penalty(罰時),因此你們也希望 penalty 越小越好。這個程式競賽的 penalty 算法比較特別,定義為解出最後一題時的時間(類似 codejam,而且因為你們一定一次 AC(Accept,解出題目),所以也不用考慮因為沒有 AC 而加的額外 penalty 了)。總而言之你們希望在解出所有題目的情況下,penalty 越小越好。
你們很快的看完了所有題目,並且知道每一題是什麼題型。因為你們三個人擅長的題型不一樣,你們決定仔細分析一下來決定每個人花在每一題的時間。在競賽中任何時候你們可以分別做不同題,也可以合作做同一題。而對於第 $i$ 題,你們之中的第 $j$ 個人有一個值 $a_{i, j}$ 表示這個人單獨做這一題只需要 $a_{i, j}$ 秒的時間就可以 AC,也就是說這個人 1 秒可以對這一題貢獻 $1 / a_{i, j}$。而且因為你們合作無間,三個人對同一題的貢獻值可以直接相加,不論你們是同時還是分別做這一題。換句話說,如果你們三個人分別在這一題上面花了 $t_1, t_2, t_3$ 秒(這些數字可以是任意非負實數,如 $1.23$),那你們對這一題的貢獻值總合就是 $t_1 / a_{i, 1} + t_2 / a_{i, 2} + t_3 / a_{i, 3}$,而如果這個值大於等於 1 就表示你們將這一題解出來了。
現在你們知道所有的 $a_{i, j}$ 了,請問你們在最佳的分配方式下,最少花多少時間可以破台?
第一行有唯一的一個正整數 $N$ 表示題目的數量。
接下來有 $N$ 行,第 $i$ 行有三個正整數 $a_{i, 1}$, $a_{i, 2}$, $a_{i, 3}$ 表示每個人單獨做這一題需要多久。
輸出 $1$ 行上面有且僅有一個數字 $t$ 表示在最佳策略下,最少要花多少時間。只要你的輸出和答案絕對或相對誤差小於 $10^ {-6}$ 即算正確。
對於第一筆範例測資,你們三個人各有一題比較擅長的題目。因此你們第 $i$ 個人就做第 $i$ 道題,每個人花 1 秒就可以解出,於是你們就「秒」破台了。
對於第二筆範例測資,最佳策略是第 $i$ 個人分別做第 $i$ 題,1 秒後第 1 和 2 個人都把題目做出來了,而第 3 個人把第 3 題做了 $1/3$。接著你們一起合作第 3 題,再花 1 秒後你們加起來又貢獻了 $1/3 + 1/6 + 1/6 = 2/3$,因此就把這一題做出來了,總共花了 2 秒。
No. | Testdata Range | Score |
---|---|---|
1 | 0~23 | 1 |