Al Zimmermann's Programming Contests - Son Of Darts

Al Zimmermann's Programming Contests 又開始新的比賽了, 基本上看名字就曉得它並不太在意你使用電腦程式與否(其實根本就是要用, 不然你會解到瘋掉)。以下是本次比賽的題目以及規則。

Started:  20 Jun 2009
Ends:  20 Jun 2010 16:00 

開始時間: 2009年6月20日
結束時間: 2010年6月20 日 16:00

The Darts Problem
擲鏢遊戲問題

Suppose that you have a dartboard that is divided into R regions. Each dartboard region has a positive integer value associated with it. Further suppose that you have D darts and that you throw each of them at the dartboard. Each dart either lands in one of the board's R regions or misses the board altogether. Your score is the sum of the values for the regions in which the darts land. A dart that misses the board contributes nothing to your score. If multiple darts land in the same region, you accumulate the value for that region multiple times.
嗯, 假設你有一個飛鏢靶, 上面被分成了 R 個區域, 每個鏢靶上的區域都有一個正整數, 代表你射到本區時的得分。接下來假設你也有幾支飛鏢, 數量為 D, 你可以把它們每支都丟到鏢靶上(譯批: 啊不然是拿來丟人嗎??)
每支鏢不是落在靶上 R 個區域其中之一, 就是射到外面去。你在這場射鏢遊戲的分數算法, 就是把每支?射中區域的分數做總計。什麼都沒射中的飛鏢, 當然無助於你分數的提升。如果你有多支鏢射中同一區域, 則每支鏢的分數照樣做累計。

For example, suppose that R = 5, that the dartboard regions have values (1, 2, 4, 7, 11), and that D = 3. If your three darts land in regions 2, 4 and 11 you score 17 points. If one dart misses the board and the other two land in region 7 you score 14 points.
舉例來說, 假設 R=5, 鏢靶上分成五個區域, 每區的分數為(1, 2, 4, 7, 11); 另外D=3。如果你的三支鏢分別擲中了分數為2,4,和11的區域, 那麼你的遊戲分數就是17分。要是其中一支鏢擲到了場外, 而另兩支都落在7分區, 你的分數就是14分。

The Darts Problem is this: for a given R and D, determine what values should be associated with a dartboard's R regions in order to maximize the smallest score unattainable by throwing D darts.
現在來說明擲鏢遊戲這道謎題的要求了: 對每一個我們給的R 與 D 的值, 請你決定你要給飛鏢靶這 R 個區域各幾分, 目標是 – 在使用 D 支鏢的情況下, 你『 不可能』得到的總分最少是多少, 然後你要想辦法調整 R 個區域的分數, 讓這個值盡可能地大。

For example, again suppose that R = 5 and D = 3. If you choose the values (1, 2, 4, 7, 11) for the board's 5 regions, then the smallest score unattainable with your 3 darts is 27. But if you choose the values (1, 4, 6, 14, 15) the smallest unattainable score is 37. The second choice of values is therefore a better choice for 3 darts and 5 regions.
舉例來說, 再一次我們假定 R=5 且 D=3。如果你還是在這五個區域給了(1, 2, 4, 7, 11)的配分, 那麼使用三支鏢的狀況下, 你『不可能』獲得的總分最小值是27。但如果你改給(1, 4, 6, 14, 15), 那麼這個『不可能』獲得的總分最小值就變成了37。顯然第二種分數配置方法在3鏢5區的狀況下, 比第一種來得好。

By the way, the Darts Problem is more commonly known as the Postage Stamp problem, wherein you are asked to determine which R denominations of stamps to issue in order to maximize the smallest postage unattainable with D stamps.
順便提及, 射鏢遊戲這款題目, 其實有另一個類似且更知名的題型, 稱為『貼郵票謎題』(譯注: 請參見 http://en.wikipedia.org/wiki/Postage_stamp_problem )。你被要求去決定R種郵票的面額, 在使用 D 張郵票的情況下, 你『不可能』湊成的郵資最少是多少, 然後你要想辦法調整 R 種郵票的面額, 讓這個值盡可能地大。

The Contest
比賽

Submit (see How to Enter, below) your best solutions to the Darts Problem for the following values of R and D:
在每個給定的 R 和 D 值, 輸入你最好的答案(如何輸入請往下看)

Thus, there are 100 problems and you are asked to submit 100 solutions. You can submit more than one solution for the same problem, but if you do we count only your best solution. There is no penalty for submitting multiple solutions for the same problem.
所以, 如上所示, 你有一百道問題要回答。相同的問題你可以輸入不只一次的答案, 我們會採計你最好的那一個。重覆輸入同一問題的答案不會有任何扣分。

See The Scoring System, below, to learn how we determine the winner.
看看下方的計分方式, 去想想你要怎麼做才能成為贏家。

The Prizes
The prizes are metal sculptures by Bathsheba Grossman. The 1st place winner has his pick from among the larger ones, and 2nd place chooses from the smaller.
獎品!!
獎品是由知名的Bathsheba Grossman 所設計的金屬雕刻品。冠軍挑一個大的, 而亞軍則選一個小的。

How to Enter
Just paste your solutions into the large box on the Submit page and click Submit. Format your solutions as follows:
An individual solution consists of
   a number (representing the number of darts), followed by
   a colon, followed by
   a comma-delimited list of region values.
Submit mulitple solutions in a single batch by separating them with semicolons. Do not place a semicolon after your last solution.
Include spaces and line breaks anywhere you like (except within a number) to improve readability.
There's an example of an entry in the Frequently Asked Questions section, below.

如何輸入答案
將你的答案貼上 Submit page 裏的空格中, 再按下 Submit。你答案的格式如下:
一道問題的答案必須先列出飛鏢的數量, 跟著輸入冒號(:), 然後再輸入各區的數值, 以逗號做區隔。
如果你一次要輸入多組題目的答案, 請將各組答案中間以分號(;)做區隔, 但是最後一道答案的尾端請別再輸入分號。
你可以在任何地方加上空格或是橫線(但不要加數字), 讓你的答案更易閱讀辨識。
在底下 Frequently Asked Questions section 的地方有個輸入答案的範例。

Do not submit entries under more than one account. This is important. Do not submit entries under more than one account.
不准用超過一個帳號輸入你的答案。這非常重要!! 不准用超過一個帳號輸入你的答案。

The Scoring System
Each time you submit a solution we will merge it with your prior solutions, if any. The result will be a virtual entry containing your best solutions for each of the 100 problems. We will give each of these 100 solutions a subscore from 0 to 1 and their sum will be your contest score.

計分方式
每當你輸入了一道題的答案, 我們會將它和之前你的答案做比較。你的回答包含了這一百道題中, 每道題你輸入最好的答案。而每道題都各自會有0到1之間的分數評分(包含小數), 它們的總和就是你的總。分。

We score the individual solutions as follows. If your solution is the best that was submitted for that problem, we give it 1 point; otherwise we give it only a fraction of a point. The fraction is the solution's smallest-unattainable-score divided by the best smallest-unattainable-score submitted any