Слава практически дописал условие последней задачи для ICPC Kyrgyzstan Qualification Round — ещё немного, и задача будет готова!
Причем Слава умудрился написать условие без пробелов, знаков табуляции и переводов строк (он и сам не понял, как у него это получилось).
Вне себя от радости, Слава пошел заварить себе вкусный чай.
Именно в этот момент Анатолий подкрался к ноутбуку Славы и начал в случайных местах нажимать клавишу Enter.
Когда Слава вернулся, всё было уже потеряно — вместо цельного условия он видел лишь отдельные куски, разделенные переносами строк.
Помогите Славе оценить ущерб — вычислите, сколько раз Анатолий успел нажать клавишу Enter.
Например, Слава написал условие $$$abracadabra$$$
Но пришел Анатолий и нажал $$$4$$$ раза клавишу Enter:
Первая строка входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 100$$$) — количество частей, на которые развалилось исходное условие задачи.
Каждая из следующих $$$n$$$ строк содержит строку $$$s_i$$$ ($$$1 \le |s_i| \le 10$$$) — $$$i$$$-ю часть исходного условия.
Каждая часть состоит только из строчных латинских букв.
Гарантируется, что части даны в том же порядке, в котором они шли в исходном условии.
Выведите единственное целое число — минимальное количество нажатий клавиши Enter, с помощью которых Анатолий мог превратить исходное условие в представленные $$$n$$$ частей.
5abracadabra
4
Вы нашли очень интересный муравейник. Вы настолько им заинтересовались, что решили выяснить, сколько муравьёв в нём находилось в начальный момент (когда вы нашли его).
Для этого вы в течение дня проводили наблюдения и записали массив ai — сколько муравьёв вошло или вышло в i-й момент времени:
Используя свои наблюдения, определите минимальное количество муравьёв, которое могло находиться внутри муравейника до начала наблюдений.
Обратите внимание, что в муравейнике ни в какой момент времени не могло находиться отрицательное количество муравьёв.
В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество совершённых наблюдений.
Во второй строке содержится n целых чисел a1, a2, ..., an ( - 106 ≤ ai ≤ 106, i = 1, 2, ..., n) — результат i-го наблюдения.
В единственной строке выведите целое число — минимально возможное количество муравьёв внутри муравейника до начала наблюдений.
3
20 -50 30
30
Первый тестовый пример
Количество муравьёв внутри муравейника в процессе наблюдений менялось следующим образом:
Есть лабиринт, состоящий из n комнат. Из i-й комнаты можно перейти в комнату i + 1 (но не наоборот).
Вход в лабиринт находится в комнате 1, переход из n-й комнаты ведёт на выход.
Но в чём же смысл лабиринта, если его можно пройти напрямую?
Поэтому создатели лабиринта придумали комнаты-развилки — если посетить такую комнату в 1-й, 3-й, 5-й и т.д. раз (то есть в каждое нечетное посещение) — то переход из неё будет вести в комнату 1 вместо следующей по номеру комнаты (или выхода).
Известно, что комнаты r1, r2, ..., rk являются развилками.
Выведите суммарное количество комнат, которое необходимо посетить, чтобы выйти из лабиринта.
В первой строке содержатся целые числа n и k (1 ≤ n ≤ 30, 0 ≤ k ≤ n) — общее количество комнат в лабиринте и количество комнат-развилок, соответственно.
В следующей строке содержится k целых чисел r1, r2, ..., rk (1 ≤ r1 < r2 < ... < rk ≤ n) — номера комнат-развилок.
В единственной строке выведите целое число — суммарное количество комнат, которые необходимо посетить, чтобы выйти из лабиринта.
5 2
2 4
13
Первый тестовый пример
Последовательность посещённых комнат будет следующей:
(1, 2, 1, 2, 3, 4, 1, 2, 1, 2, 3, 4, 5), после чего следует выход.
Всего посещено 13 комнат.
Набор чисел называется хорошим, если
Набор может содержать одинаковые значения — например, размер набора (2, 7, 3, 7) равен 4, а разница между минимальным и максимальным числом равна 7 - 2 = 5.
Дан массив целых чисел a. Разбейте его элементы на минимальное количество хороших наборов.
В первой строке содержатся целые числа n, M, k (1 ≤ n, k ≤ 105, 0 ≤ M ≤ 109) — количество элементов массива, максимальная разница между числами набора и максимальный размер набора соответственно.
Во второй строке содержится n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109) — элементы массива.
В единственной строке выведите минимально возможное количество хороших наборов, на которые можно разбить данный массив.
4 3 3
5 8 13 21
3
10 5 3
1 6 4 15 4 10 8 2 12 5
4
Второй тестовый пример
Массив можно разбить, например, на следующие наборы:
Вы смотрите в окно и видите n гор, высота i-й горы равна hi.
Вы считаете, что две соседние горы i и (i + 1) входят в одну горную цепь, если |hi - hi + 1| ≤ k, где k — параметр схожести.
Определите минимально возможный параметр схожести k, чтобы все горы разбились на ровно m горных цепей.
В первой строке содержатся целые числа n и m (1 ≤ m ≤ n ≤ 2·105) — количество гор и необходимое количество горных цепей соответственно.
Во второй строке содержится n целых чисел h1, h2, ..., hn (1 ≤ hj ≤ 106, j = 1, 2, ..., n) — высота j-й горы.
В единственной строке выведите единственное целое положительное число k — параметр схожести, при котором все горы разбиваются на ровно m горных цепей.
Если существует несколько возможных значений k, выведите минимальное значение.
Если решения не существует, выведите в качестве ответа - 1.
11 3
2 3 1 5 2 1 4 8 7 9 6
3
5 3
3 1 5 7 6
-1
Первый тестовый пример
При k = 3 получаются следующие m = 3 горные цепи:
При k = 2 будет уже 6 горных цепей.
Второй тестовый пример
При k = 2 получаются следующие 2 горные цепи:
При k = 1 получаются 4 горные цепи.
Видно, что не существует k, при котором получаются ровно m = 3 горные цепи.
Начался новый учебный год, а значит опять придется ехать в автобусе по пробкам в университет.
Вы знаете, что между начальной и конечной остановками расположено n перекрестков со светофорами.
Сама начальная остановка находится сразу после перекрёстка 0, а конечная — сразу за перекрестком n.
Вы знаете, что от (i - 1)-го до i-го перекрестка автобус доезжает за ai секунд. Временем на остановках можно пренебречь.
Про светофор на i-м перекрестке известны три характеристики:
Если автобус подъезжает ровно в тот момент, когда свет как раз переключается на красный свет — автобус уже не проедет.
Используя всю эту информацию, определите — сколько секунд займет вся поездка на автобусе от начала до конца.
В первой строке содержится целое число n (1 ≤ n ≤ 104) — количество перекрёстков у вас на пути.
Во второй строке содержатся целые числа a1, a2, ..., an (1 ≤ ai ≤ 104, i = 1, 2, ..., n) — время, за которое автобус проезжает путь от (i - 1)-го до i-го перекрёстка.
В каждой из следующих n строк содержится по три целых числа ri, gi, di (1 ≤ ri, gi ≤ 1000, 1 ≤ di ≤ 104) — характеристики i-го светофора.
В единственной строке выведите целое число — время, за которое вы доедете на автобусе от начальной остановки до конечной.
3
100 110 50
80 20 50
60 10 100
30 40 50
370
Первый тестовый пример
Начался новый семестр — а значит и ваши тренировки в киберспортивной сборной по Doka 3.
Сегодня вы впервые играете на герое по имени Мидас. Опытные сокомандники рассказали, что сила данного героя напрямую зависит от количества накопленного им золота.
Чтобы получать золото, вы должны побеждать монстров.
На карте мира расположено n монстров, с которыми вы можете сражаться в любом порядке. С каждым монстром можно сразиться только один раз.
Для i-го монстра известны две характеристики:
Изначально у вас 0 золота. Ваша цель на игру — накопить не менее w золота.
Найдите минимальное количество монстров, которых вам необходимо победить для достижения цели, а также номера монстров в порядке сражений с ними.
В первой строке содержится целое число w (1 ≤ w ≤ 109) — количество золота, являющееся вашей целью на игру.
Во второй строке содержится целое число n (1 ≤ n ≤ 105) — количество монстров, с которыми вы можете сразиться.
В каждой из следующих n строк содержится по два целых числа gi и bi (1 ≤ gi ≤ 109, 0 ≤ bi ≤ 109) — характеристики i-го монстра из условия задачи.
В первой строке выведите целое число k — минимальное количество сражений с монстрами, необходимое для достижения цели в w золота. Если вы никак не можете достичь цели — выведите - 1.
В случае успеха во второй строке выведите k чисел — номера монстров в том порядке, в котором вы должны сражаться с ними.
Считайте, что монстры занумерованы в порядке их упоминания во входных данных.
Если существует несколько вариантов ответа, приводящих к минимальному количеству сражений — выведите любой.
28
8
5 2
7 25
4 0
6 1
2 20
3 3
8 7
4 15
6
3 4 1 6 7 8
5
1
5 1
-1
Первый тестовый пример
Опишем последовательность сражений и заработанного золота.
Обратите внимание, что существуют и другие порядки / выборы монстров для сражений.
Второй тестовый пример
У вас 0 золота в начале, а единственный доступный монстр требует 1 золота для победы.
Вы не можете набрать w = 5 золота, значит необходимо вывести - 1.
Вы устроились в крупную корпорацию.
Корпорация разделена на несколько компаний, каждая компания управляется генеральным директором.
Все сотрудники корпорации, кроме генеральных директоров, имеют ровно одного непосредственного начальника.
Вам дан массив b — номера непосредственных начальников для каждого сотрудника компании.
Выведите номер генерального директора, в компании которого наибольшее число сотрудников, а также само это количество.
В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество людей в компании.
Во второй строке содержится n целых чисел bi (0 ≤ bi ≤ n), где bi — номер непосредственного начальника i-го сотрудника. Если bi = 0, то i-й сотрудник — генеральный директор.
Гарантируется, что описанная иерархия корректна — если сотрудник bi является непосредственным начальником сотрудника i, то сотрудник i ни прямо, ни косвенно не является начальником сотрудника bi.
В первой строке выведите два целых числа — номер генерального директора с наибольшим числом сотрудников в компании, а также само это количество.
Если существует несколько вариантов ответа с наибольшим количеством сотрудников — выведите любой.
15
6 0 0 15 13 2 15 14 13 3 12 0 12 2 11
12 8
Первый тестовый пример
Сегодня вам предстоит прослушать n лекций, на i-й лекции вы можете получить ai знаний.
Чтобы увеличить эффект от учебы, перед лекцией вы можете помедитировать — в таком случае за эту лекцию вы получите удвоенное количество знаний.
К сожалению, вы не можете медитировать перед двумя лекциями подряд — эффект сильно ослабнет.
Вычислите наибольшее количество знаний, которое вы можете получить за все лекции, медитируя в оптимальные моменты времени.
В первой строке содержится целое число n 
— количество лекций.
Во второй строке содержится n целых чисел a1, a2, ..., an 
— количество знаний, которое вы получите по умолчанию за j-ю лекцию.
В первой строке выведите целое число k — максимально возможное суммарное количество знаний, которое вы можете получить за день.
Во второй строке выведите n символов s1s2... sn, где символ sj = M, если вы медитировали перед j-й лекцией, и sj = O, если вы слушали лекцию без медитации.
Символы M и O — заглавные латинские буквы.
Если существует несколько вариантов ответа с оптимальным количеством знаний, выведите любой.
6
1 8 1 1 5 2
31
OMOOMO
7
2 4 2 3 5 4 5
39
MOMOMOM
Первый тестовый пример
Вы решили помедитировать перед 2-й и 5-й лекциями — суммарно получили 1 + 8·2 + 1 + 1 + 5·2 + 2 = 31.
Второй тестовый пример
В данном случае вы медитировали перед каждой нечетной лекцией — суммарно получилось 2·2 + 4 + 2·2 + 3 + 5·2 + 4 + 5·2 = 39.
Обратите внимание, что вы не могли, например, медитировать и перед 5-й, и перед 6-й лекциями.