Задача A. Фасады
Задачу добавил: alef
Успешно сдано решений: 486
Ограничения по времени: 2 с на тест
Ограничения по памяти: 256 Мб
Несмотря на то, что трамвай будет ехать с очень высокой скоростью, мэра беспокоит вид из окна трамвая, который откроется болельщикам и гостям города. Поэтому он решил, что нужно покрасить фасады домов, стоящих вдоль трамвайных путей.
Однако мэр никак не может определиться, в какой цвет он хотел бы покрасить фасады: ему одинаково симпатичны два цвета. Для определенности будем их называть первый цвет и второй цвет. Краска первого цвета поставляется в банках ёмкостью a литров, а краска второго цвета — в банках ёмкостью b литров.
Будем считать, что все n домов, фасады которых решено покрасить, расположены вдоль одной линии. Занумеруем их последовательно числами от 1 до n. Специальная измерительная комиссия уже выяснила, что для покраски фасада здания #j потребуется sj литров краски.
Впрочем, фирмы, занимающиеся покраской фасадов, заявили мэру и комиссии, что технологический процесс не позволяет использовать краску, оставшуюся после покраски одного дома, при покраске другого. Так что даже если из банки с краской был использован всего один литр, оставшуюся часть придётся утилизировать.
Это обстоятельство огорчило мэра. Поэтому он сформулировал следующие условия.
Во-первых, фасады домов с номерами от 1 до некоторого k (его и предстоит найти) должны быть покрашены в один из понравившихся мэру цветов (неважно, в какой именно), а фасады домов с номерами от k + 1 до n должны быть покрашены в другой из понравившихся ему цветов. При этом и в первый цвет, и во второй цвет должно быть покрашено хотя бы по одному фасаду.
Во-вторых, суммарное количество краски, которое придётся утилизировать ввиду особенностей технологического процесса, должно быть минимально возможным.
В-третьих, если существуют несколько вариантов покраски фасадов, удовлетворяющих первым двум условиям, мэр хочет, чтобы количество домов, фасады которых будут выкрашены в один цвет, отличалось от количества домов, фасады которых будут выкрашены в другой цвет, на минимально возможную величину.
Наконец, если и в этом случае существует более одного варианта покраски, мэр согласен на любой из них.
В первой строке содержатся целые числа n, a, b (2 ≤ n ≤ 3·105, 1 ≤ a, b ≤ 106) — количество домов, фасады которых нужно покрасить, ёмкость банки краски первого цвета, ёмкость банки краски второго цвета.
Во второй строке содержится n целых чисел s1, s2, ..., sn (1 ≤ sj ≤ 106, j = 1, 2, ..., n), где sj — количество литров краски, которое требуется для покраски фасада дома #j.
Выведите целые числа r, k и 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, то остатки будут следующими:
Для второго цвета остатки будут такими:
Если первые 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.