Computer Science Canada

Old CCC question

Author:	Martin [ 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 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

Author:	Catalyst [ Sun May 11, 2003 2:21 am ]
Post subject:
shouldnt it be 5 strokes 55+30+5+5+5 or do you not count the last one? (or the first)

Author:	Asok [ Sun May 11, 2003 10:24 am ]
Post subject:
you don't count the first I believe, it's the distance.

Author:	Catalyst [ Sun May 11, 2003 12:36 pm ]
Post subject:
she still has to hit the ball 5 times to get it in tho

Author:	Tony [ Sun May 11, 2003 1:06 pm ]
Post subject:
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

Author:

Crono [ Sun May 11, 2003 1:21 pm ]

Post 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

Author:

Crono [ Sun May 11, 2003 1:27 pm ]

Post 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

Author:	Crono [ Sun May 11, 2003 1:41 pm ]
Post subject:
hey martin, pays off 2 b in the same class eh? lol

Author:

Catalyst [ Sun May 11, 2003 7:25 pm ]

Post 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

Author:	Crono [ Sun May 11, 2003 8:10 pm ]
Post 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

Author:	Martin [ Sun May 11, 2003 8:27 pm ]
Post subject:
There's your bits chrono...

Author:	Crono [ Sun May 11, 2003 8:30 pm ]
Post subject:
thx martin, i'll c u in class tomorrow, how's the essay comin?

Author:	Catalyst [ Sun May 11, 2003 8:42 pm ]
Post subject:
chrono on yours the same input ends in 18 strokes too

Author:

Martin [ Mon May 12, 2003 9:37 am ]

Post 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

Author:	Tony [ Mon May 12, 2003 11:58 am ]
Post subject:
yo, martin... you gotta explain this stuff to me some time... before CCC 2004 hopefully

Author:	Martin [ Mon May 12, 2003 3:05 pm ]
Post subject:
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.

Author:	Crono [ Mon May 12, 2003 4:30 pm ]
Post subject:
yea, catalyst ur rite, however my first proc works, guess i just wuzn't payin attention to all possible cases...

Author:	Catalyst [ Mon May 12, 2003 8:25 pm ]
Post subject:
yup i should fix mine.... ...ill get to it eventually....

Author:

Martin [ Tue May 13, 2003 12:36 pm ]

Post subject:

Iteratively:

code:

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) <= dist then
if arr (x) + 1 < arr (x + club (y)) then
arr (x + club (y)) := arr (x) + 1
end if
end if
end for
end for

if arr (dist) = 1542343 then
put "It's raining, so Roberta short circuits and blows up the golf course."
else
put "Roberta wins in ", arr (dist), " strokes"
end if

Author:	Martin [ Tue May 13, 2003 5:03 pm ]
Post subject:
Bugz showed me how to do this, so the bitz go to him

Author:

Tony [ Tue May 13, 2003 8:13 pm ]

Post subject:

you'd have to explain

code:

if arr (x) + 1 < arr (x + club (y)) then
arr (x + club (y)) := arr (x) + 1

whats arr? whats up with 1542343? and just what the line above means... I think the rest is understandable

Author:	Martin [ Tue May 13, 2003 9:06 pm ]
Post subject:
1542343 is what happens when you press 7 random numbers on your keyboard. Arr is an array, used in the generation of the distance. The concept behind this is like so: say, for example your input is: Distance = 50 nclub = 4 club(1) = 4 club(2) = 5 club(3) = 20 club(4) = 36 Now, starting at 4, the least number of ways to get to 4 is 1, then the least number of ways to get to 5 is 1, you can't get to 6 or 7, then the least number of ways to get to 8 is 2 (4+4), 9 is 2 (4+5) and so on. After finding all of the ways, it just puts them together...I know it's not to detailed, but if you trace the program, it should make sense.

Author:	Martin [ Tue May 13, 2003 11:11 pm ]
Post subject:
Arr(x) basically stores the minimum number of strokes to get to x

Author:	bugzpodder [ Thu May 22, 2003 4:07 pm ]
Post subject:
Quote: Bugz showed me how to do this, so the bitz go to him before i went into this thread, i was thinking that you were about to take credit for my work! ^.^; guess i was wrong! Darkness wrote: 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. only if you are top 50 programmer in the world, then you are able to finish it. otherwise dont even think about it. i am still barely half-way (not even). 1542343 is only for convience. we just need a big number. Quote: Arr(x) basically stores the minimum number of strokes to get to x true. but obviously 1542343 means unobtainable btw this technique is called dynamic programming. it trades off memory for speed. a recursive method, while uses constant storage, also has exponential run-time. however, this method have only quadratic run-time with linear storage (however still very memory expansive, but can be improved with optimizations)

Author:

Martin [ Thu May 22, 2003 4:29 pm ]

Post subject:

fibinacci sequence dynamically

code:

var a,b,c,n : int := 1
get n
for i:3..n
c := a + b
a := b
b := c
end for
put c

Author:

bugzpodder [ Thu May 22, 2003 4:39 pm ]

Post subject:

good memory!

recursively,

code:

fcn fib(n:int):int
if n<2 then
result 1
else
result fib(n-1)+fib(n-2)
end if
end fib

Author:	Martin [ Thu May 22, 2003 5:57 pm ]
Post subject:
Heh, I wrote a program to do that on my calculator. now I have to figure out how to graph them

You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy