Помогите решить задание из олимпиады по программированию

У Жени накопился большой список игр разных жанров. Он решил разбить их на две непустых папки так, чтобы игры из первой части списка попали в одну папку, а из второй — в другую.

Женя решил оценить энтропию получившегося разбиения, однако на его калькуляторе отсутствует функция логарифма, поэтому он решил оценивать качество распределения жанров игр по папкам при помощи следующей оценки:

где N1 и N2 — число игр в первой и второй папке соответственно, K — число возможных жанров, а pf,i — вероятность встретить игру жанра i в f-й папке. Эта вероятность оценивается как pf,i = countf[i] / Nf, где countf[i] — число игр жанра i в f-й папке.

Помогите Жене определить качество распределения жанров игр по папкам для всех возможных непустых разбиений списка игр.

Замечание
В первом примере оценка второго разбиения вычисляется следующим образом:

Формат входных данных
Первая строка содержит два разделённых пробелом натуральных числа N и K (2 <= N,K <= 105) — число игр и жанров.

Вторая строка содержит N разделённых пробелом натуральных чисел ci (1 <= ci <= K) — жанры соответствующих игр.

Формат выходных данных
Выведите N − 1 вещественное число с плавающей точкой — оценку качества распределения жанров игр по папкам для соответствующих разбиений. Разбиения упорядочены по возрастанию числа игр в первой папке.

Ответ считается верным, если его относительная или абсолютная погрешность не превышает 10−9 .

Пример 1
Входные данные:
5 3
1 1 2 2 3

Выходные данные:
0.5
0.2666666666666666
0.46666666666666656
0.4

Пример 2
Входные данные:
5 3
1 2 3 2 1

Выходные данные:
0.5
0.6
0.6
0.5