06/04/2025 16:12:09

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

648. Космическая станция

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

На международной космической станции много центрифуг в каждой лаборатории. Каждая центрифуга имеет несколько (

$N$ ) отделений, в каждое из которых можно поместить 0, 1 или 2 образца. Вы должны написать программу, которая позволит разместить

$M$ образцов по отделениям центрифуги, таким образом, чтобы число образцов в отделении не превышало 2 и следующее выражение для IMBALANCE было минимальным:

$N$
IMBALANCE =

$∑$

$|\ "МО"_i\ -\ "СМ"\ |$

$i=1$

где

$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

23/10/1998	Личное первенство университета по программированию (3)
24/10/2007	Занятие 7 (C)