CF200E Tractor College
题目描述
translated by @[RebelAlliance](https://www.luogu.org/space/show?uid=92461)
------------
当大部分学生在准备考试时,拖拉机学院已经完成了夏季学期的期末考试。事实上,学生们只学一门科目——拖拉机驾驶的艺术,所以学期末学生们只有一个成绩,3分(合格),4分(良好),5分(优秀)。分数更低的,很不幸,会被开除。
学院有 $n$ 个学生,奇怪的是,每个人都拿的到奖学金。既然期末考试考完了,是时候决定下学期的奖学金数额了。
每个月的奖学金预算有 $s$ 卢布。为了更合理地分配奖学金,你必须遵守以下规则:
• 考试成绩相同的学生拿相同的奖学金
• 用 $k_3, k_4, k_5$(卢布)分别表示拿3分、4分、5分的同学获得的奖学金数额。$k_3, k_4, k_5$ 是整数且满足 $0 \leqslant k_3 \leqslant k_4 \leqslant k_5$
• 定义 $c_3, c_4,c_5$ 分别表示拿3分、4分、5分的学生人数。每月的奖学金预算必须被花完,就是说,$c_3 \times k_3 + c_4 \times k_4 + c_5 \times k_5 = s$
• 引入函数 $f(k_3, k_4,k_5)=|c_3 \times k_3 - c_4 \times k_4| +|c_4 \times k_4 - c_5 \times k_5|$ ,其值表示奖学金分配的合理程度。在最佳分配方案中,$f(k_3, k_4,k_5)$ 取最小值
给出考试的结果和每月预算 $s$,请找出奖学金最佳分配方案
输入格式
第一行包括两个整数 $n$,$s$ ($3 \leqslant n \leqslant 300 , 1 \leqslant s \leqslant 3\times 10^5$) ——学生人数和每月奖学金预算。
第二行包括 $n$ 个整数,第 $i$ 个数表示第 $i$ 个学生在考试中的得分。保证每个成绩都有至少一名学生拿到。
输出格式
一行包括两个数 $k_3. k_4,k_5$,代表最佳分配方案。如果有多组答案,输出任意一组;如果没有答案,输出"-1"(输出不带引号)