CCC '00 S4 - Golf

View as PDF

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

Problem type
Canadian Computing Competition: 2000 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 clubs, and the total distance from the tee to the hole does not exceed metres.

Input Specification

The first line of input gives the distance from the tee to the hole, an integral number of metres between and . The next line states the number of clubs, between and . For each club, a line follows giving the distance, in metres, that the club will hit the ball, an integer between and . 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 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.

• commented on July 4, 2021, 2:37 p.m.

I'm getting test case 5 wrong for some reason, all other test cases are AC. I am using memoization and I have a Map with the distance as the key and the number of hits it takes to reach the hole as the value. Is there something I'm doing wrong?

• commented on Nov. 12, 2020, 3:05 p.m. edited

(redacted)

• commented on Sept. 30, 2020, 2:39 p.m.

Did this get a new test case?

• commented on Feb. 24, 2021, 8:19 p.m. edit 3

i believe that test case 6 has data thats longer than 5280 meters?

• commented on Oct. 28, 2020, 8:59 a.m.

kdrkdr's dad tried to cheese the problem (:

• commented on Oct. 28, 2020, 7:45 p.m.

:monkey:

• commented on Jan. 11, 2020, 1:48 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on May 5, 2020, 11:12 p.m.

Low stingers all day.

• commented on March 13, 2017, 2:51 a.m.

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?

• commented on July 17, 2020, 2:50 p.m.

"Without passing the hole"

• commented on May 5, 2020, 6:27 p.m.

...and she always hits exactly the distance that is specified for the club.

This means that, even if the distance hit by the club is greater than the remaining distance, Roberta will hit the ball over and beyond the hole instead of letting the ball roll. That's just a little made-up explanation for the question :)

• commented on Dec. 3, 2016, 11:29 a.m. edited

is the golf field 1 dimensional?

• commented on Dec. 3, 2016, 12:13 p.m.

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

Effectively, yes.

• commented on Oct. 28, 2016, 6:51 p.m.

Can Roberta use a club more than once?

• commented on Oct. 28, 2016, 11:02 p.m.

Yes.