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