USACO_nuggets.

## Problem:

Beef McNuggets
Hubert Chen
Farmer Brown's cows are up in arms, having heard that McDonalds is considering the introduction of a new product: Beef McNuggets. The cows are trying to find any possible way to put such a product in a negative light.
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.

### INPUT FORMAT

 Line 1: N, the number of packaging options Line 2..N+1: The number of nuggets in one kind of box

```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.

`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.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 {
PrintWriter out = new PrintWriter(new FileWriter("nuggets.out"));
int[] array = new int[N];
for (int i = 0; i < N; i++) {
}
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 :

imrebaar said...

Pembrokes and Mummys Gold Casino, Newmarket - MapYRO
Compare 의왕 출장마사지 reviews, photos 바카라 사이트 승리바카라 and location for Pembrokes and Mummys 원주 출장샵 Gold Casino 인천광역 출장마사지 in Newmarket, 사천 출장안마 NJ.