2000 Canadian Computing Competition, Stage 1

Problem S4: Golf

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 5280 metres.

Input

The first line of input gives the distance from the tee to the hole, an integral number of metres between 1 and 5280. 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

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. 

All Submissions
Best Solutions


Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 29, 2008

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

The description is missing something very important. You may use the same club more than once. This solved my problem.

This seems obvious, but okay, sure.

Ummm.. no, it's not obvious from the problem description. It is merely your assumption.

Like SourSpinach mentioned below, it's usually important to consider the real world context; I personally wouldn't throw away my golf clubs after using them once--although that certainly would encourage people to try to win in as few shots as possible :)

Correct me if I'm wrong, but I believe there is an error on the wiki page that links to this problem.
http://screencloud.net/v/kTdp

In both cases the if statement should say "if d[j] ≤ i" rather than "if d[j] ≤ c[i]". However I'm not sure if I'm right.

Link to the wiki page is:
http://wcipeg.com/wiki/Dynamic_programming

Couldn't you have posted this on the talk page for the wiki article? Anyway, I fixed it.

Sorry, didn't know there was one.

It only took 79 tries!!!!! Ouch that was painful, made me take a break for a few weeks... but I got it!

I think description should include"you can use a club multiple times". It may be obvious for people who know golf but not for everyone.

This problem's fairly easy, but I'm not sure why I'm runtime-error'ing, although I suspect an overflow. Can one of the admins tell me what I'm doing wrong please?

int t = state[j] + j;

notice how that can overflow your state array. check to see if t is in bounds in your if statement.

makes sense.

so (if t > dist)
break;

?

All right, I've looked at your submission more closely. The output says:
terminate_called_after_throwing_an_instance_of_'std::bad_alloc'
__what():__std::bad_alloc_

bad_alloc is an exception thrown when a memory allocation fails. Since you're probably too smart to be using exceptions (ugh...) it must have been thrown by the STL. Indeed, inspection of your code reveals that you construct the vectors clubs and state before n and size are initialized!
That is not how vectors and their constructors work. The argument to the constructor is evaluated immediately and the vector is constructed immediately with this size. You have to read in n and dist and then construct the vectors.

OR you could avoid all this nonsense by simply having fixed-length arrays...

got it. thanks

No two clubs have the same distance.


So, a club cannot be used more than 1 time right?

Does that sentence say that you can only use it once? No.

This is golf - in golf, after you use a club, do you just throw it away and never use it again?

Hanson, I realize that my solution is getting TLE, but I think you ought to consider the brilliance in the code. I would appreciate it if you were to give me 5 partial points for this, since otherwise, I will have to resort to cheap ways to do this problem.

If you are trying to get marks, DON'T BEG HANSON FOR THEM. ACTUALLY GET THEM!!!!!!!naughty.gif

"I would appreciate...if I you were to give me 5 partial points"

I really can't believe it, asking for points for a TLEing solution that doesn't deserve any.

If you're solution TLE's, it's not brilliant at all.

1) Optimize it, if you're using recursion.
2) Think of another method.
3) Stop whining.

And if you cheat, you will probably get banned.

Would it rest well on your conscience that you cheated on a problem just so you could get points while others toiled endlessly for many sleepless nights over it before being able to do it?

I swear you copied and pasted this reply from somewhere else. lol

anyway
NO CHEATING BANNED FOR LIFE

If it takes one stroke, do you output Roberta wins in 1 stroke, or do you follow the question and output 1 strokes?

I'm pretty sure you have to be grammatically correct.
I remember some program on the judge where it was wrong for missing a period and it took ages to debug =/

nope you don't, i chekced my code.

Can someone please teach me recursion!?!?!? I'm so screwed

someone needs to give him a hug.

he doesnt know recursion :'(

i thought I told you earlier on today that DFS IS RECURSION!!!! USACO WILL NEVER GIVE YOU A PROBLEM THAT INVOVLES CONCEPTS YOU HAVE'T LEARNED YET!!!!!!!!!!!!

perhaps you are lacking in the "brainpower" category.

It's DFS. Not DPS.

DFS stands for Depth-First Search.