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





Задача C. Заплыв.

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

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

Брат Маши Витя очень любит плавать. Разумеется, плавание в бассейне отличается от плавания в реке. Рельеф берега и дна сильно влияет на течение, а температура воды — на время пребывания в ней. Благодаря жаре вода в реке хорошо прогрелась, и Витя знает, что при такой температуре воды он может плавать долго — в течение времени 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

 


Сдать задачу

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