Codeforces Round 100 |
---|
Закончено |
Пока Геральд накрывает стол, Александр отправляет открытки, а Сергей и его двойники создают армию (клонов) снеговиков, Геннадий пишет новогодний контест.
Новогодний контест начинается в 18:00 31 декабря и заканчивается в 6:00 1 января. На контесте предлагается n задач. Штрафное время по каждой сданной задаче начисляется как расстояние от момента ее сдачи до Нового года в минутах. Например, задача, сданная в 21:00 получает штрафное время 180, так же как задача, сданная в 3:00. Общее штрафное время считается как сумма штрафных времен по всем сданным задачам. Разрешается сдавать задачу ровно в момент окончания контеста 6:00.
Геннадий открыл задачи ровно в 18:00 и за первые 10 минут контеста успел оценить их сложность. Он полагает, что потратит на решение i-ой задачи ai минут. Отправить решение на проверку Геннадий сможет в любой момент времени после завершения его написания. Вероятно, ему придется отрываться от решения одной задачи, чтобы отправить на проверку решение по другим. Временем отправки решения можно пренебречь, то есть считать его равным нулю. Генндий может одновременно отправить несколько решений. Кроме того, он может в любой момент перейти от решения одной задачи к другой, а потом вернуться к первой задаче с того же места, на котором закончил. При этом суммарное время решения i-ой задачи составит также ai минут. Разумеется, Геннадий не совершает штрафных попыток, и все его решения проходят с первого раза. Он может приступать к решению задач начиная с 18:10.
Помогите Геннадию выбрать из стратегий, при которых он решит максимальное возможное количество задач, ту, при которой его общее штрафное время будут минимальным.
В первой строке задано целое число n (1 ≤ n ≤ 100) — количество задач. В следующей строке через пробел заданы n целых чисел ai (1 ≤ ai ≤ 720) — количества времени в минутах, которые Геннадий потратит на решение задач.
Выведите два целых числа — количество решенных Геннадием задач и общее штрафное время при оптимальной стратегии.
3
30 330 720
2 10
В примере одна из возможных оптимальных стратегий Геннадия такова. В 18:10 он начинает решать первую задачу и решает ее через 30 минут (в 18:40). В 18:40 он начинает решать вторую задачу. До Нового года остается 320 минут, поэтому Геннадий не успевает закончить решение второй задачи до Нового года. В 0:00 он отрывается от решения второй задачи и сдает первую, и сразу же возвращается к решению второй задачи. В 0:10 он дописывает решение по второй задаче и сдает его, получая 10 минут штрафного времени. Заметим, что так как общая продолжительность контеста 720 минут и 10 минут Геннадий уже потратил на чтение задач, он вообще не успеет решить за контест третью задачу. Да, такие задачи бывают.
Соревнования по описанным правилам ежегодно проходят на сайте http://b23.ru/3wvc
Название |
---|