Howdy, Stranger!

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

Categories

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

  • BannerdogBannerdog Member Posts: 12
    [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]


  • BannerdogBannerdog Member Posts: 12

    [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]


  • BannerdogBannerdog Member Posts: 12

    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.