// CCC 2000 // Problem S4 Golf // This is a classic Dynamic programming problem // given a set of numbers(clubs), determine the total number of clubs // needed to get to a given distance. // (full solution giving the clubs themselves is in javapgms) // For example if there were clubs 2,4,5 and the total distance was 12 // then it would take 3 clubs (5, 5 and 2) // method is calculate # for all distances from 0 to given! // F(0) = 0 // F(n) = (minimum of F(n-club(i)) i=0 to #clubs, provided minimum >= 0) + 1 // using the above example of 2, 4 and 5 clubs you would have: // F(0) = 0 // F(1) = -1 (can't get there) // F(2) = 1 // F(3) = -1 // F(4) = 1 // F(5) = 1 // F(6) = 2 because F(6-2) = 1 is min, therefore answer is F(4) + 1 = 2 // F(7) = 2 because F(7-2) = 1 is min, therefore answer is F(5) + 1 = 2 // F(8) = 2 because F(8-4) = 1 is min, therefore answer is F(4) + 1 = 2 // F(9) = 2 because F(9-4) = 1 is min, therefore answer is F(5) + 1 = 2 // F(10) = 2 because F(10-5) = 1 is min, therefore answer is F(5) + 1 = 2 // F(11) = 3 because F(11-2) = 2 is min, therefore answer is F(9) + 1 = 3 // F(12) = 3 because F(12-2) = 2 is min, therefore answer is F(10) + 1 = 3 // file consists of distance, number of clubs and then the clubs. // output is a statement about number of strokes, or "defeat" import java.awt.*; import hsa.*; public class S4Golf { static Console c; public static void main (String [] args) { c = new Console (); int club [] = new int [32]; int dis, n, ans; TextInputFile fi = new TextInputFile ("golf.in1"); TextOutputFile fo = new TextOutputFile ("golf.ou1"); dis = fi.readInt (); n = fi.readInt (); for (int i = 0 ; i < n ; i++) club [i] = fi.readInt (); ans = solve (dis, club, n); if (ans == -1) { fo.println ("Roberta acknowledges defeat."); c.println ("Roberta acknowledges defeat."); } else { fo.println ("Roberta wins in " + ans + " strokes."); c.println ("Roberta wins in " + ans + " strokes."); } } public static int solve (int distance, int [] club, int n) { int [] f; int min, t; f = new int [distance + 1]; f [0] = 0; for (int x = 1 ; x <= distance ; x++) { min = 999999999; for (int j = 0 ; j < n ; j++) { t = x - club [j]; if (t >= 0 && f [t] >= 0 && f [t] < min) min = f [t]; } if (min < 999999999) f [x] = min + 1; else f [x] = -1; } return f [distance]; } }