[Cnoi2021] 自我主义的平衡者
题目背景
「流浪月球 ~ The Wandering Moon」在幻想乡上映了。
正如一千个人心中有一千个哈姆雷特,关于它的争议也在悄然蔓延。
不知何时起,一个叫做「花瓣」的平台出现,慢慢取代了市井之中的讨论声,成为了争议的主战场——因为它具有评分功能。平台上旁征博引、各抒己见的评分帖成为了幻想乡的居民们日常,一切看起来岁月静好。
直到平衡者的出现。
起初没有人在意在意这缕杂音,这只不过是一种无心的叛逆,一点无奈的情感,一次无聊的宣泄。直到平衡的思想深入人心,自我主义的狂潮达到顶峰,评分系统的秩序几近崩溃。
Cirno 觉得自己该做些什么了。
题目描述
Cirno 决定通过计算来说服与拯救被自我主义裹挟的众人。
参与评分的共有 $n$ 位居民,平台限制的最高分为 $m$。
每个居民在评分前都有一个心理预期分数 $a_i(a_i\in[0,m]\cap\mathbb{Z})$。
但人们并不会按照心理预期分数直接评分,而是当当前平台上的平均分严格高于自己的心理预期分数时,便评分道「分数太高了,打个 $0$ 分平衡一下」,反之则说「分数太低了,打个满分($m$分)平衡一下」。
初始时平台上的平均分为 $0$。
为了证明这种评分方式对公平的破坏性,Cirno 希望你计算出这 $n$ 位居民在不同的排列顺序下评分,平台上最终平均分可能的最大值与最小值。
输入输出格式
输入格式
第一行,两个整数,用空格隔开,表示 $n$,$m$。
第二行,$n$ 个整数,用空格隔开,表示 $\{a_n\}$。
输出格式
一行,两个实数,保留两位小数,分别表示平均分最大值和最小值。
输入输出样例
输入样例 #1
5 5
1 2 3 4 5
输出样例 #1
4.00 2.00
输入样例 #2
7 114
23 75 35 17 101 55 73
输出样例 #2
81.43 32.57
说明
**数据范围与约定**
对于 $100\%$ 的数据保证,$1 < n,m\le 10^5$,$a_i \in [0,m]$。
**子任务**
Subtask1(10 points):$n \le 8$。
Subtask2(10 points):$n \le 20$。
Subtask3(30 points):$n \le 10^3$。
Subtask4(50 points):无特殊限制。