// 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
Advertisements
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