Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1423
“Who can take a sunrise Sprinkle it with dew Cover it in chocolate and a miracle or two The Candy Man The Candy Man can The Candy Man can ’cause he mixes it with love And makes the world taste good” (taken from the movie ”Willy Wonka and the Chocolate Factory”, 1971) The Candyman can. But can he really? It’s the first of October, the day Willy Wonka opens the doors to his famous Chocolate Factory for the five lucky kids that hold one of the golden tickets: Charlie, Augustus, Mike, Veruca and Violet. The tour guided by Willy Wonka begins, and after Augustus falls into the river of chocolate and Violet turns into a blueberry (but don’t worry, they are going to be safe and healthy at the end), there are three of the children left. What a shock! To calm down the remaining three children, Willy Wonka wants to give some candies to them. He has a couple of candies that are of different weight and wants to divide them evenly between the children, so that they don’t get jealous at each other. He wants to know how bad the fairest distribution is, i.e. what is the minimum difference in the candies weight, of the kid getting the candies of the most total weight and the kid getting the least. For example, assume that he gives the three children candies of weight a, b and c, respectively. The badness of this distribution is the difference between the maximum of a, b, c and the minimum of a, b, c. Unfortunately, Willy Wonka is not very good in mathematics, so he needs your help. Input The first line of input contains a single integer (less than 130) indicating the number of testcases that follow. Each testcase consists of two lines. The first line contains a number n(0 < n ≤ 32), the number of candies to be distributed. The second line contains n numbers a1 . . . an (0 < ai ≤ 20 for all i = 1 . . . n), the weight of the different candies. Output For each testcase, output a single line which contains the case number (as shown in the sample output) and then the smallest badness that can be achieved when distributing all candies to the children. There is only a single space between the colon and the smallest badness.
Sample Input 4 3 2 2 2 2 3 4 6 13 9 7 7 1 7 8 3 3 3 3 3 3 5 5
Sample Output Case 1: 0
Case 2: 4
Case 3: 2
Case 4: 1
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int tc,n,v;
vector<int> candies;
vector<int> cul_sum;
// can we reach this state?
bool dp[33][641][641]; // state: candyIdx, giveA, giveB: infer giveC with sum-giveA-giveB
int max_diff(int a, int b, int c){
int highest = max(a, max(b, c));
int lowest = min(a, min(b, c));
return highest - lowest;
}
int main() {
scanf("%d",&tc);
for(int t=1;t < =tc;t++){
scanf("%d",&n);
memset(dp, 0, sizeof dp);
candies.clear();
cul_sum.assign(1, 0);
for(int j=0;j < n;j++){
scanf("%d",&v);
candies.push_back(v);
cul_sum.push_back(cul_sum.back() + v);
}
dp[0][0][0] = 1;
for(int i=0;i < n;i++){
int sum = cul_sum[i];
for(int j=0;j < =sum;j++){
for(int k=0;k < =sum;k++){
if(dp[i][j][k] == 0) continue;
int a = j, b = k;
int c = sum - a - b; // infer c from a & b
if(c < 0) continue;
int next_a = a + candies[i], next_b = b + candies[i], next_c = c + candies[i];
dp[i+1][next_a][b] = dp[i+1][a][next_b] = dp[i+1][a][b] = 1;
}
}
}
int res = 1e7;
int sum = cul_sum.back();
for(int j=0;j < =sum;j++)
for(int k=0;k < =sum;k++>
if(dp[n][j][k] != 0 && sum-j-k >= 0)
res = min(res, max_diff(j,k,sum-j-k));
printf("Case %d: %d\n", t, res);
}
}Input
3
2 2 2
2
3 4
6
13 9 7 7 1 7
8
3 3 3 3 3 3 5 5
Output
Case 2: 4
Case 3: 2
Case 4: 1
Demonstration
UVA Online Judge solution - 10482-The Candyman Can - UVA Online Judge solution in C,C++,java