Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Задача A. Фасады

Задачу добавил: alef

Успешно сдано решений: 452

Ограничения по времени: 2 с на тест

Ограничения по памяти: 256 Мб

Несмотря на то, что трамвай будет ехать с очень высокой скоростью, мэра беспокоит вид из окна трамвая, который откроется болельщикам и гостям города. Поэтому он решил, что нужно покрасить фасады домов, стоящих вдоль трамвайных путей. 

Однако мэр никак не может определиться, в какой цвет он хотел бы покрасить фасады: ему одинаково симпатичны два цвета. Для определенности будем их называть первый цвет и второй цвет. Краска первого цвета поставляется в банках ёмкостью a литров, а краска второго цвета — в банках ёмкостью b литров.

Будем считать, что все n домов, фасады которых решено покрасить, расположены вдоль одной линии. Занумеруем их последовательно числами от 1 до n. Специальная измерительная комиссия уже выяснила, что для покраски фасада здания #j потребуется sj литров краски. 

Впрочем, фирмы, занимающиеся покраской фасадов, заявили мэру и комиссии, что технологический процесс не позволяет использовать краску, оставшуюся после покраски одного дома, при покраске другого. Так что даже если из банки с краской был использован всего один литр, оставшуюся часть придётся утилизировать. 

Это обстоятельство огорчило мэра. Поэтому он сформулировал следующие условия.

Во-первых, фасады домов с номерами от 1 до некоторого k (его и предстоит найти) должны быть покрашены в один из понравившихся мэру цветов (неважно, в какой именно), а фасады домов с номерами от k + 1 до n должны быть покрашены в другой из понравившихся ему цветов. При этом и в первый цвет, и во второй цвет должно быть покрашено хотя бы по одному фасаду.

Во-вторых, суммарное количество краски, которое придётся утилизировать ввиду особенностей технологического процесса, должно быть минимально возможным.

В-третьих, если существуют несколько вариантов покраски фасадов, удовлетворяющих первым двум условиям, мэр хочет, чтобы количество домов, фасады которых будут выкрашены в один цвет, отличалось от количества домов, фасады которых будут выкрашены в другой цвет, на минимально возможную величину.

Наконец, если и в этом случае существует более одного варианта покраски, мэр согласен на любой из них.

Входные данные

В первой строке содержатся целые числа nab (2 ≤ n ≤ 3·105, 1 ≤ a, b ≤ 106) — количество домов, фасады которых нужно покрасить, ёмкость банки краски первого цвета, ёмкость банки краски второго цвета.

Во второй строке содержится n целых чисел s1, s2, ..., sn (1 ≤ sj ≤ 106, j = 1, 2, ..., n), где sj — количество литров краски, которое требуется для покраски фасада дома #j

Выходные данные

Выведите целые числа rk и f.

Число r — минимально возможное количество краски, которое придётся утилизировать.

Числа k и f описывают план покраски.

Если f = 1, то фасады домов с #1 по #k следует покрасить в первый цвет, а фасады домов с #(k + 1) по #n — во второй цвет.

Если же f = 2, то фасады домов с #1 по #k следует покрасить во второй цвет, а фасады домов с #(k + 1) по #n — в первый цвет.

При выводе разделяйте числа пробелами или переводами строк.

Система оценки

Важно! Обратите внимание, что первый и третий примеры не удовлетворяет условиям подзадачи 2. Решение принимается на проверку на полном наборе тестов, только если оно выводит правильные ответы на все тесты из условия.

Подзадача 1 (до 20 баллов)

2 ≤ n ≤ 100,  1 ≤ a,  b ≤ 100, 1 ≤ sj ≤ 100.

Баллы начисляются за каждый пройденный тест.

Подзадача 2 (до 20 баллов)

2 ≤ n ≤ 3·105,  2 ≤ a,  b ≤ 3, 1 ≤ sj ≤ 106.

Баллы начисляются за каждый пройденный тест.

Подзадача 3 (до 60 баллов)

Все величины из условия могут принимать любые допустимые значения.

Баллы начисляются в случае прохождения всей группы тестов.

По запросу сообщается первый непройденный тест.

Примеры

входные данные
10 5 3
11 7 2 4 9 8 10 13 19 14
выходные данные
11 6 2
входные данные
10 2 3
17 21 4 2 14 12 11 23 9 3
выходные данные
4 5 1
входные данные
5 1 2
3 6 8 2 5
выходные данные
1 2 2

Примечание

Поясним приведённые примеры.

Рассмотрим первый пример.

Выпишем для каждого здания количество неизрасходованной краски при покраске его в первый цвет. Поскольку банка краски первого цвета имеет ёмкость 5, то остатки будут следующими: 

4,  3,  3,  1,  1,  2,  0,  2,  1,  1
(действительно, если требуется 11 литров краски, то две банки будут израсходованы полностью, а из третьей банки будет использован только один литр, а 4 останутся).

Для второго цвета остатки будут такими: 

1,  2,  1,  2,  0,  1,  2,  2,  2,  1
.

Если первые 6 зданий будут покрашены во второй цвет, то неизрасходованной краски наберётся 7 литров (1 + 2 + 1 + 2 + 0 + 1). Здания с 7 по 10 будут покрашены в первый цвет, и неизрасходованной краски будет 4 литра (0 + 2 + 1 + 1).

Во втором примере, как можно заметить, здание #6 может быть покрашено в любой из двух цветов, и оставшейся краски при этом не будет.

Однако, поскольку мэр хочет, чтобы количество зданий, покрашенных в один цвет, отличалось от количества зданий, покрашенных в другой цвет, на минимально возможную величину, корректным ответом будет именно 4 5 1, а вывод 4 6 1не будет считаться корректным ответом.

Третий пример иллюстрирует ситуацию, в которой выгоднее всего покрасить все здания в один цвет (в первый, поскольку банка краски этого цвета имеет ёмкость 1). Однако, поскольку существует требование покрасить в каждый из двух цветов хотя бы по одному зданию, минимально возможный расход краски будет составлять именно 1, а не 0. 

Также заметим, что в третьем примере корректными ответами будут и 1 3 2, и 1 2 1, и 1 3 1.

Сдать задачу

Задать вопрос жюри по этой задаче