Problem A
一個棒球隊有 n 個投手, 要和 m 隊比賽 (m <= n <= 300),
每位投手只能出賽一場, 而且必須完投該場球賽.
題目給定每位投手對上每隊的勝率, 要找出最大的全勝機率.
每位投手的勝率只有 6 種: 0, 1/5, 2/5, 3/5, 4/5, 1.
輸入 p 代表勝率為 p/5, 輸出 a b c 代表最大全勝機率為 2^a * 3^b / 5^c.
Problem B
地底有許多礦坑, 而要挖某些礦坑時可能必須先挖上面的一些礦坑.
(意思就是礦坑的關係圖形成一個 directed acyclic graph)
我們可以預先測知挖每個礦坑所獲得的利潤 (有正有負),
題目要求我們找出能獲得的最大利潤及方法 (任何一種方法都可以).
Problem C
題目給定 xy 平面上的 5 ~ 7 個點, 要求我們求出最小方差二次曲線.
(意思就是要找出一個 f(x) = a x^2 + b x + c, 使 sigma (y_i - f(x_i))^2 最小)
Problem D
給定 affine linear 加密函數 f(x) = (ax + b) mod 26 (a 和 26 互質),
還有加密過後的密文, 要求解出解密函數 g(x) = (cx + d) mod 26, 並翻出明文.
Problem E
請 scwg 補充
Problem F
一直線上有 n 個點, 每個點都有 weight, 且相鄰的兩個點中間有邊相連,
在直線外有另一個點, 其 weight 是無限大, 並且和直線上的某些點相連.
我們要拿掉一些點, 使整個圖形變成 tree, 並使拿掉的總 weight 最小.
Problem G
請 scwg 補充
Problem H
有一些電腦，分佈在一直線上, 相鄰的電腦有邊相連,
每條邊有方向，例如 1 -> 2 代表電腦 1 可以傳資料給電腦 2.
另外，我們還有很多 jobs, 這些 jobs 也之間也有 directed edge 相連,
例如 1 -> 2 表示 job 1 和 job 2 必須在兩台電腦上運行,
而且 job 2 要依靠 job 1 傳過來的資料運作. 每台電腦可以同時許多 jobs.
題目目給定電腦的連接方式以及 jobs 的關係圖,
要我們判斷有沒有方法讓所有的 jobs 都能在電腦上運作.
Problem I
請 greenoyster 補充
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.46
※ 編輯: chhsiao 來自: 140.112.30.46 (10/17 00:32)