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)

<
1
2
>

I tried again and I got 3 right. Please help me.

HI vyom, I'll look over your code and check to see what's wrong
Edit: remember, you can use the same club
Edit: as i said before, you might want to look at dynamic programming,and try giving your variables meaningful names, so people can understand your code better when trying to help you
here is a hint/pseudo code :
 
#include<bits/stdc++.h>
using namespace std;
int main(){
inputs........
.........
memset(dp,100,sizeof(dp));
tmp = dyn[0]
dyn[0] = 0
for(int a=0;a<dist;a++){
if(dp[a]<tmp)
for(int b=0;b<n;b++){
if(dp[a+club[b]]>dp[a]+1)
dp[a+club[b]]=dp[a]+1;
}
}
if(dp[dist]==tmp)
.....
else
....
return 0;
}

for any admins thinking this is giving away too much, edit it as you see fit.

I'm getting the first test case right but not the other 4.

search up on dynamic programming, and the reason is obvious, your code or logic/algorithm is wrong

So first off, use int instead of long long. Second of all, your code won't work for a test case such as 31m, 3 clubs, and the 3 clubs are 15, 11 and 10. Your program would output "Roberta acknowledges defeat." while the correct answer should be "Roberta wins in 3 strokes". Try starting your clubs calculation from the club with the lowest amount of distance and work your way up. If it takes fewer swings than the previous combination, replace the minimum amount of clubs. Also, try searching up on dynamic programming just like my friend said. If you still need help, I'll be here :3 :)

btw, you don't have to use long, since there is only a max of 32 clubs and each of them don't exceed a "long" data type,

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.