// http://uva.onlinejudge.org/external/100/10032.html
// Runtime: 0.248s
// Tag: Dp
/*
* File: main.cpp
* Author: shahab
* Created on March 6, 2011, 11:24 PM
*/
// @BEGIN_OF_SOURCE_CODE
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long
#define For(i, a, b) for ( int i = (a); i < (b); i++ )
#define Fors(i, sz) for ( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset (a, s, sizeof (a))
using namespace std;
int weight [100 + 10];
bool minWeight [45000 / 2 + 100];
int minPeople [45000 / 2 + 100];
int maxPeople [45000 / 2 + 100];
int main(int argc, char** argv) {
int testCase;
scanf ("%d", &testCase);
bool blank = false;
while ( testCase-- ) {
int n; scanf ("%d", &n);
int total = 0;
For (i, 0, n) { scanf ("%d", &weight [i]); total += weight [i]; }
Set (minWeight, false);
for ( int i = 0; i < 45000 / 2 + 100; i++ ) { minPeople [i] = INT_MAX; maxPeople [i] = 0; }
minWeight [0] = true;
minPeople [0] = 0;
For (i, 0, n) {
for ( int j = total / 2 + 5; j >= 0; j-- ) {
if ( minWeight [j] ) {
minWeight [j + weight [i]] = true;
if ( minPeople [j + weight [i]] > minPeople [j] + 1)
minPeople [j + weight [i]] = minPeople [j] + 1;
if ( maxPeople [j + weight [i]] < maxPeople [j] + 1)
maxPeople [j + weight [i]] = maxPeople [j] + 1;
}
}
}
if ( blank ) printf ("\n"); blank = true;
for ( int i = total / 2; i >= 0; i-- ) {
if ( minWeight [i] && ((minPeople [i] <= n / 2 && maxPeople [i] >= n / 2) || (minPeople [i] <= n / 2 + n % 2 && maxPeople [i] >= n / 2 + n % 2)) ) {
printf ("%d %d\n", i, total - i); break;
}
}
}
return 0;
}
// @END_OF_SOURCE_CODE

### Like this:

Like Loading...

*Related*

Would you please explain, how you did this program ?

@Saleh

ya, i can try 🙂

array minWeight is initially false

after running the program, if minWeight [x] = true

it means, it is possible to make weight x, using some people

for example, if total weight of all people is P

and if we can make (P/2) using some people

then definitely we can make another (P/2) using rest of the people

we have two others array minPeople and maxPeople

if minPeople [x] = y then

it means, we can make weight x, but we need at least y people

if maxPeople [x] = y then

it means, we can make weight x, using at most y people

finally i started to search from totalWeight/2 to downward

if i found a weight that can be made and maxPeople == minPeople then output

or, find a weight that can be made and (maxPeople + 1 == minPeople) or (maxPeople == minPeople + 1) then output

hope this may help 🙂

Did it get accepted? Doesn’t this entry brake your code?

6 persons each with weight: 1 1 2 10 10 20

The answer should be 22

team 1: {10 10 2}

team 2:{20 1 1}

Yet we can get 22 with:

{20, 2} two people => minPeople = 2

{10 10 1 1} four people => maxPeople = 4

So the final loop would miss the correct answer and not print it, is that correct or i misunderstood you code?

hummm I was wrong what actually would break it would be

6 persons: 1 1 1 1 1 5

the answer should be: 3 7

team1:{1 1 1} and team2:{1 1 5}

5 weight can be made with

{5}=> minPeople[5] = 1

or with

{1 1 1 1 1}=> maxPeople[5] = 5

your output would be 5 5 instead of 3 7 is that correct?

ops! my mistake

input:

1

6

1 1 1 1 1 5

correct output should be 3 7

test cases might be weak 😦

thx for the answer.

what about this:

6

10 1 1 2 3 3

Correct Ans: 8 12

Your Ans would be: 10 10

@Skywalker

yea, the code is wrong