Задача №115250. Ещё одна $n$-мерная шоколадка
Мама купила мальчику Васе \(n\)-мерную шоколадку, представляющую собой \(n\)-мерный куб, у которого длина каждой стороны равна \(1\). У шоколадки намечено разделение на дольки. По \(i\)-му измерению ее можно разделить гиперплоскостями на \(a_i\) равных частей. Таким образом, шоколадка делится суммарно на \(a_1 \cdot a_2 \cdot a_3 \cdot \ldots \cdot a_n\) долек, у каждой дольки длина по \(i\)-му измерению равна \(\frac{1}{a_i}\), соответственно объём каждой дольки равен \(\frac{1}{a_1 a_2 \cdots a_n}\).
Вася с друзьями хочет разрезать шоколадку, чтобы получилось хотя бы \(k\) кусочков, при этом Вася хочет максимизировать объем наименьшего из них. Резать шоколадку можно только по местам соединения долек, причём каждый разрез должен проходить через всю шоколадку вдоль некоторой гиперплоскости, участвующей в образовании долек. Только сделав все разрезы, Вася разбирает шоколадку на кусочки.
Более формально, Вася хочет выбрать числа \(b_1, b_2, \dots, b_n\) (\(1 \le b_i \le a_i\)) — количество частей на которые Вася разрежет шоколадку вдоль каждого измерения. Должно выполняться условие \(b_1 \cdot b_2 \cdot \ldots \cdot b_n \ge k\), чтобы получить не менее \(k\) кусочков после всех разрезаний. Можно заметить, что при оптимальном разрезании с такими параметрами, минимальный кусочек будет содержать \(\lfloor \frac{a_1}{b_1} \rfloor \dotsm \lfloor \frac{a_n}{b_n} \rfloor\) долек, а его объём будет равен \(\lfloor \frac{a_1}{b_1} \rfloor \dotsm \lfloor \frac{a_n}{b_n} \rfloor \cdot \frac{1}{a_1 a_2 \cdots a_n}\).
Вася хочет получить максимальное возможное значение объема минимального кусочка, умноженного на \(k\), то есть он хочет максимизировать число \(\lfloor \frac{a_1}{b_1} \rfloor \dotsm \lfloor \frac{a_n}{b_n} \rfloor \cdot \frac{1}{a_1 a_2 \cdots a_n} \cdot k\). Помогите ему в этом.
В первой строке даны два целых числа \(n\) и \(k\) \((1 \le n \le 100\), \(1 \le k \le 10^7)\) — размерность шоколадки, и на сколько частей её нужно поделить.
Во второй строке даны \(n\) целых чисел \(a_1,\ a_2,\ \dots,\ a_n\) \((1 \le a_i \le 10^7)\) — количество кусочков, на которое размечена шоколадка вдоль каждого из измерений.
Выведите одно число — максимальный возможный объём наименьшего из полученных кусочков, умноженный на \(k\), с абсолютной или относительной погрешностью не более \(10^{-9}\).
Если при заданных ограничениях разрезать шоколадку хотя бы на \(k\) кусочков невозможно, выведите \(0\).
В первом примере одномерную шоколадку можно разделить так:
Тогда ответ будет \(\frac{2}{5} \cdot 2 = 0.8\)
Во втором примере шоколадку можно разрезать следующим образом:
Тогда ответ будет \(\frac{2}{5} \cdot \frac{3}{10} \cdot 6 = 0.72\)
В третьем примере шоколадку можно разрезать следующим образом:
Тогда ответ будет \(\frac{2}{4} \cdot \frac{1}{4} \cdot 7 = 0.875\)
Тесты к этой задаче состоят из 8 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | ||||||
| Группа | Баллы | \(n\) | \(k\) | \(a_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 10 | \( n \le 2\) | – | – | – | |
| 2 | 12 | – | \(k \le 500\) | \( a_i \le 500 \) | 0 | |
| 3 | 13 | – | \(k \le 20\,000\) | \( a_i \le 2000 \) | 0, 2 | |
| 4 | 12 | – | \(k \le 40\,000\) | – | 0, 2, 3 | |
| 5 | 10 | – | \(k \le 200\,000\) | – | 0, 2, 3, 4 | |
| 6 | 11 | – | \(k \le 4 \cdot 10^6\) | \( a_i \le 2000 \) | 0, 2, 3 | |
| 7 | 15 | – | \(k \le 5 \cdot 10^6\) | – | 0, 2 – 6 | |
| 8 | 17 | – | – | – | 0 – 7 | Offline-проверка. |
1 2 5
0.80000000000000004441
2 6 5 10
0.71999999999999997335
2 7 4 4
0.87500000000000000000
2 3 4 5
0.75000000000000000000
4 444 57 179 239 2
0.97557326850704739751
2 5 2 2
0.00000000000000000000