Ігральні кості#2373

Ігральні кості

3 секунди

256 мегабайтів

Легка

Феадагор любить грати в настільні рольові ігри. Нещодавно він знайшов нову гру та хоче зіграти в неї з друзями. На жаль, зараз він не може їх запросити, бо для гри потрібен незвичайний набір кубиків. Згідно з описом гри, потрібно $n$ кубиків, а на $i$ -му кубику має бути $a_{i}$ a_i граней. Кожен кубик має бути зроблений так, щоб усі його грані випадали з однаковою ймовірністю.

За правилами гри числа від $1$ до $m$ , де $m = a_{1} + a_{2} + \dots + a_{n}$ m = a_1 + a_2 + \dots + a_n, потрібно розподілити по всіх гранях так, щоб кожне число з цього діапазону було використане рівно один раз. Розташування треба вибрати так, щоб при одночасному киданні всіх кубиків математичне сподівання $E$ суми випадших чисел було максимальним.

У правилах сказано, що лише Майарі є достатньо мудрими, щоб правильно розмістити числа (тож ваша єдина опція — купити ці кубики за $133$ долари; телепатія нині досить дорога). Але, можливо, є простіший спосіб знайти оптимальне розташування?

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 1000$ 1 \leq n \leq 1000). Другий рядок містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n ( $1 \leq a_{i} \leq 100$ 1 \leq a_i \leq 100).

Вихідні дані

Виведіть максимально можливе математичне сподівання $E$ — дійсне число рівно з $5$ знаками після десяткової крапки.

А далі виведіть $n$ рядків, які описують розташування чисел: $i$ -й рядок повинен містити $a_{i}$ a_i чисел, які треба написати на гранях $i$ -го кубика.

Приклади

Приклад 1