First Hellenic Internet Programming Contest
30 November 1996

Problem 2 - A Variation of Bin-packing

The bin-packing problem is well known from theory and practice. Given an 
infinite population of numbered bins, each of capacity 1, and a set of 
objects with weight smaller than 1, the problem is to find the minimum 
number of bins which can accommodate the set of objects. The exact solution 
may be found after exhaustive enumeration. Among the proposed suboptimal 
heuristics, the FIRST FIT DECREASING (FFD) method is a simple and efficient 
one. According to FFD, first we order the objects with decreasing weight, 
and then we place each object in the first bin which can accommodate it.

We have to solve a variation of the classical bin-packing problem, where the 
bins have different capacities. Try to adapt the FFD algorithm in the new 
environment. Basically, you have to assign the objects (which are ordered 
decreasingly again) to the bins, which are also ordered according to 
decreasing capacity. If there are two or more objects with equal weight, 
or two or more bins with equal capacity, then in both cases we sort them 
according to their id's (i.e. order in the input). The key idea behind the 
proposed algorithm is that again the aim is to minimize the number of used 
bins. Therefore, it is better to use a few large bins instead of more small 
ones.

Input
Your program should read the INPUT2.TXT file, which has three lines. 
- The first line contains the number of bins, b<=20, and the number of 
objects, o<=100. 
- The second line contains b integers (in the range 1..10) representing the 
bin capacities. 
- The third line contains o reals (in the range 0.1..9.9) representing the 
object weights. 
The numbers in each line are separated by space characters. Note, also, that 
each bin and each object is characterized by an id equal to its order in the 
respective line of the input.

Output
Output your results in the OUTPUT2.TXT file, which contains b lines. Each 
line corresponds to a bin (sorted in the order of the bins as given in the 
input file) and contains the object id's (sorted in the order of the objects 
as given in the input file), which are assigned to the specific bin. If a 
bin is not assigned any object, then the respective line contains a zero. 
Note, also, that the object id's in each line are separated by space 
characters.

Example 1
Input
4 5
2 4 1 6
0.5 2.5 3 1.2 0.8

Output
0
4 5
0
1 2 3

Example 2
Input
4 5
3 2 3 2
0.5 1.5 1.5 2 0.5

Output
1 4 5
0
2 3
0