printРабочее место участника

printЗадачи

1699. K-квест

Ограничения: время – 500ms/1000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В одной из компьютерных игр-квестов есть следующее задание. На карте игрового мира размещены `N` персонажей, с каждым из которых может встретиться игрок. От общения с `i`-м персонажем карма игрока меняется на величину `a_i`, которая может быть как положительной, так отрицательной или даже нулем.
Изначально карма игрока равна нулю. Для того чтобы пройти на следующий уровень, нужно чтобы карма была в точности равна значению `K`, при этом карма также может принимать как положительные, так и отрицательные значения.
Комнаты, в которых находятся персонажи, соединены односторонними магическими порталами, поэтому игроку придется встречать персонажей в определенной последовательности: после персонажа номер `i` он попадает к персонажу номер `i+1`, затем к персонажу номер `i+2`, и т.д. В комнате последнего персонажа с номером `N` портала к другому персонажу нет.
Для перемещения между персонажами можно использовать еще и заклинания телепортации, но к сожалению у героя осталось всего лишь два свитка с заклинаниями. Поэтому один из этих свитков придется использовать для того, чтобы телепортироваться к любому из персонажей, а второй свиток – чтобы покинуть игровой мир, после того, как карма героя станет равна `K`.
Помогите игроку определить, в какую комнату надо телепортироваться в начале и из какой комнаты нужно покинуть игровой мир, чтобы достичь кармы `K` или сообщите, что это невозможно.
В первой строке ввода записаны два числа: количество персонажей `N` (`1\ ≤\ N\ ≤\ 200\ 000`) и необходимый уровень кармы `K` (`|K|≤\ 10^9`, `K≠0`). Во второй строке через пробел записаны `N` целых чисел `a_1`, `a_2`, …, `a_N` – величины, на которые меняется карма героя после общения с персонажами с номерами 1, 2, …, `N` соответственно.
Выведите номер комнаты, в которую надо войти игроку и номер комнаты, из которой надо выйти, чтобы набрать карму `K`. Если возможных вариантов несколько, то необходимо вывести самый короткий путь, а если и таких несколько, то путь, начинающийся в комнате с как можно большим номером. Если достичь кармы `K` последовательно общаясь с персонажами невозможно, то выведите одно число `-1`.

Пример ввода 1

5 3
-2 2 -1 2 4

Пример вывода 1

2 4

Пример ввода 2

7 1
1 -1 1 -1 1 -1 2

Пример вывода 2

5 5

Пример ввода 3

4 3
2 2 2 2

Пример вывода 3

-1
Источник: Московская олимпиада школьников по информатике, 2011/12 учебный год
loading