-----------------------------------

Martin

Thu May 08, 2003 7:49 am


Old CCC question

-----------------------------------

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 "Roberta wins in n strokes", where n is minimized. If she cannot make it to the hole, output  "Roberta admits defeat."

SAMPLE:
 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

Sun May 11, 2003 2:21 am



-----------------------------------

shouldnt it be 5 strokes

55+30+5+5+5

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


-----------------------------------

Asok

Sun May 11, 2003 10:24 am



-----------------------------------

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


-----------------------------------

Catalyst

Sun May 11, 2003 12:36 pm



-----------------------------------

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


-----------------------------------

Tony

Sun May 11, 2003 1:06 pm



-----------------------------------

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

Sun May 11, 2003 1:21 pm



-----------------------------------

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

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

Sun May 11, 2003 1:27 pm



-----------------------------------

my bad, here's the recursive proc again, i accidentally put it outside the if statements
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

Sun May 11, 2003 1:41 pm



-----------------------------------

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


-----------------------------------

Catalyst

Sun May 11, 2003 7:25 pm



-----------------------------------

Iteratively

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

Sun May 11, 2003 8:10 pm



-----------------------------------

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

Sun May 11, 2003 8:27 pm



-----------------------------------

There's your bits chrono...


-----------------------------------

Crono

Sun May 11, 2003 8:30 pm



-----------------------------------

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


-----------------------------------

Catalyst

Sun May 11, 2003 8:42 pm



-----------------------------------

chrono on yours the  same input ends in 18 strokes too


-----------------------------------

Martin

Mon May 12, 2003 9:37 am



-----------------------------------

Here's how you do it recursively:

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

Mon May 12, 2003 11:58 am



-----------------------------------

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


-----------------------------------

Martin

Mon May 12, 2003 3:05 pm



-----------------------------------

Seriously, if you want to get really good at programming, go to http://ace.delos.com/usacogate first, it's a great way to learn c++, and secondly, if you can finish it, you will get first on the senior ccc I guarentee.


-----------------------------------

Crono

Mon May 12, 2003 4:30 pm



-----------------------------------

yea, catalyst ur rite, however my first proc works, guess i just wuzn't payin attention to all possible cases...


-----------------------------------

Catalyst

Mon May 12, 2003 8:25 pm



-----------------------------------

yup
i should fix mine....
...ill get to it eventually....


-----------------------------------

Martin

Tue May 13, 2003 12:36 pm



-----------------------------------

Iteratively:

var nclubs : int
var dist : int
put "Number of clubs: " ..
get nclubs
put "Distance to hole: " ..
get dist
var club : array 1 .. nclubs of int
for i : 1 .. nclubs
    put "Club (", i, "): " ..
    get club (i)
end for

var arr : array 0 .. 6000 of int
for i : 0 .. 6000
    arr (i) := 1542343
end for
arr (0) := 0
for x : 0 .. dist
    for y : 1 .. nclubs
        if x + club (y)