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
OK, so the example data has the groups (let's label them as A B C D) seated as: Code: AAAAAAAAAABBBBB AAAAAAAAAACCCD- 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.
