Problem Links:
USACO_nuggets.Problem:
Hubert Chen
One strategy the cows are pursuing is that of `inferior packaging'. ``Look,'' say the cows, ``if you have Beef McNuggets in boxes of 3, 6, and 10, you can not satisfy a customer who wants 1, 2, 4, 5, 7, 8, 11, 14, or 17 McNuggets. Bad packaging: bad product.''
Help the cows. Given N (the number of packaging options, 1 <= N <= 10), and a set of N positive integers (1 <= i <= 256) that represent the number of nuggets in the various packages, output the largest number of nuggets that can not be purchased by buying nuggets in the given sizes. Print 0 if all possible purchases can be made or if there is no bound to the largest number.
The largest impossible number (if it exists) will be no larger than 2,000,000,000.
PROGRAM NAME: nuggets
INPUT FORMAT
Line 1: | N, the number of packaging options |
Line 2..N+1: | The number of nuggets in one kind of box |
SAMPLE INPUT (file nuggets.in)
3 3 6 10
OUTPUT FORMAT
The output file should contain a single line containing a single integer that represents the largest number of nuggets that can not be represented or 0 if all possible purchases can be made or if there is no bound to the largest number.SAMPLE OUTPUT (file nuggets.out)
17
Solution:
1st, check if the answer existed and can be represented. If not return 0;2nd, Using Dynamic Programming to mark all the possible solution, till reach the boundary.
Source Code: [on GitHub]
/* ID: LANG: JAVA PROG: nuggets */ import java.io.BufferedReader; import java.io.FileReader; import java.io.FileWriter; import java.io.PrintWriter; /** * @author antonio081014 * @time Jul 28, 2013, 3:26:58 PM */ public class nuggets { private static final int SIZE = 100000; private boolean[] mark; public static void main(String[] args) { nuggets main = new nuggets(); main.run(); System.exit(0); } private void run() { try { BufferedReader in = new BufferedReader(new FileReader("nuggets.in")); PrintWriter out = new PrintWriter(new FileWriter("nuggets.out")); int N = Integer.parseInt(in.readLine()); int[] array = new int[N]; for (int i = 0; i < N; i++) { array[i] = Integer.parseInt(in.readLine()); } in.close(); out.println(solve(array)); out.close(); } catch (Exception e) { e.printStackTrace(); } } private int solve(int[] array) { mark = new boolean[SIZE]; boolean flag = true; for (int i = 0; i < array.length; i++) for (int j = i + 1; j < array.length; j++) if (gcd(array[i], array[j]) == 1) flag = false; if (flag) return 0; int max = 0; mark[0] = true; for (int i = 0; i < SIZE; i++) { if (!mark[i]) max = i; else for (int j = 0; j < array.length; j++) { if (i + array[j] < SIZE) mark[i + array[j]] = true; } } return max; } public int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); } }
1 comment :
Pembrokes and Mummys Gold Casino, Newmarket - MapYRO
Compare 의왕 출장마사지 reviews, photos 바카라 사이트 승리바카라 and location for Pembrokes and Mummys 원주 출장샵 Gold Casino 인천광역 출장마사지 in Newmarket, 사천 출장안마 NJ.
Post a Comment