※ 引述《JonathanWang (小尹)》之銘言：
: Contest standings
: Name Solved Score A B C D E F G H att/solv
: 1 Escape 4 407 1/124 2/-- 2/-- 2/-- 2/174 1/27 1/62 0/-- 11/4
: 2 ( ] 3 339 2/110 3/-- 0/-- 0/-- 5/-- 5/109 1/20 0/-- 16/3
: 3 NULL 3 339 1/140 0/-- 2/-- 0/-- 0/-- 1/115 2/64 0/-- 6/3
: 4 Wall 3 535 1/238 2/-- 0/-- 0/-- 2/-- 3/160 1/97 2/-- 11/3
: 5 KSR 1 208 0/-- 2/-- 0/-- 0/-- 0/-- 0/-- 1/208 0/-- 3/1
: Summary 5/4 9/0 4/0 2/0 9/1 10/4 6/5 2/0 47/14
: http://acmclub.csie.org/problem/acm/regional/2002/Europe/SouthEasternEurope/
這是 2002 東南歐的題目, 同時在 uva online judge archive 裡
http://acm.uva.es/archive/data/2002eu06.php
同時也是浙江大學 online judge 的 1366~1373
http://acm.zju.edu.cn/list_problem.php?vol=4
若我沒記錯的話, Wall 這隊在比賽後開始 20~30 分鐘左右隊員還沒到齊
因此由 ledia 加入, 又過了一些時間又增加一人湊滿三人一隊
今天 Wall 隊充當 judge
A 是有限數量湊零錢問題, n 種幣值, 幣值 d_i 有 n_i 枚, 問湊 cash 最近可以多近
n<=10, n_i<=1000, cash<=100000
若把多枚硬幣當作多種幣值, 可以 DP O(cash*n_i*n) 10^9
其實可以做到 O(cash*n) 10^6
不過測試數據可能不夠好(?), 用 10^9 一樣可以跑出來
B 數學, 大家都找不出偶數的公式
C 排程相關
D 幾何題, 平面上 n 簡單多邊形, 想像成房間跟牆, 問房內能看到全部房間而無死角
的面積多少
Escape 有做這題, 但還沒做出來
E 兩層 DP 求機率, ( ] 隊只錯最後一組資料, 在練習賽結束後解出來
F 模擬
G MST
H 線性代數問題, 解法可能跟同餘系 matrix/inverse/determine 有關
題目有怪條件: sly number in set {0,1,2} 不知道怎麼用
從 standing 上看起來, 與當時的隊伍比較, Escape 是解四題中最快的
排名 11
第一名解六題, 而第六名五題最快只有 378 penalty
網路上找不到各題解題分布
猜測他們多的題目可能是 D 跟 B
--
"聲音是聲音, icon 是 icon, 用 icon 來表示聲音的結果,
就是不知道哪個是聲音, 哪個是 icon. "
小光光
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.70.142.187