eolymp
bolt
Try our new interface for solving problems
Məsələlər

Игральные кости

Игральные кости

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Наряду с другими вещами, Фидагор любит играть в настольные ролевые игры. Он только что изобрел новую игру, в которую хотел бы сыграть со своими друзьями. К несчастью, он не может собрать друзей прямо сейчас, потому что для игры требуется достаточно необычный набор игральных костей. В описании игры сказано, что для нее требуется n костей, причем i-ая кость должна иметь a_i граней. Каждая кость должна иметь форму, при которой выпадение любой грани будет равновероятным.

Согласно правилам игры, на гранях кубика записаны числа от 1 до m, где m = , причем каждое число из указанного интервала записано лишь один раз. Числа на гранях должны быть выбраны таким образом, что при одновременном броске всех кубиков математическое ожидание E суммы выпавших чисел максимально.

Руководство пользователя говорит, что только у Майара хватит мудрости расставить числа правильно (и, следовательно, ваш единственный выбор - купить кости только за 133 доллара, телепатия сейчас довольно дорого стоит). Но, возможно, есть более простой способ найти надлежащее расположение?

Giriş verilənləri

Первая строка содержит значение n (1 n1000). Следующая строка содержит n целых чисел a_1, a_2 ... a_n (1a_i100).

Çıxış verilənləri

В первой строке следует вывести максимальное возможное ожидание E - действительное число с точностью до 5 знаков после десятичной запятой.

Следующие n строк содержат расположение чисел: i-ая строка содержит a_i целых чисел - чисел, записанных на гранях i-ой кости.

Nümunə

Giriş verilənləri #1
2
1 4
Çıxış verilənləri #1
7.500000
5
4 3 2 1