CF140D.New Year Contest
普及+/提高
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
As Gerald sets the table, Alexander sends the greeting cards, and Sergey and his twins create an army of clone snowmen, Gennady writes a New Year contest.
The New Year contest begins at 18:00 (6.00 P.M.) on December 31 and ends at 6:00 (6.00 A.M.) on January 1. There are n problems for the contest. The penalty time for each solved problem is set as the distance from the moment of solution submission to the New Year in minutes. For example, the problem submitted at 21:00 (9.00 P.M.) gets penalty time 180, as well as the problem submitted at 3:00 (3.00 A.M.). The total penalty time is calculated as the sum of penalty time for all solved problems. It is allowed to submit a problem exactly at the end of the contest, at 6:00 (6.00 A.M.).
Gennady opened the problems exactly at 18:00 (6.00 P.M.) and managed to estimate their complexity during the first 10 minutes of the contest. He believes that writing a solution for the i-th problem will take a__i minutes. Gennady can submit a solution for evaluation at any time after he completes writing it. Probably he will have to distract from writing some solution to send the solutions of other problems for evaluation. The time needed to send the solutions can be neglected, i.e. this time can be considered to equal zero. Gennady can simultaneously submit multiple solutions. Besides, he can move at any time from writing one problem to another, and then return to the first problem from the very same place, where he has left it. Thus the total solution writing time of the i-th problem always equals a__i minutes. Of course, Gennady does not commit wrong attempts, and his solutions are always correct and are accepted from the first attempt. He can begin to write the solutions starting from 18:10 (6.10 P.M.).
Help Gennady choose from the strategies that help him solve the maximum possible number of problems, the one with which his total penalty time will be minimum.
当杰拉尔德布置餐桌、亚历山大寄送贺卡、谢尔盖和他的双胞胎兄弟制作一支克隆雪人军队时,根纳季正在编写一场新年编程竞赛题目。
这场新年编程竞赛于12月31日18:00(下午6:00)开始,至1月1日6:00(凌晨6:00)结束。竞赛共包含 n 道题目。每道被成功解答的题目的罚时定义为:从该题提交时刻到新年(即1月1日00:00)所经过的分钟数。例如,在21:00(晚上9:00)提交的题目罚时为180;同样地,在3:00(凌晨3:00)提交的题目罚时也为180。总罚时等于所有已解题目的罚时之和。允许在竞赛结束时刻(即1月1日6:00)提交题目。
根纳季恰好于12月31日18:00(下午6:00)打开题目,并在竞赛开始后的前10分钟内估算了各题难度。他估计写出第 i 道题的解法需要 ai 分钟。根纳季可在完成某题解法书写后任意时刻提交该解法以供评测。他可能需要暂时中断某题的书写,转而提交其他题目的解法以进行评测。提交解法所需的时间可忽略不计(即视为零)。根纳季可同时提交多个解法。此外,他可在任意时刻从一道题的书写切换至另一道题,并随后从之前中断处继续完成第一道题的书写。因此,第 i 道题的总书写时间恒为 ai 分钟。当然,根纳季不会提交错误解法,其所有解法均正确且总能一次通过。他最早可于12月31日18:10(下午6:10)开始书写解法。
请帮助根纳季在所有能使其解出题目数量最大化的策略中,选出总罚时最小的那一种策略。
输入格式
The first line contains an integer n (1 ≤ n ≤ 100) — the number of the problems. The next line contains n space-separated integers a__i (1 ≤ a__i ≤ 720) — each number shows how much time in minutes Gennady will spend writing a solution to the problem.
第一行包含一个整数 n(1≤n≤100)—— 表示题目的数量。
下一行包含 n 个用空格分隔的整数 ai(1≤ai≤720)—— 每个数字表示根纳季解答该题目所需的时间(单位:分钟)。
输出格式
Print two integers — the number of problems Gennady will solve and the total penalty time considering that he chooses the optimal strategy.
输出两个整数——Gennady 将解决的问题数量以及总罚时(假设他采用最优策略)。
输入输出样例
输入#1
3 30 330 720
输出#1
2 10
说明/提示
In the sample, one of Gennady's possible optimal strategies is as follows. At 18:10 (6:10 PM) he begins to write the first problem and solves it in 30 minutes (18:40 or 6.40 P.M.). At 18:40 (6.40 P.M.) he begins to write the second problem. There are 320 minutes left before the New Year, so Gennady does not have the time to finish writing the second problem before the New Year. At 0:00 (12.00 A.M.) he distracts from the second problem, submits the first one, and returns immediately to writing the second problem. At 0:10 (0.10 A.M.), he completes the solution for the second problem, submits it and gets 10 minute penalty time. Note that as the total duration of the contest is 720 minutes and Gennady has already spent 10 minutes on reading the problems, he will not have time to solve the third problem during the contest. Yes, such problems happen to exist.
Competitions by the given rules are held annually on the site http://b23.ru/3wvc
在样例中,根纳季的一种可能的最优策略如下:他在 18:10(即晚上 6:10)开始撰写第一道题,并用 30 分钟完成(即 18:40 或晚上 6:40)。他在 18:40(即晚上 6:40)开始撰写第二道题。此时距离新年还有 320 分钟,因此根纳季没有足够时间在新年之前完成第二道题的撰写。在 0:00(即凌晨 0:00)时,他暂停第二道题的撰写,提交第一道题,然后立即返回继续撰写第二道题。他在 0:10(即凌晨 0:10)完成第二道题的解答,提交后获得 10 分钟罚时。注意,由于比赛总时长为 720 分钟,而根纳季已花费 10 分钟阅读题目,因此他在比赛期间将没有时间求解第三道题。是的,此类问题确实存在。
按照给定规则举办的竞赛每年都在网站 http://b23.ru/3wvc 上举行。
输入解题思路,AI测评打分。不知道怎么写?