ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Max Alekseyev                        2:5015/60      22 Aug 2001  20:55:52
 To : All
 Subject : problem for $100
 -------------------------------------------------------------------------------- 
 

 
 http://members.aol.com/DrMWEcker/Contest.html
 
 ===cut===
                         *NEW Prize CONTEST!*
 
                                 *DARTS*
 
 *THE DARTS PROBLEM*
 
 Suppose that we have a dartboard that is divided into N areas. Each area has a
 positive integer value associated with it. You have three darts and you throw
 each of them at the dartboard. Each dart either lands in one of the board's N
 areas or misses the board altogether. Your score is the sum of the values for
 the areas in which the darts land. A dart that misses the board contributes
 nothing to your score. If multiple darts land in the same area, you accumulate
 the value for that area multiple times.
 
 For example, suppose N = 5 and the dartboard areas have values (1, 2, 4, 7, 11).
 If your three darts land in areas 2, 4 and 11 you score 17 points. If one dart
 misses the board and the other two land in area 7 you score 14 points.
 
 The Darts Problem is this: for a given N, determine what values should be
 associated with its N areas in order to maximize the smallest unattainable
 score.
 
 For example, again suppose that N = 5 and that the 5 areas have values (1, 2, 4,
 7, 11). Then the smallest unattainable score is 27. (That is, we can attain
 scores 0 through 26 but not 27.) But we can do better than 27. If we change the 
 values on the dartboard to (1, 4, 6, 14, 15) then the smallest unattainable
 score is 37.
 
 *THE CONTEST*
 
 Send us (see HOW TO ENTER, below) your best solutions to the Darts Problem for
 values of N from 1 to 25. The winning entry will be the one with the best
 solution for N = 1. In case of a tie (which is pretty likely) the tie will be
 broken by comparing solutions for N = 2. Continued ties will be broken by
 considering solutions for successively higher values of N. In the unlikely event
 of a tie after N = 25, the winner will be selected at random from among those
 tied.
 
 *THE PRIZES*
 
 First prize: One hundred dollars.
 
 Second prize: Choice of either WinFax or Norton Anti-Virus (provided courtesy of
 John Pilge).
 
 *HOW TO ENTER*
 
 Send an email containing your entry to bitzenbeitz@aol.com before Noon EDT on
 October 1, 2001. Put just the word DARTS in the subject line. The body of the
 email should be formatted as follows.
 
 The first line should contain your solution for N = 1. The second line should
 contain your solution for N = 2. And so forth through N = 25. Each such solution
 should be expressed as a list of N comma-delimited integers in ascending order
 representing the values on the dartboard. After your last solution leave a blank
 line. After that blank line provide your name and address. Your name and address
 can be in any human-readable format.
 
 Scoring will be done by computer, so be careful in composing your email.
 
 You may enter as often as you like, but only your best entry is eligible to win 
 a prize.
 
 *IF YOU HAVE QUESTIONS*
 
 If you have questions, check the FREQUENTLY ASKED QUESTIONS section, below. If
 your questions aren't answered there, send them to alzimmerma@aol.com .  If you 
 would like to receive copies of the questions I receive and of the responses
 (which could contain clarifications and/or corrections to the rules) send a
 request to the same address.
 
 *FREQUENTLY ASKED QUESTIONS*
 
 Can I assign the same value to more than one area of the dartboard?
 
 Yes. Multiple areas of the dartboard can have identical values. There is no
 requirement that each area have a unique value.
 
 In the example given, where N=5 and the dartboard areas have values (1, 2, 4, 7,
 11), I can score 33 by landing all three darts in area 11. So why is 27 the
 smallest unattainable score and not 34?
 
 It is not true that the smallest unattainable score is exactly one more than the
 largest attainable score. In the example, 33 is the largest attainable score.
 But there are a few scores smaller than 33 that are unattainable. To see that 27
 is unattainable, try to figure out where the 3 darts should land to score 27
 points - you'll find that it can't be done.
 
 Can you give an example of a valid entry?
 
 Sure. Here's my pet parrot's entry. (She's a real birdbrain, so her solution
 isn't very good. She's a mediocre typist too (mostly she just hunts and pecks), 
 but she formatted this perfectly.)
 
 1
 1,4
 1,4,7
 1,4,7,10
 1,4,7,10,13
 1,4,7,10,13,16
 1,4,7,10,13,16,19
 1,4,7,10,13,16,19,22
 1,4,7,10,13,16,19,22,25
 1,4,7,10,13,16,19,22,25,28
 1,4,7,10,13,16,19,22,25,28,31
 1,4,7,10,13,16,19,22,25,28,31,34
 1,4,7,10,13,16,19,22,25,28,31,34,37
 1,4,7,10,13,16,19,22,25,28,31,34,37,40
 1,4,7,10,13,16,19,22,25,28,31,34,37,40,43
 1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46
 1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49
 1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52
 1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55
 1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58
 1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58,61
 1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58,61,64
 1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58,61,64,67
 1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58,61,64,67,70
 1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58,61,64,67,70,73
 
 Harpo Zimmermann
 14 Aviary Lane
 Macaw, ME 01101
 
 How will I know that you've received my entry?
 
 When an entry is received it is immediately (that is, usually within 24 hours)
 processed by the automated Parser/Scorer and a confirmation is sent back to the 
 submitter. If the entry is valid, the confirmation contains the 25 Smallest
 Unattainable Scores calculated by the Scorer. If the entry is invalid, the
 confirmation explains why the Parser rejected it.
 
 My email software automatically inserts line breaks in long lines. Will this
 cause my entry to be rejected?
 
 Here at Darts Contest Galactic Headquarters we are a forgiving lot. If the
 Parser/Scorer rejects an entry but the submitter's intent is clear, we'll
 probably (depending on the effort involved) repair the entry. In particular, we 
 will always fix spurious line breaks inserted by your email software.
 ===cut===
 
 Regards,      ш.ш
         Max    ~
 
 --- FleetStreet 1.27.3.6
  * Origin:  (2:5015/60)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор