1. We have moved from vBulletin to XenForo and you are viewing the site in the middle of the move. Though the functional aspect of everything is working fine, we are still working on other changes including the new design on Xenforo.
    Dismiss Notice

problem number 1

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

  1. lmfaomanwtf

    lmfaomanwtf Banned

    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

    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