Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Old CCC question
Index -> Contests
Goto page 1, 2  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Martin




PostPosted: 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
Sponsor
Sponsor
Sponsor
sponsor
Catalyst




PostPosted: Sun May 11, 2003 2:21 am   Post subject: (No subject)

shouldnt it be 5 strokes

55+30+5+5+5

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




PostPosted: Sun May 11, 2003 10:24 am   Post subject: (No subject)

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




PostPosted: Sun May 11, 2003 12:36 pm   Post subject: (No subject)

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




PostPosted: Sun May 11, 2003 1:06 pm   Post subject: (No subject)

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

I updated the post with official sample from waterloo.

its 3 strokes : 66 + 33 + 1 = 100
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
Crono




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




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




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

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




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




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




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

There's your bits chrono...
Crono




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




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

chrono on yours the same input ends in 18 strokes too
Martin




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




PostPosted: 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 Wink
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 2  [ 27 Posts ]
Goto page 1, 2  Next
Jump to:   


Style:  
Search: