Al Zimmermann's Programming Contests - Son Of Darts

地區:
分類:
標籤:
文字-A A +A

Logo 

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 值, 輸入你最好的答案(如何輸入請往下看)

D = number of darts R = number of dartboard regions
3 1 through 40
4 1 through 30
5 1 through 20
6 1 through 10

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

FB留言板

PeoPo 討論區

回應文章建議規則:

  • 文章屬於開放討論空間,回應文章的議題與內容不代表本站的立場
  • 於明知不實或過度謾罵之言論,本站及文章撰寫者保留刪除權
  • 請勿留下身份證字號、住址等個人隱私資料,以免遭人盜用,本站不負管理之責
  • 回應禁止使用HTML語法
prada

?校的力量,享受?生的美好?代。

祈求一顆天真的心

To 帕索大:
但是要去想那個思維, 還是很有趣的啊!!

To Cheng-Lin Tsao:
那是偶然心念一動的神來一筆翻譯, 其他的內容常常陷入拗口不通順的狀況。
不過還真的要謝謝你, 因為我在這句翻譯上一直抓不到它正確的概念, 反而會擔心自己是不是正好把意思弄反了。

Cheng-Lin Tsao

To Joky,

我們才該感謝你的翻譯,最後那句「我天才啊!!」我覺得超傳神的 :P

我稍微google了一下,postage stamp problem根本就是NP-hard problem
http://portal.acm.org/citation.cfm?doid=507457.507473
看起來只能用程式硬幹了 @@a

puzzlez

TO 北叔大:

對啊,我就是指像我這種不懂程式的人
只能夠乾瞪眼囉:-(

祈求一顆天真的心

To 帕索大:
我倒不覺得耶, 擅用程式的人應該很快就解出很棒的答案
只是哪種程式比較有效率的篩, 這才是要動腦的地方

To Cheng-Lin Tsao:
真的十分感謝, 您彌補了缺憾:)

Cheng-Lin Tsao

In case of a tie, preference is given to the entrant whose latest improved solution was submitted least recently.
平分狀況下,以較早上傳答案者為優勝(以最新的改善答案為準)

puzzlez

光看題目就昏了

如果是要用到電腦
那似乎一般人就很難參加了

100題!

比馬拉松還馬拉松

1

加入時間: 2007.06.06

祈求一顆天真的心

加入時間: 2007.06.06
157則報導
1則影音
0則OnTV

誰推薦本新聞

作者其他報導

PuzzleUp 2018

2018-07-26
瀏覽:
2,348
推:
0
回應:
0

[比賽] 2015 U.S. Puzzle Championship

2015-09-05
瀏覽:
1,844
推:
0
回應:
0

[比賽] WPF Puzzle Grand Prix 2015 - 第 8 場

2015-07-28
瀏覽:
1,441
推:
6
回應:
0

[比賽] WPF Sudoku Grand Prix 2015 - 第 8 場

2015-07-18
瀏覽:
1,817
推:
5
回應:
0

2013 Puzzleup 線上賽

2013-07-13
瀏覽:
1,229
推:
0
回應:
0

2012 U.S. Sudoku Team Qualifying

2012-09-01
瀏覽:
2,442
推:
0
回應:
5

US Puzzle Championship 2012

2012-08-25
瀏覽:
2,459
推:
0
回應:
2

[影片介紹]街舞狂潮

2010-11-08
瀏覽:
3,273
推:
0
回應:
0

特教影片 - 海洋天堂

2010-09-15
瀏覽:
5,540
推:
3
回應:
3

Al Zimmermann's Programming Contests - Son Of Darts

搜尋表單

目前累積了149,531篇報導,共11,257位公民記者

目前累積了149,531篇報導

11,257位公民記者