Серая зона
Доктор Грей — аналитик данных, который ежедневно визуализирует различные аспекты данных, поступающих со всего мира. Хотя он отлично владеет сложными инструментами визуализации, его любимым инструментом остается простой самодельный генератор гистограмм.
Рисунок 1: Гистограмма
Рисунок 1 демонстрирует пример гистограммы, автоматически созданной его генератором. Гистограмма представляет собой визуальное отображение частот значений в виде столбцов. В этом примере значения в диапазоне 0–9 встречаются пять раз, в диапазоне 10–19 — три раза, а в диапазонах 20–29 и 30–39 — по одному разу.
Генератор гистограмм доктора Грея — это простой инструмент. Во-первых, высота гистограммы фиксирована, то есть высота самого высокого столбца всегда одинакова, а высоты остальных регулируются пропорционально. Во-вторых, ширина столбцов также фиксирована. Он может создавать гистограммы только с равномерными интервалами, то есть каждый интервал должен иметь одинаковую ширину (10 в приведенном примере). Наконец, столбцы окрашены в серый цвет, где самый левый и самый правый столбцы — черный и белый соответственно, а темнота столбцов монотонно уменьшается слева направо. Например, в Рисунке 1 уровни темноты четырех столбцов составляют 1, 2/3, 1/3 и 0 соответственно.
В этой задаче вам нужно оценить расход чернил при печати гистограммы на бумаге. Количество чернил, необходимое для рисования столбца, пропорционально его площади и темноте.
Входные данные
Входные данные состоят из нескольких наборов, каждый из которых содержит целые числа и задает таблицу значений и интервалы для генератора гистограмм в следующем формате.
n w
v_1
v_2
...
v_n
n — это общее количество значений для гистограммы, и каждая из n строк, следующих за первой строкой, содержит одно значение. Обратите внимание, что одно и то же значение может встречаться несколько раз.
w — это ширина интервала. Значение v находится в первом (т.е. самом левом) интервале, если 0 ≤ v < w, во втором, если w ≤ v < 2w, и так далее. Обратите внимание, что интервал от 0 (включительно) до w (исключительно) следует рассматривать как самый левый, даже если в этом интервале нет значений. Последний (т.е. самый правый) интервал — это тот, который включает наибольшее значение в наборе данных.
Вы можете предположить следующее.
1 ≤ n ≤ 100
10 ≤ w ≤ 50
0 ≤ v_i ≤ 100 для 1 ≤ i ≤ n
Также можно предположить, что максимальное значение не меньше w. Это означает, что гистограмма имеет более одного интервала.
Конец ввода обозначается строкой, содержащей два нуля.
Выходные данные
Для каждого набора данных выведите строку, содержащую количество чернил, израсходованных на печать гистограммы.
Одна единица чернил необходима для окрашивания одного самого высокого столбца в черный цвет. Предположим, что 0.01 единиц чернил на гистограмму расходуется на различные цели, кроме окрашивания столбцов, такие как рисование линий и символов (см. Рисунок 1). Например, количество чернил, израсходованных на печать гистограммы в Рисунке 1, составляет:
Каждое выходное значение должно быть в виде десятичной дроби и может иметь ошибку менее 10^{−5}.