Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Old CCC question
Author Message
Martin

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

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

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

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

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

Posted: 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
Tony

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

I updated the post with official sample from waterloo.

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

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)

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
Tony's programming blog. DWITE - a programming contest.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 2  [ 27 Posts ]
Goto page 1, 2  Next
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: