| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Мама купила мальчику Васе $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ドル$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $ n \le 2$ |
| 2 | 12 | $k \le 500,ドル $ a_i \le 500 $ |
| 3 | 13 | $k \le 20,000円,ドル $ a_i \le 2000 $ |
| 4 | 12 | $k \le 40,000円$ |
| 5 | 10 | $k \le 200,000円$ |
| 6 | 11 | $k \le 4 \cdot 10^6,ドル $ a_i \le 2000 $ |
| 7 | 15 | $k \le 5 \cdot 10^6$ |
| 8 | 17 |
1 2 5
0.8
2 6 5 10
0.72
2 7 4 4
0.875
2 3 4 5
0.75
4 444 57 179 239 2
0.97557326850704739751
2 5 2 2
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$
Olympiad > Moscow Open Olympiad in Informatics > Moscow Open Olympiad in Informatics 2022-23 > Day 1 Tetris번