HMMT 二月 2007 · 冲刺赛 · 第 35 题

英文解析

35. [ ≤ 25 ] The Algorithm. There are thirteen broken computers situated at the following set S of thirteenpoints in the plane:
    A = (1 , 10) B = (976 , 9) C = (666 , 87)
    D = (377 , 422) E = (535 , 488) F = (775 , 488)
    G = (941 , 500) H = (225 , 583) I = (388 , 696)
    J = (3 , 713) K = (504 , 872) L = (560 , 934)
    M = (22 , 997)
    At time t = 0, a repairman begins moving from one computer to the next, traveling continuously instraight lines at unit speed. Assuming the repairman begins and A and fixes computers instantly, whatpath does he take to minimize the total downtime of the computers? List the points he visits in order.
    Your score will be b c , where n
    N = 1000 + b the optimal downtime c − b your downtime c ,40
    or 0, whichever is greater. By total downtime we mean the sum
    ∑
    t ,
    P ∈ SPwhere t is the time at which the repairman reaches P .12
    Answer: ADHIKLEFGBCJM . This is an instance of the minimum-latency problem, which is at pleast NP-hard. There is an easy O ( n !) algorithm, but this is unavailable to teams on computationalgrounds (100MHz calculators used to seem fast...) The best strategy may be drawing an accuratepicture and exercising geometric intuition. The distribution of the points somewhat resembles a short,
    four-pronged fork with its outermost prongs bent apart; it is plausible to assume that the optimal orderrespects this shape. The optimal downtime is 24113.147907, realized by ADHIKLEFGBCJM, thougha number of others also receive positive marks.