В одной из компьютерных игр-квестов есть следующее задание. На карте игрового мира размещены N персонажей, с каждым из которых может встретиться игрок. От общения с i-м персонажем карма игрока меняется на величину ai, которая может быть как положительной, так отрицательной или даже нулем.
Изначально карма игрока равна нулю. Для того чтобы пройти на следующий уровень, нужно чтобы карма была в точности равна значению K, при этом карма также может принимать как положительные, так и отрицательные значения.
Комнаты, в которых находятся персонажи, соединены односторонними магическими порталами, поэтому игроку придется встречать персонажей в определенной последовательности: после персонажа номер i он попадает к персонажу номер i + 1, затем к персонажу номер i + 2, и т.д. В комнате последнего персонажа с номером N портала к другому персонажу нет.
Для перемещения между персонажами можно использовать еще и заклинания телепортации, но к сожалению у героя осталось всего лишь два свитка с заклинаниями. Поэтому один из этих свитков придется использовать для того, чтобы телепортироваться к любому из персонажей, а второй свиток — чтобы покинуть игровой мир, после того, как карма героя станет равна K.
Помогите игроку определить, в какую комнату надо телепортироваться в начале и из какой комнаты нужно покинуть игровой мир, чтобы достичь кармы K или сообщите, что это невозможно.
В первой строке входных данных записаны два числа: количество персонажей N и необходимый уровень кармы K (|K| ≤ 109, K ≠ 0). Во второй строке через пробел записаны N целых чисел a1, a2, ..., aN — величины, на которые меняется карма героя после общения с персонажами с номерами 1, 2, ..., N соответственно.
Выведите номер комнаты, в которую надо войти игроку и номер комнаты, из которой надо выйти, чтобы набрать карму K. Если возможных вариантов несколько, то необходимо вывести самый короткий путь, а если и таких несколько, то путь, начинающийся в комнате с как можно большим номером. Если достичь кармы K последовательно общаясь с персонажами невозможно, то выведите одно число - 1.
5 3
-2 2 -1 2 4
2 4
7 1
1 -1 1 -1 1 -1 2
5 5
4 3
2 2 2 2
-1
Тесты по этой задачи разбиты на группы. На 1-3 группах тестов проверка проводится во время тура (online), на последней группе — после окончания тура (offline).
В первой группе тестов 1 ≤ N ≤ 100, |ai| ≤ 100. Баллы начисляются только при прохождении всех тестов группы, группа оценивается в 20 баллов.
Во второй группе тестов 1 ≤ N ≤ 2000, |ai| ≤ 1 000 000. Баллы начисляются только при прохождении всех тестов группы, группа оценивается в 20 баллов.
В третьей группе тестов 1 ≤ N ≤ 200 000, 0 ≤ ai ≤ 109. Баллы начисляются только при прохождении всех тестов группы, группа оценивается в 20 баллов.
В четвертой группе тестов 1 ≤ N ≤ 200 000, |ai| ≤ 109. Каждый тест этой группы оценивается отдельно. Общее число баллов за тесты этой группы равно 40.
В Команде проходит традиционная ежегодная олимпиада по теории магии среди младшекурсников. Завхозу смены Кате Медведевой поручили заняться распределением студентов по аудиториям.
Каждый факультет выставил своих лучших учеников на олимпиаду. От Звездочек участвует G студентов, от Солнышек S студентов, Травинок представляет H студентов и Подсолнухов — R студентов. В распоряжении Медведевой находится M аудиторий. На аудитории наложено особое заклятие расширения, поэтому при необходимости они могут вместить любое количество студентов. При рассадке необходимо учесть, что ученики одного факультета, находящиеся в одной аудитории, могут, воспользовавшись случаем, начать жульничать, обмениваясь идеями по решению задач. Поэтому в любой аудитории количество студентов с одного факультета, попавших в нее, следует свести к минимуму. Назовем рассадку, удовлетворяющую такому требованию, оптимальной.
Помогите посчитать, какое минимальное количество студентов с одного факультета все же придется посадить в одной аудитории даже при оптимальной рассадке.
В первой строке идут четыре целых числа G, S, H и R (1 ≤ G, S, H, R ≤ 1000) — количество учеников, представляющих каждый из факультетов школы.
Во второй строке идет целое число M (1 ≤ M ≤ 1000) — количество классов в распоряжении у завхоза.
Выведите минимальное количество студентов с одного факультета, которое Кате придётся посадить в одну аудиторию даже при оптимальной рассадке.
4 3 4 4
2
2
15 14 13 14
5
3
Лёша сидел на лекции. Ему было невероятно скучно. Голос лектора казался таким далеким и незаметным...
Чтобы окончательно не уснуть, он взял листок и написал на нём свое любимое слово. Чуть ниже он повторил своё любимое слово, без первой буквы. Ещё ниже он снова написал своё любимое слово, но в этот раз без двух первых и последней буквы.
Тут ему пришла в голову мысль — времени до конца лекции все равно ещё очень много, почему бы не продолжить выписывать всеми возможными способами это слово без какой-то части с начала и какой-то части с конца?
После лекции Лёша рассказал Максу, как замечательно он скоротал время. Максу стало интересно посчитать, сколько букв каждого вида встречается у Лёши в листочке. Но к сожалению, сам листочек куда-то запропастился.
Макс хорошо знает любимое слово Лёши, а ещё у него не так много свободного времени, как у его друга, так что помогите ему быстро восстановить, сколько раз Лёше пришлось выписать каждую букву.
На вход подаётся строка, состоящая из строчных латинских букв — любимое слово Лёши.
Длина строки лежит в пределах от 5 до 100 000 символов.
Для каждой буквы на листочке Лёши, выведите её, а затем через двоеточие и пробел сколько раз она встретилась в выписанных Лёшей словах (см. формат вывода в примерах). Буквы должны следовать в алфавитном порядке. Буквы, не встречающиеся на листочке, выводить не нужно.
hello
e: 8
h: 5
l: 17
o: 5
abacaba
a: 44
b: 24
c: 16
Пояснение к первому примеру. Если любимое Лёшино слово — "hello", то на листочке у Лёши будут выписаны следующие слова:
Маленький Петя очень любит компьютеры и хочет научиться программировать.
В небольшом городке Маховники, где он живёт, работает сеть кружков по программированию самой разной тематики. Когда Петя пошёл записываться, он увидел большой список, состоящий из N кружков. Петя хочет быть всесторонне развитой личностью, поэтому он собрался отучиться во всех этих кружках. Но когда он собрался записаться на все занятия сразу, обнаружилось, что не всё так просто. Во-первых, в один момент времени разрешается учиться только в одном из этих N кружков. Во-вторых, некоторые преподаватели выдвигают входные требования к знаниям учеников, заключающиеся в знании курсов каких-то других кружков!
Петя хочет стать великим программистом, поэтому подобные мелочи его не останавливают. Действительно, ему достаточно всего-лишь составить правильный порядок посещения кружков, чтобы удовлетворить всем входным требованиям — это совсем простая задача, доступная даже совсем неопытному программисту.
Перед тем как сесть составлять порядок посещения кружков, Петя внимательно перечитал условия обучения и обнаружил ещё один важный пункт. Оказывается, для привлечения школьников, во всех кружках действует система поощрения учеников конфетами. Это означает, что по окончании очередного кружка ученику выдают несколько коробок конфет, всё больше и больше с каждым пройденным кружком. С другой стороны, в каждом кружке количество конфет в коробке своё, зависящее от сложности курса. Более конкретно — за прохождение i-го по счёту кружка, если этот кружок идёт в общем списке под номером j, ученику выдают аж Ni - 1·j конфет — такие щедрые люди программисты.
Петя решил совместить полезное с приятным — теперь он хочет выбрать такой порядок посещения кружков, чтобы при этом получить как можно больше конфет, однако эта задача ему уже не под силу. Помогите будущему великому человеку отыскать такой порядок.
В первой строке входного файла содержится целое число N (1 ≤ N ≤ 100 000) — количество кружков в Маховниках.
В последующих N строках идут описания входных требований кружков, в порядке их следования в общем списке. В i-ой строке сначала записано целое число ki (0 ≤ ki ≤ N - 1) — количество кружков, в которых нужно отучиться перед записью в i-й кружок, а потом ki номеров этих кружков.
Сумма ki не превосходит 200 000.
Гарантируется, что возможно посетить все эти кружки в некотором порядке, не нарушая условия посещения.
Выведите N номеров, разделённых пробелами — порядок, в котором Пете надо посещать кружки, чтобы съесть как можно больше конфет.
6
1 2
0
1 2
3 1 2 5
1 2
4 1 3 4 5
2 1 3 5 4 6
Пояснение к примеру. Посещая кружки в указанном порядке, Петя получит 60·2 + 61·1 + 62·3 + 63·5 + 64·4 + 65·6 = 2 + 6 + 108 + 1080 + 5184 + 46656 = 53036 конфет.
Кроме Земли, пандорианцы уже много тысячелетий исследуют и другие планеты. Большой интерес для них в прошлом представляла планета Арракис. К сожалению, с началом исследований на Земле финансирование исследований на Арракисе было существенно урезано, и местным агентам-исследователям пришлось искать дополнительные источники дохода.
К счастью, пандорианцы очень хорошо разбираются в финансовых вопросах. Им не составило труда проанализировать политические, экономические и психологические тенденции, а также некоторые другие факторы, не имеющих названий на земных языках и на основе этих данных точно предсказать изменение стоимости воды на Арракисе на ближайший год. Как известно, вода на этой планете является главной ценностью после золота, на которое эту воду можно купить.
Изначально пандорианцы обладают запасом золота в 10 золотых слитков. Они решили в один из дней года купить на все это золото воды, а в какой-то последующий день продать всю купленную воду и получить прибыль за счет разницы стоимости. К примеру, если бы стоимость воды в день покупки составляла 1 литр за 4 золотых слитка, а стоимость воды в день продажи – 1 литр за 6 золотых слитков, то пандорианцы могли бы получить купить \(\frac{10}{4}=2.5\) литра воды, а продать они эту воду смогут за \(2.5 \times 6=15\) золотых слитков. Таким образом, прибыль пандорианцев составила бы \(15-10=5\) золотых слитков. Конечно же, пандорианцы хотят максимизировать свой доход в результате этих махинаций. Помогите им выбрать оптимальные дни для покупки и продажи воды!
В первой строке задано целое число 2 ≤ N ≤ 100 000 — количество дней в году на планете Арракис.
Во второй строке заданы N целых положительных чисел a i ( 1 ≤ i ≤ N , 1 ≤ a i ≤ 5000 ), задающих стоимость воды на Арракисе в день i .
Выведите два целых числа: первое число — номер дня, в который стоит купить воду, второе число — номер дня, в который следует воду продать. Дни нумеруются с единицы. Если оптимальных пар дней для покупки/продажи несколько, то выведите любую из них.
Выведите два нуля, если покупка и продажа воды по указанной схеме не принесет пандорианцам прибыли.
6 10 3 5 3 11 9
2 5
4 5 5 5 5
0 0