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
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
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 : [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++){ // insert dynamic programming here... } } if(dp[dist]==tmp) ..... else .... return 0; } [/code] for any admins thinking this is giving away too much, edit it as you see fit.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 :
for any admins thinking this is giving away too much, edit it as you see fit.
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
notice how that can overflow your state array. check to see if t is in bounds in your if statement.
so (if t > dist)
break;
?
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...
So, a club cannot be used more than 1 time right?
This is golf - in golf, after you use a club, do you just throw it away and never use it again?
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?
anyway
NO CHEATING BANNED FOR LIFE
I remember some program on the judge where it was wrong for missing a period and it took ages to debug =/