Posted: Thu May 08, 2003 7:49 am Post subject: 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

Quote:

"Roberta wins in n strokes"

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

Posted: Sun May 11, 2003 1:21 pm Post subject: (No subject)

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

Posted: Sun May 11, 2003 1:27 pm Post subject: (No subject)

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

Posted: Sun May 11, 2003 1:41 pm Post subject: (No subject)

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

Catalyst

Posted: Sun May 11, 2003 7:25 pm Post subject: (No subject)

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

Posted: Sun May 11, 2003 8:10 pm Post subject: (No subject)

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

Posted: Sun May 11, 2003 8:27 pm Post subject: (No subject)

There's your bits chrono...

Crono

Posted: Sun May 11, 2003 8:30 pm Post subject: (No subject)

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

Catalyst

Posted: Sun May 11, 2003 8:42 pm Post subject: (No subject)

chrono on yours the same input ends in 18 strokes too

Martin

Posted: Mon May 12, 2003 9:37 am Post subject: (No subject)

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

Posted: Mon May 12, 2003 11:58 am Post subject: (No subject)

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