Old CCC question

[Martin]

This is an old CCC question...not too hard but let's see what you guys can do with it. For an added challenge, try doing it iteratively instead of recursive.

Roberta the Robot plays a perfect game of golf. Your job is to find the minimum number of strokes to the hole. Input the distance to the hole (Integer value less than or equal to 5860), followed by n, which is the number of clubs. After that, there are n lines, each one with a distance that the club can hit. Roberta always hits the ball to the maximum distance. She can use any club, at any time, any amount of times. If Roberta can make it to the hole, your output should be

Quote:

"Roberta wins in n strokes"

, where n is minimized. If she cannot make it to the hole, output

Quote:

"Roberta admits defeat."

SAMPLE:

Quote:

Sample Input ( Input file : golf.in )
100
3
33
66
1


Output for Sample Input ( Output file : golf.out )
Roberta wins in 3 strokes.

25 bits to the person who gets this recursively, 100 if you can do it iteratively.

Sample edited by Tony

[Catalyst]

shouldnt it be 5 strokes

55+30+5+5+5

or do you not count the last one? (or the first)

[Asok]

you don't count the first I believe, it's the distance.

[Catalyst]

she still has to hit the ball 5 times to get it in tho

[Tony]

yeah, Catalyst is right... its just that Martin doesn know what he's doing

I updated the post with official sample from waterloo.

its 3 strokes : 66 + 33 + 1 = 100

[Crono]

well, here it is in recursion, make ur own "golf.in"

code:

var temp, fin, dist, num, low : int var club : flexible array 1 .. 0 of int var won : boolean proc FORE (strokes, dist, clubID : int)     if dist = 0 then         low := min (low, strokes)         won := true         return     elsif clubID > num then         return     elsif dist >= club (clubID) then         FORE (strokes + 1, dist - club (clubID), clubID)     end if     FORE (strokes, dist, clubID + 1) end FORE open : fin, "golf.in", get assert fin not= 0 get : fin, dist, num new club, num for i : 1 .. num     get : fin, club (i) end for for x : 1 .. num - 1     for y : x + 1 .. num         if club (x) < club (y) then             temp := club (x)             club (x) := club (y)             club (y) := temp         end if     end for end for low := maxint won := false FORE (0, dist, 1) if won then     put "Roberta sinks the ball in ", low, " strokes." else     put "Roberta loses and kills herself." end if

[Crono]

my bad, here's the recursive proc again, i accidentally put it outside the if statements

code:

proc FORE (strokes, dist, clubID : int)     if dist = 0 then         low := min (low, strokes)         won := true         return     elsif clubID > num then         return     elsif dist >= club (clubID) then         FORE (strokes + 1, dist - club (clubID), clubID)     else         FORE (strokes, dist, clubID + 1)     end if end FORE

[Crono]

hey martin, pays off 2 b in the same class eh? lol

[Catalyst]

Iteratively

code:

proc Bubble (var a : array 1 .. * of int, n : int)     var hold : int     for i : 1 .. n         for k : 1 .. n - 1             if a (k) > a (k + 1) then                 hold := a (k)                 a (k) := a (k + 1)                 a (k + 1) := hold             end if         end for     end for end Bubble var holeDist : int get holeDist var numClubs : int get numClubs var ClubDist : array 1 .. numClubs of int for i : 1 .. numClubs     get ClubDist (i) end for var distToHole : int := holeDist Bubble (ClubDist, numClubs) var Strokes : int := 0 loop     exit when distToHole < ClubDist (1)     for decreasing i : numClubs .. 1         if distToHole >= ClubDist (i) then             distToHole -= ClubDist (i)             put "Used Club #", i, "][", distToHole, " yards left."             Strokes += 1             exit         end if     end for end loop if distToHole = 0 then     put "Roberta wins in ", Strokes, " strokes." else     put "Roberta admits defeat." end if

[Crono]

uh catalyst i think ther's a problem, cuz it goes for the largest one and tries based on the largest one, try 100 = distance, 3 = numclubs, 66, 50, and 2, it gave me 18

[Martin]

There's your bits chrono...

[Crono]

thx martin, i'll c u in class tomorrow, how's the essay comin?

[Catalyst]

chrono on yours the same input ends in 18 strokes too

[Martin]

Here's how you do it recursively:

code:

var nClub : int put "Number of clubs: " .. get nClub var least := 6000 var dist : int var club : array 1 .. nClub of int put "Distance to the hole: " .. get dist for i : 1 .. nClub     put "Club (", i, ") :" ..     get club (i) end for proc golf (nStroke, dist, cl : int)     if (dist = 0) then         least := min (least, nStroke)         return     elsif (cl > nClub) then         return     elsif (dist >= club (cl)) then         golf (nStroke + 1, dist - club (cl), cl)     end if     golf (nStroke, dist, cl + 1) end golf golf (0, dist, 1) if least = 6000 then     put "Roberta admits defeat." else     put "Roberta wins in ", least, " strokes." end if

[Tony]

yo, martin... you gotta explain this stuff to me some time... before CCC 2004 hopefully