Занятие 7

На международной космической станции много центрифуг в каждой лаборатории. Каждая центрифуга имеет несколько (`N`) отделений, в каждое из которых можно поместить 0, 1 или 2 образца. Вы должны написать программу, которая позволит разместить `M` образцов по отделениям центрифуги, таким образом, чтобы число образцов в отделении не превышало 2 и следующее выражение для IMBALANCE было минимальным:

где `MО_i` – это масса `i`-го отделения, равная сумме масс образцов в `i`-ом отделении

`СM` – это средняя масса отделения и равна сумме масс всех образцов, деленной на число отделений (`N`).

Входной файл содержит несколько наборов данных. Первая строка каждого набора содержит два числа, разделенных пробелом. Первое число `N` (`1\ ≤\ N\ ≤\ 5`) определяет число отделений в центрифуге, а второе число `M` (`1\ ≤\ M\ ≤\ 2*N`) определяет число образцов. Вторая строка содержит `M` чисел (от 1 до 1000), разделенных пробелом, представляющие массы образцов. Ввод завершается строкой с двумя нулями.

В выходной файл для каждого набора вы должны напечатать строку с номером набора в формате "Set #`X`" где `X` – номер набора, нумерация начинается с 1. Следующие `N` строк содержат номер отделения в первой колонке, двоеточие во второй колонке и массы образцов, начиная с четвертой колонки, разделенных одним пробелом. Далее ваша программа должна напечатать значение IMBALANCE с точностью 5 знаков после запятой (т.е. десятичной точки). После результатов для каждого набора (в т.ч. и самого последнего) вывести пустую строку.

2 3
6 3 8
3 5
51 19 27 14 33
5 9
1 2 3 5 7 11 13 17 19
0 0

Set #1
1: 3 6
2: 8
IMBALANCE 1.00000

Set #2
1: 14 33
2: 19 27
3: 51
IMBALANCE 6.00000

Set #3
1: 1 17
2: 2 13
3: 3 11
4: 5 7
5: 19
IMBALANCE 11.60000