TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

50.0% (2/4)

Submission's AC Ratio

50.0% (6/12)

Tags

Description

相信大家知道最後一天 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}$ 了,請問你們在最佳的分配方式下,最少花多少時間可以破台?

Input Format

第一行有唯一的一個正整數 $N$ 表示題目的數量。
接下來有 $N$ 行,第 $i$ 行有三個正整數 $a_{i, 1}$, $a_{i, 2}$, $a_{i, 3}$ 表示每個人單獨做這一題需要多久。

  • $1 \le N \le 10^ 5$
  • $1 \le a_{i, j} \le 18000$

Output Format

輸出 $1$ 行上面有且僅有一個數字 $t$ 表示在最佳策略下,最少要花多少時間。只要你的輸出和答案絕對或相對誤差小於 $10^ {-6}$ 即算正確。

Sample Input 1

Sample input #1

3
1 100 100
100 1 100
100 100 1

Sample Output 1

1

Sample Input 2

3
1 2 3
2 1 3
6 6 3

Sample Output 2

2



Hints

對於第一筆範例測資,你們三個人各有一題比較擅長的題目。因此你們第 $i$ 個人就做第 $i$ 道題,每個人花 1 秒就可以解出,於是你們就「秒」破台了。

對於第二筆範例測資,最佳策略是第 $i$ 個人分別做第 $i$ 題,1 秒後第 1 和 2 個人都把題目做出來了,而第 3 個人把第 3 題做了 $1/3$。接著你們一起合作第 3 題,再花 1 秒後你們加起來又貢獻了 $1/3 + 1/6 + 1/6 = 2/3$,因此就把這一題做出來了,總共花了 2 秒。

Problem Source

Subtasks

No. Testdata Range Score
1 0~23 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 6000 262144 262144 1
1 6000 262144 262144 1
2 6000 262144 262144 1
3 6000 262144 262144 1
4 6000 262144 262144 1
5 6000 262144 262144 1
6 6000 262144 262144 1
7 6000 262144 262144 1
8 6000 262144 262144 1
9 6000 262144 262144 1
10 6000 262144 262144 1
11 6000 262144 262144 1
12 6000 262144 262144 1
13 6000 262144 262144 1
14 6000 262144 262144 1
15 6000 262144 262144 1
16 6000 262144 262144 1
17 6000 262144 262144 1
18 6000 262144 262144 1
19 6000 262144 262144 1
20 6000 262144 262144 1
21 6000 262144 262144 1
22 6000 262144 262144 1
23 6000 262144 262144 1