e-olymp
Yarışlar

ACM ICPC 2011–2012, NEERC 2011

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

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

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

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

Входные данные

Первая строка содержит значение n (1 n1000). Следующая строка содержит n целых чисел a1, a2 ... an (1ai100).

Выходные данные

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

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

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
2
1 4
Çıxış verilənləri #1
7.500000
5
4 3 2 1