CF200E.Tractor College
提高+/省选-
通过率:0%
时间限制:4.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
While most students still sit their exams, the tractor college has completed the summer exam session. In fact, students study only one subject at this college — the Art of Operating a Tractor. Therefore, at the end of a term a student gets only one mark, a three (satisfactory), a four (good) or a five (excellent). Those who score lower marks are unfortunately expelled.
The college has n students, and oddly enough, each of them can be on scholarship. The size of the scholarships varies each term. Since the end-of-the-term exam has just ended, it's time to determine the size of the scholarship to the end of next term.
The monthly budget for the scholarships of the Tractor college is s rubles. To distribute the budget optimally, you must follow these rules:
- The students who received the same mark for the exam, should receive the same scholarship;
- Let us denote the size of the scholarship (in roubles) for students who have received marks 3, 4 and 5 for the exam, as _k_3, _k_4 and _k_5, respectively. The values _k_3, _k_4 and _k_5 must be integers and satisfy the inequalities 0 ≤ _k_3 ≤ _k_4 ≤ _k_5;
- Let's assume that _c_3, _c_4, _c_5 show how many students received marks 3, 4 and 5 for the exam, respectively. The budget of the scholarship should be fully spent on them, that is, _c_3·_k_3 + _c_4·_k_4 + _c_5·_k_5 = s;
- Let's introduce function
— the value that shows how well the scholarships are distributed between students. In the optimal distribution function f(_k_3, _k_4, _k_5) takes the minimum possible value.
Given the results of the exam, and the budget size s, you have to find the optimal distribution of the scholarship.
当大多数学生仍在参加期末考试时,拖拉机学院已经结束了暑期考试。事实上,该学院的学生每学期只学习一门课程——拖拉机操作艺术。因此,学期末每位学生仅获得一个成绩:三分(合格)、四分(良好)或五分(优秀)。成绩低于三分者不幸被开除。
该学院共有 $ n $ 名学生,而颇为奇特的是,每位学生都有资格获得奖学金。每学期的奖学金金额各不相同。由于本学期期末考试刚刚结束,现在正是确定下学期奖学金金额的时候。
拖拉机学院每月用于发放奖学金的预算是 $ s $ 卢布。为实现预算的最优分配,须遵循以下规则:
- 期末考试中获得相同成绩的学生,应获得相同金额的奖学金;
- 设期末考试成绩为 3、4、5 的学生所获奖学金金额(单位:卢布)分别为 $ k_3 、 k_4 $ 和 $ k_5 $。这些值必须为整数,并满足不等式 $ 0 \leq k_3 \leq k_4 \leq k_5 $;
- 设期末考试中获得成绩 3、4、5 的学生人数分别为 $ c_3 、 c_4 、 c_5 $。奖学金预算必须全额发放完毕,即满足等式 $ c_3 \cdot k_3 + c_4 \cdot k_4 + c_5 \cdot k_5 = s $;
- 定义函数
—— 该函数值反映了奖学金在学生之间分配的均衡程度。在最优分配方案下,函数 $ f(k_3,,k_4,,k_5) $ 应取最小可能值。
给定期末考试成绩结果及预算总额 $ s $,请找出奖学金的最优分配方案。
输入格式
The first line has two integers n, s (3 ≤ n ≤ 300, 1 ≤ s ≤ 3·105) — the number of students and the budget size for the scholarship, respectively. The second line contains n integers, where the i-th number represents the mark that the i-th student got for the exam. It is guaranteed that at each mark was given to at least one student.
第一行包含两个整数 n、s(3 ≤ n ≤ 300,1 ≤ s ≤ 3⋅105)—— 分别表示学生人数和奖学金预算总额。
第二行包含 n 个整数,其中第 i 个数表示第 i 名学生在考试中获得的成绩。保证每个成绩至少被一名学生获得。
输出格式
On a single line print three integers _k_3, _k_4 and _k_5 — the sought values that represent the optimal distribution of the scholarships. If there are multiple optimal answers, print any of them. If there is no answer, print -1.
在一行中输出三个整数 k3、k4 和 k5 —— 即所求的奖学金最优分配方案。若存在多个最优解,输出其中任意一个即可;若无解,则输出 -1。
输入输出样例
输入#1
5 11 3 4 3 5 5
输出#1
1 3 3
输入#2
6 15 5 3 3 4 4 5
输出#2
-1
输入解题思路,AI测评打分。不知道怎么写?