problem number 1

Discussion in 'C' started by lmfaomanwtf, Mar 31, 2011.

  1. lmfaomanwtf

    lmfaomanwtf Banned

    Mar 31, 2011
    Likes Received:
    Trophy Points:
    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...


    file in.txt
    20 5 3 1

    output: 15
  2. xpi0t0s

    xpi0t0s Mentor

    Aug 6, 2004
    Likes Received:
    Trophy Points:
    Senior Support Engineer
    OK, so the example data has the groups (let's label them as A B C D) seated as:
    If you start by adding up the group sizes (29), divide by 2 and round up (15) that'll give you a lower bound. You definitely can't fit the people in to fewer seats than that.

    The next step would be to see if you can fit the people into that many seats.

    If you can, then you have a solution. If not, then increase the number of seats by 1 and try again.

    The tricky bit is going to be assigning the seats. You don't have to find the optimal packing; the rest of the algorithm will take care of that, so you only need to know if it is possible.

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice