Задача C. Заплыв.
Задачу добавил: alef
Успешно сдано решений: 57
Брат Маши Витя очень любит плавать. Разумеется, плавание в бассейне отличается от плавания в реке. Рельеф берега и дна сильно влияет на течение, а температура воды — на время пребывания в ней. Благодаря жаре вода в реке хорошо прогрелась, и Витя знает, что при такой температуре воды он может плавать долго — в течение времени T.
Обычно Витя заходит в воду в каком-либо месте пляжа строго напротив какого-нибудь буйка, доплывает до него (за пренебрежимо малое время :)) и затем плывет вдоль буйков. Витя плавает каждый день, и для каждой соседней пары буйков (j и j+1) он знает время tj, за которое он доплывает от одного до другого.
Вите стало интересно, мимо какого наибольшего количества буйков он может проплыть за время T. Ваша задача — вычислить это количество. Определите также номер буйка, напротив которого ему нужно войти в воду, и номер последнего буйка, мимо которого он проплывет.
Формат входного файла input.txt
Первая строка — целые числа N (2 <= N <= 100500) и T (1 <= Т <= 10^9) через пробел — количество буйков и время, в течение которого Витя может находиться в воде.
В каждой из следующих N – 1 строк содержится время, за которое Витя может проплыть между очередной парой буйков: во второй строке — между буйками # 1 и # 2, в третьей — между буйками # 2 и # 3 и т.д.
Все времена положительны и не превосходят 10^9
Формат выходного файла output.txt
Первая строка — целое число — максимально возможное количество буйков, мимо которых может проплыть Витя (буек, напротив которого он вошел в воду, учитывается).
Вторая строка — два целых числа через пробел — номер буйка, напротив которого Витя должен войти в воду, и номер последнего буйка, мимо которого он проплывет. Если существует несколько вариантов, выведите тот, в котором стартовый буек имеет наименьший номер.
Решения, работающие для N <= 1000, могут набрать 40 баллов
Пример входного файла — 1
10 25
12
13
4
6
9
6
5
11
4
Пример выходного файла — 1
5
3 7
Пример входного файла — 2
20 25
2
3
4
6
10
6
5
11
4
1
1
2
2
3
4
5
18
28
2
Пример выходного файла — 2
9
9 17