problem number 1

well err?.. i don't like to ask for help with homeworks but i really don't know how to solve this problem..

At the new year's eve concert the first 2 rows are reserved to the officials. Both rows are formed from the same number of chairs S. The chairs are numbered from 1 to S, from left to right. There are N official persons who must receive an invitation (let's count them from 1 to N). Each official person comes with a group. let's note with Gi the number of members from i's group (including i, the official). The members of a group must be placed on the same row on consecutive places, or (if the number of members is even) the members of the group can be divided into 2 halves and they can be placed on consecutive places having the same numbers on the 2 rows. Write a program which determines the minimum value of S which forms the 2 rows to arrange all members from the groups according to the rules.

Input data
file in.txt contains on the first line the number N of official persons. on the second line there are N numbers separated by a space = G1, G2 ... Gn where Gi represents the number of members from i's group. (including i)

Output data
write the minimum value of S.. wherever you want...

1<=N<=1000
G1+G2+...+GN<=100000

Example:
file in.txt
4
20 5 3 1

output: 15

Comments

  • [code]
    #include
    #include

    using namespace std ;

    static UINT kCalcTotalOfLargerPartition(const vector& kDescendingVec)
    {
    UINT kSum1 = 0;
    UINT kSum2 = 0;


    for (UINT k=0; k& vecGroupSizes)
    {
    UINT kEvenTotal = 0;
    UINT kNumGroups = vecGroupSizes.size();
    vector kvecOdds;
    for (UINT k=0; k<kNumGroups ;++k)
    {
    if ( 0 == vecGroupSizes[k] % 2 )
    kEvenTotal += vecGroupSizes[k];
    else
    kvecOdds.push_back(vecGroupSizes[k]);
    }

    sort(kvecOdds.rbegin(), kvecOdds.rend()); // sort into descending order

    UINT kS = kEvenTotal/2;
    kS += kCalcTotalOfLargerPartition(kvecOdds);

    return kS;
    }

    [/code]



  • [code]
    #include
    #include

    using namespace std ;

    static UINT kCalcTotalOfLargerPartition(const vector& kDescendingVec)
    {
    UINT kSum1 = 0;
    UINT kSum2 = 0;


    for (UINT k=0; k& vecGroupSizes)
    {
    UINT kEvenTotal = 0;
    UINT kNumGroups = vecGroupSizes.size();
    vector kvecOdds;
    for (UINT k=0; k<kNumGroups ;++k)
    {
    if ( 0 == vecGroupSizes[k] % 2 )
    kEvenTotal += vecGroupSizes[k];
    else
    kvecOdds.push_back(vecGroupSizes[k]);
    }

    sort(kvecOdds.rbegin(), kvecOdds.rend()); // sort into descending order

    UINT kS = kEvenTotal/2;
    kS += kCalcTotalOfLargerPartition(kvecOdds);

    return kS;
    }

    [/code]



  • I posted the same message twice because on the first post I received an error message that something bad had happened, and assumed the post had not been made.


Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

In this Discussion