MathDB
2007 Guts #35: The Algorithm

Source:

June 22, 2012
algorithmfloor function

Problem Statement

The Algorithm. There are thirteen broken computers situated at the following set SS of thirteen points 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)\begin{array}{ccc}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)&\end{array}
At time t=0t=0, a repairman begins moving from one computer to the next, traveling continuously in straight lines at unit speed. Assuming the repairman begins and AA and fixes computers instantly, what path does he take to minimize the total downtime of the computers? List the points he visits in order. Your score will be N40\left\lfloor \dfrac{N}{40}\right\rfloor, where N=1000+the optimal downtimeyour downtime,N=1000+\lfloor\text{the optimal downtime}\rfloor - \lfloor \text{your downtime}\rfloor , or 00, whichever is greater. By total downtime we mean the sum PStP,\sum_{P\in S}t_P, where tPt_P is the time at which the repairman reaches PP.