CCC '00 S4 - Golf

View as PDF

Submit solution


Points:10
Time limit:2.0s
Memory limit:16M

Problem type

Canadian Computing Competition: 2001 Stage 1, Senior #4

Roberta the Robot plays a perfect game of golf. When she hits the golf ball it always goes directly towards the hole on the green, and she always hits exactly the distance that is specified for the club. Each such action is known as a stroke, and the object of golf is to hit the ball from the tee to the hole in the fewest number of strokes. Roberta needs a program to select the best combination of clubs to reach the hole in the fewest strokes. She also needs to decide if the task is impossible, in which case she graciously acknowledges the loss. Roberta can carry up to 32 clubs, and the total distance from the tee to the hole does not exceed 5\,280 metres.

Input Specification

The first line of input gives the distance from the tee to the hole, an integral number of metres between 1 and 5\,280. The next line states the number of clubs, between 1 and 32. For each club, a line follows giving the distance, in metres, that the club will hit the ball, an integer between 1 and 100. No two clubs have the same distance.

Output Specification

If Roberta can get the ball from the tee to the hole, without passing the hole, print Roberta wins in n strokes. where n is minimized. If Roberta cannot get the ball from the tee to the hole, print Roberta acknowledges defeat.

Sample Input

100
3
33
66
1

Sample Output

Roberta wins in 3 strokes.

Comments


  • 0
    mofeng
     commented on March 13, 2017

    Is the combination of distances cannot exactly equal the distance to the hole, is it means it is impossible to hit? I mean if the combination is greater than the distance, is it means cannot hit?


  • 1
    BetaHaxor
     commented on Dec. 3, 2016 edited
    Question

    is the golf field 1 dimensional?


    • 0
      Kirito
       commented on Dec. 3, 2016

      When she hits the golf ball it always goes directly towards the hole on the green

      Effectively, yes.


  • 0
    leonchen0613
     commented on Oct. 28, 2016
    Question

    Can Roberta use a club more than once?


    • 0
      Kirito
       commented on Oct. 28, 2016

      Yes.