Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Ледяная горка#81116

В Простоквашино построили ледяную горку. Она состоит из N ступенек. На каждой ступеньке написано число — сколько секунд нужно отдохнуть, если встать на неё. Дядя Фёдор стартует перед первой ступенькой и может прыгать на 1 или 2 ступеньки вперёд. Ему нужно добраться до вершины (встать на последнюю ступеньку), потратив минимум времени на отдых.

Входные данные: В первой строке число N (1 ≤ N ≤ 10). Во второй строке N целых чисел от 0 до 100 — время отдыха на каждой ступеньке.

Выходные данные: Минимальное суммарное время отдыха.

Динамическое программирование: один параметр

✓ 163✗ 393800средняяВойти и решать

Летокоины#60945

В деревне Летовецк, где живут мудрые старцы и их ученики, существует древний банк, который хранит богатства в виде ле́токоинов — особых монет, обладающих магической силой. Однако банк установил строгие правила: чтобы снять деньги, нужно использовать только определённые суммы за одну операцию:

за одну операцию можно снять только 1 ле́токоин,
за одну операцию можно снять сумму 6^x, где x - любое натуральное число (можно снять сумму равную 6, 36, 216, и т.д.),
за одну операцию можно снять сумму 9^x, где x - любое натуральное число (можно снять сумму равную 9, 81, 729, ...).

Старец Летовец спросил своих учеников: за какое минимальное количество операций вы сможете снять ровно N ле́токоинов?

Примечание: невозможно повторно вносить снятые деньги в банк!

Формат входных данных
На вход подается целое число N (\(1<=N<=100000\)).

Формат выходных данных
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	127	4	При снятии 1 + 9 + 36 + 81 получится снять 127 летокоинов за 4 операции.
2	3	3	1+1+1 = 3, всего 3 операции
3	44852	16

Динамическое программирование: один параметр

✓ 7✗ 1401 100средняяВойти и решать

Разделить конфеты#59889

Старец Летовец, известный своей любовью к математике, решил проверить смекалку своих учеников. Он дал им n конфет и сказал: "Разложите эти конфеты на три кучки так, чтобы в каждой кучке было не больше, чем limit. И определите сколькими различными способами это можно сделать?"

Напишите программу, которая поможет ученикам получить ответ на вопрос Летовца.

Формат входных данных
В первой строке входных данных записано натуральное число n, во второй - натуральное число limit.

Ограничения

1 <= n <= 1000
1 <= limit <= 1000

Формат выходных данных
Выведите одно число - количество способов

Примечание
В первом тестовом примере есть 3 способа разложить 5 конфет таким образом, чтобы в каждой кучке было не больше 2 конфет: (1, 2, 2), (2, 1, 2) и (2, 2, 1).
Во втором тестовом примере существует 10 способов распределить 3 конфеты таким образом, чтобы в каждой кучке было бы не больше 3 конфет: (0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0) и (3, 0, 0).

Динамическое программирование: один параметр Перебор

✓ 5✗ 84900средняяВойти и решать

Операции с числом#50364

Дима работает на складе чисел. Он входит на склад с двоичным числом \(x=0\). Ему необходимо превратить свое число \(x\) в число \(s\). Для этого на складе есть два автомата для увеличения чисел.

Первый автомат увеличивает двоичное число \(x\) на \(1\) за \(a\) секунд. Он расположен слева от входа на склад, в \(p\) секундах ходьбы от входа.

Второй автомат умножает двоичное число \(x\) на \(2\) за \(b\) секунд. Он расположен справа от входа на склад, в \(q\) секундах ходьбы от входа.

Таким образом, если Диме понадобится дойти от одного автомата до другого, он потратит \(p+q\) секунд. Исходно он находится у входа на склад.

Помогите Диме узнать, за какое наименьшее количество секунд можно получить число \(x=s\) и вернуться ко входу на склад.
Число в двоичной системе счисления из \(n\) цифр, представимое в виде: \(\overline{a_1 a_2 \ldots a_n}\) \((a_i \in \{0, 1\})\), равно \(2^{n-1} \cdot a_1 + 2^{n-2} \cdot a_2 + \ldots + 2 \cdot a_{n-1} + a_n\). (\(a_1 = 1\) при \(n > 1\), то есть число не имеет ведущих нулей).

Формат входных данных
В первой строке даны два целых числа \(a\) и \(b\) в десятичной записи \((1 \le a, b \le 10^9)\) — время, которое потребуется автоматам для увеличения числа.

Во второй строке даны целые числа \(p\) и \(q\) в десятичной записи \((0 \le p, q \le 10^9)\) — расстояние от входа на склад до первого и второго автоматов.

В третьей строке дано число \(s\) в двоичной системе счисления без ведущих нулей (кроме случая \(s = 0\)). Длина числа \(s\) не превышает \(100\,000\) цифр.

Формат выходных данных
Выведите минимальное количество секунд, которое потребуется, чтобы из \(x=0\) получить \(x=s\), пользуясь автоматами, и вернуться ко входу на склад.

Примечание

В первом тесте необходимо получить число \(s=32 + 8 + 2 + 1 = 43\) в десятичной записи.

Оптимальная последовательность действий: Дима идет к первому автомату (2 секунды), прибавляет к числу единицу 5 раз (5 секунд), потом идет ко второму автомату (\(2+3=5\) секунд), умножает число 3 раза (\(3 \cdot 2 = 6\) секунд) и получает число 40, возвращается к первому автомату (\(3+2=5\) секунд), прибавляет единицу 3 раза (3 секунды), и идет ко входу на склад (2 секунды). Всего потрачено 28 секунд.

Во втором тесте у Димы с самого начала есть число \(x=0\).

Динамическое программирование: один параметр Системы счисления

✓ 11✗ 771 000средняяВойти и решать

Призы#50361

Миша участвует в процедуре награждения на интеллектуальном шоу. В процессе награждения ему последовательно предлагают призы. У каждого приза есть стоимость. Про каждый приз Миша должен заявить, хочет ли он его взять. После того, как Миша возьмет или пропустит приз, ему показывается следующий, и так далее, вернуться к предыдущим призам и изменить свое решение нельзя.

В качестве первого приза Миша может взять любой приз, а затем Миша может взять приз, если его стоимость строго больше стоимости предыдущего взятого им приза.

Миша подсмотрел сценарий шоу и знает стоимости призов, а также порядок, в котором они будут ему предлагаться. Помогите ему выбрать призы таким образом, чтобы их суммарная стоимость была как можно больше.

Формат входных данных
Первая строка ввода содержит целая число \(n\) — количество призов (\(1 \le n \le 1000\)). Вторая строка содержит \(n\) чисел \(a_1, a_2, \ldots, a_n\) — стоимости призов в том порядке, в котором их покажут Мише (\(1 \le a_i \le 10^9\)).

Формат выходных данных
Выведите одно число — максимальную суммарную стоимость призов, которые может получить Миша.

Динамическое программирование: один параметр

✓ 9✗ 461 100средняяВойти и решать

Разбиение на тройки#48972

На день рождения Маше как обычно подарили массив \(a\) из \(n\) натуральных чисел, в котором каждое число находится в пределах от \(1\) до \(m\) включительно. Маша очень любит число три, поэтому длина массива делится на три.

Маша решила объединять числа в тройки: каждая тройка чисел должна состоять или из трех одинаковых чисел, или из трех последовательных чисел. Другими словами, каждая тройка имеет или вид \((x, x, x)\), или \((x, x+1, x+2)\), где \(x\) — какое-то натуральное число.

Маша хочет поиграть с подаренным массивом, и ее интересует количество способов разбить числа этого массива на такие тройки. Два способа разбиения считаются различными, если нельзя установить взаимно-однозначное соответствие между тройками первого разбиения и тройками второго разбиения, что числа внутри соответствующих троек равны. Так как количество разбиений может быть большим, Маше достаточно знать его остаток по модулю \(10^9+7\).

Помогите Маше посчитать количество способов разбить числа подаренного ей массива на тройки по модулю \(10^9+7\).

Формат входных данных
Первая строка входных данных содержит два целых числа \(n\) и \(m\) (\(1 \le n \le 5000\), \(1 \le m \le 5000\), \(n=3\cdot k\) для какого-то натурального \(k\)).

Вторая строка содержит \(n\) целых чисел \(a_i\) — числа массива (\(1 \le a_i \le m\)).

Формат выходных данных
В единственной строке одно число — количество способов разбить числа массива на тройки по модулю \(10^9+7\).

В первом примере числа можно разбить на тройки двумя способами: {\((2, 2, 2)\), \((3, 3, 3)\), \((4, 4, 4)\)} и {\((2, 3, 4)\), \((2, 3, 4)\), \((2, 3, 4)\)}.

Динамическое программирование: один параметр

✓ 2✗ 21 100средняяВойти и решать

Ферзь в угол#48821

В левом верхнем углу доски размером NxM находится ферзь, который может двигаться только вправо-вниз. Игроки по очереди двигают ферзя, то есть за один ход игрок может переместить ферзя либо по вертикали вниз, либо по горизонтали вправо, либо во диагонали вправо-вниз. Игрок, который не сможет сделать хода - проигрывает, иными словами, выигрывает игрок, который поставит ферзя в правый нижний угол. Необходимо определить, какой из игроков может выиграть в этой игре независимо от ходов другого игрока.

Формат входных данных

Программа получает на вход два натуральных числа N и M, записанных в одной строке через пробел. Числа не превосходят 100.

Формат выходных данных

Программа должна вывести номер игрока (1 или 2), у которого есть выигрышная стратегия.

Динамическое программирование: один параметр Простые игры

✓ 24✗ 169900средняяВойти и решать

Эксперименты Шелдона#47569

Юному Шелдону очень интересно проводить эксперименты, результатом которых являются различные последовательности чисел. После проведения очередных экспериментов, Шелдон получил определенную последовательность чисел и заинтересовался вопросом, сможет ли он из исходной последовательности вычеркнуть некоторые числа таким образом, чтобы оставшиеся числа образовывали возрастающую подпоследовательность, где каждый элемент строго больше предыдущего. Шелдон хочет вычеркнуть как можно меньше чисел (в том числе, если можно, то ничего не вычеркивать).
Теперь он хочет узнать, сколько существует различных вариантов выбрать одну такую подпоследовательность из данной последовательности чисел. Помогите юному Шелдону найти ответ для заданной последовательности чисел.

Входные данные
Первая строка содержит натуральное число n - длина последовательности Шелдона. Вторая строка содержит n чисел - элементы последовательности (nums_i).

Ограничения

1 <= n <= 2000
-10⁶ <= nums_i <= 10⁶

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	5 1 3 5 4 7	2
2	5 2 2 2 2 2	5

Динамическое программирование: один параметр

✓ 129✗ 366800средняяВойти и решать

Магическая сила#46700

Вы - маг, странствующий по волшебному лесу, в поисках своей утраченной магической силы. Эта магическая сила находится в волшебных кристаллах, которые растут на деревьях в этом волшебном лесу. На каждом дереве растет только один волшебный кристалл. Так как вы маг, то вы знаете какой силой обладает тот или иной кристалл, растущий на определенном дереве в этом лесу. Вы хотите получить в этом лесу как можно больше магической силы. Для этого вам следует выполнить следующее действие любое количество раз:

Выберите любое дерево и соберите волшебный кристалл, который растет на нем, чтобы получить его магическую силу. Помните, что после того как был сорван кристалл с определенной силой, все кристаллы, чья сила на один меньше или на один больше, чем сила кристалла, который вы только что собрали, сами исчезают, оставляя вас с магической силой, равной силе собранного кристалла.

Определите максимальную магическую силу, которую вы можете получить, применяя вышеуказанное действие любое количество раз.

Входные данные
Первая строка входных данных содержит число n - количество деревьев в волшебном лесу. Вторая строка содержит n чисел a_i - волшебная сила кристалла на i-м дереве.

Ограничения на входные данные

1 <= n <= 2 * 10⁴
1 <= a[i] <= 10⁴
1 <= i <= n

Выходные данные
Выведите максимальную магическую силу, которую вы можете получить.

Примеры

№	Входные данные	Выходные данные
1	3 3 4 2	6
2	6 2 2 3 3 3 4	9

Динамическое программирование: один параметр

✓ 10✗ 681 100средняяВойти и решать

Магическая энергия#46699

Вы - маг, который хочет собирать магическую энергию из домов вдоль улицы. В каждом доме сосредоточена определенная магическая энергия, и единственным ограничением является то, что если вы извлекаете магическую энергию из двух соседних домов в одну и ту же ночь, то это вызывает негативные последствия для вас и окружающей среды.

Зная уровень магической энергии в каждом доме, найдите максимальное количество магической энергии, которое вы можете собрать сегодня, избегая извлечения энергии из соседних домов в одну и ту же ночь. Кроме этого, определите заранее какие дома вы должны посетить?

Входные данные
В первой строке записано число n - количество домой вдоль улицы. Во второй строке - n целых чисел a_i - количество магической энергии в i-м доме.

Ограничения на входные данные

1 <= n <= 100
0 <= a[i] <= 400
1 <= i <= n

Выходные данные
Выведите в первой строке максимальное количество магической энергии, которую вы сможете собрать. Во второй строке выведите номера домов (в порядке возрастания, через пробел), которые вы посетите.

Примеры

№	Входные данные	Выходные данные
1	4 3 2 2 1	5 1 3
2	5 2 7 9 3 1	12 1 3 5

Динамическое программирование: один параметр

✓ 29✗ 127900средняяВойти и решать

Ладья Громозеки#39391

Любимая шахматная фигура Громозеки - это ладья. Но он любит ходить ей только по вертикали, причем либо на одну клетку, либо на две. Громозека заканчивает игру, когда ладья доходит до конца вертикали. Подумав над очередной позицией, он заметил, что некоторые клетки на пути ладьи находятся под ударом фигур соперника и ходить на эти клетки нельзя.
Помогите Громозеке посчитать сколькими способами он может перевести ладью c 1 горизонтали на другой конец шахматного поля, не попадая на клетки под ударом.

Входные данные
В первой строке вводится одно натуральное число N (N <= 40): размер шахматного поля. Во второй строке вводится одно натуральное число K (K <= N): количество клеток, находящихся под ударом. В третьей строке вводятся K различных натуральных чисел в диапазоне от 1 до N: номера клеток, находящихся под ударом фигур соперника.

Выходные данные
Выведите одно число - количество способов попасть на конец вертикали (на N-ю клетку).

Примеры

№	Входные данные	Выходные данные
1	7 2 3 5	1
2	10 3 5 1 2	0
3	3 1 2	1

Динамическое программирование: один параметр

✓ 29✗ 81800средняяВойти и решать

Крокрыс банк#38593

Чтобы затруднить снятие денег, банк на планете Крокрыс разрешает своим клиентам снимать только одну из следующих сумм за одну операцию:
- 1 крокрыскоин (действующая монета на планете Крокрыс);
- 6 крокрыскоинов, 36 (=6²) крокрыскоинов, 216(=6³) крокрыскоинов , ...;
- 9 крокрыскоинов, 81 (=9²) крокрыскоинов, 729(=9³) крокрыскоинов , ...
Сколько минимум операций требуется, чтобы вывести ровно N крокрыскоинов?
Невозможно повторно внести снятые вами деньги.

Входные данные
На вход подается целое число N (\(1<=N<=100000\)).

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	127	4	При снятии 1 + 9 + 36 + 81 получится снять 127 крокрыскоина за 4 операции.
2	3	3	1+1+1 = 3, всего 3 операции
3	44852	16

Динамическое программирование: один параметр

✓ 34✗ 78800средняяВойти и решать

Практический тест#38589

У нас есть сетка с H строками и W столбцами. Квадрат в i-й строке и j-м столбце будет называться Square(i, j). Целые числа от 1 до H·W записаны по всей сетке, а целое число, записанное в Square(i, j), равно A_i,j.
Вы - волшебник (волшебница), и можете телепортировать фигуру, помещенную на Square(i, j) в Square(x, y), потратив \(|x-i|+|y-j|\) маджиков (магических монет).
Теперь вам нужно пройти Q практических тестов на свои способности как волшебника (волшебницы). I-е испытание будет проводиться следующим образом:
- первоначально фигура располагается в квадрате, где записано целое число L_i;
- пусть x будет целым числом, записанным в квадрате, занятом фигурой. Неоднократно переместите фигуру в квадрат, где написано целое число x+D, пока x не станет равен R_i. Тест заканчивается, когда x = R_i .
Гарантируется, что R_i- L_i делится на D.
Для каждого теста найдите сумму маджиков, израсходованных во время этого теста.

Входные данные
В первой строке заданы три целых числа: H, W и D (\(1\leq H,W \leq 300\), \(1 \leq D \leq H \cdot W\)).
В следующих H строках записано по W чисел A_i,j(\(1 \leq A_{i,j} \leq H \cdot W\), \(A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))\).
В следующей строке записано целое число Q (\(1 \leq Q \leq 10^5\)).
В последних Q строках записано по 2 целых числа: L_i и R_i (\(1 \leq L_i \leq R_i \leq H \cdot W\)), \((R_i-L_i)\) кратно D.

Выходные данные
Для каждого теста выведите сумму маджиков, израсходованных во время этого теста. Вывод должен быть в порядке проведения тестов.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 3 2 1 4 3 2 5 7 8 9 6 1 4 8	5	- 4 записано Square (1,2). - 6 записано в Square (3,3). - 8 записано in Square (3,1). Таким образом, сумма магических очков, израсходованных во время одного теста, составляет: \((\|3-1\|+\|3-2\|)+(\|3-3\|+\|1-3\|)=5\).
2	4 2 3 3 7 1 4 5 2 6 8 2 2 2 2 2	0 0	Обратите внимание, что может быть тест, в котором фигура вообще не перемещается, и может быть несколько идентичных тестов.
3	5 5 4 13 25 7 15 17 16 22 20 2 9 14 11 12 1 19 10 6 23 8 18 3 21 5 24 4 3 13 13 2 10 13 13	0 5 0

Динамическое программирование: один параметр Массивы Префиксные суммы(минимумы, ...)

✓ 5✗ 151 100средняяВойти и решать

Количество треугольников#38574

Рассмотрим фигуру, аналогичную показанной на рисунке (большой равносторонний треугольник, составленный из маленьких равносторонних треугольников). На рисунке приведена фигура, состоящая из 4-х уровней треугольников.

Напишите программу, которая будет определять, сколько всего в ней треугольников (необходимо учитывать не только "маленькие" треугольники, а вообще все треугольники — в частности, треугольник, выделенный жирным, а также вся фигура, являются интересующими нас треугольниками).

Входные данные
Вводится одно число N — количество уровней в фигуре (1 ≤ N ≤ 100000).

Выходные данные
Выведите количество треугольников в такой фигуре.

Примеры

№	Входные данные	Выходные данные
1	1	1
2	2	5
3	4	27

Динамическое программирование: один параметр

✓ 52✗ 101800средняяВойти и решать

Поход#38552

Группа школьников решила сходить в поход вдоль Москвы-реки. У Москвы-реки существует множество притоков, которые могут впадать в нее как с правого, так и с левого берега.

Школьники хотят начать поход в некоторой точке на левом берегу и закончить поход в некоторой точке на правом берегу, возможно, переправляясь через реки несколько раз. Как известно, переправа как через реку, так и через приток представляет собой определенную сложность, поэтому они хотят минимизировать число совершенных переправ.

Школьники заранее изучили карту и записали, в какой последовательности в Москву-реку впадают притоки на всем их маршруте.

Помогите школьникам по данному описанию притоков определить минимальное количество переправ, которое им придется совершить во время похода.

Входные данные
Единственная строка содержит описание Москвы-реки между начальной и конечной точкой похода. Длина строки не превосходит 10⁵ символов.

Каждый символ строки может быть одной из трех латинских букв L, R или B. Буква L означает, что очередной приток впадает в реку с левого берега, R - приток впадает в реку с правого берега и B - притоки впадают с обоих берегов реки в одном месте. Поход начинается на левом берегу перед описанной частью реки и заканчивается на правом берегу после описанной части.

Выходные данные
Выведите одно целое число - минимальное количество переправ.

Примечания
Рисунок к приведенному ниже примеру.

Примеры

№	Входные данные	Выходные данные
1	LLBLRRBRL	5

Динамическое программирование: один параметр

✓ 45✗ 89900средняяВойти и решать

Валютные махинации#38357

Петя, изучая, как меняется курс рубля по отношению к доллару и евро, вывел закон, по которому происходят эти изменения (или думает, что вывел). По этому закону Петя рассчитал, каков будет курс рубля по отношению к доллару и евро в ближайшие N дней.

У Пети есть 100 рублей. В каждый из дней он может обменивать валюты друг на друга по текущему курсу без ограничения количества (при этом курс доллара по отношению к евро соответствует величине, которую можно получить, обменяв доллар на рубли, а потом эти рубли — на евро). Поскольку Петя будет оперировать не с наличной валютой, а со счетом в банке, то он может совершать операции обмена с любым (в том числе и нецелым) количеством единиц любой валюты.

Напишите программу, которая вычисляет, какое наибольшее количество рублей сможет получить Петя к исходу N-го дня.

Законы изменения курсов устроены так, что в течение указанного периода рублевый эквивалент той суммы, которая может оказаться у Пети, не превысит 10⁸ рублей.

Входные данные
Первая строка входного файла содержит одно число N (1≤N≤5000). В каждой из следующих N строк записано по 2 числа, вычисленных по Петиным законам для соответствующего дня — сколько рублей будет стоить 1 доллар, и сколько рублей будет стоить 1 евро. Все эти значения не меньше 0.01 и не больше 10000. Значения заданы точно и выражаются вещественными числами не более, чем с двумя знаками после десятичной точки.

Выходные данные
В выходной файл выведите искомую величину с точностью не менее двух знаков после десятичной точки.

Примеры

№	Входные данные	Выходные данные
1	1 30.00 9999.99	100.00

Динамическое программирование: один параметр

✓ 15✗ 431 100средняяВойти и решать

Распечатка условий#38332

Популярность окружной олимпиады по информатике растет год от года. При этом организаторы должны заранее распечатать как условия задач, так и другие материалы олимпиады (анкеты, памятки и т.п). В этом году они оценили объем печатной продукции в N листов.

Фирма, готовая размножить печатные материалы, предлагает следующие финансовые условия. Один лист она печатает за A1 рублей, 10 листов — за A2 рублей, 100 листов — за A3 рублей, 1000 листов — за A4 рублей, 10 000 листов — за A5 рублей, 100 000 листов — за A6 рублей и 1 000 000 листов — за A7 рублей. При этом не гарантируется, что один лист в более крупном заказе обойдется дешевле, чем в более мелком. И даже может оказаться, что для любой партии будет выгодно воспользоваться тарифом для одного листа.

Печать конкретного заказа производится или путем комбинации нескольких тарифов, или путем заказа более крупной партии. Например, 980 листов можно распечатать, заказав печать 9 партий по 100 листов плюс 8 партий по 10 листов, сделав 98 заказов по 10 листов, 980 заказов по 1 листу или заказав печать 1000 (или даже 10 000 и более) листов, если это окажется выгоднее.

Требуется по заданному объему заказа в листах N определить минимальную сумму денег в рублях, которой будет достаточно для выполнения заказа.

Входные данные
На вход программе сначала подается число N (1 ≤ N ≤ 2 × 109) — количество листов в заказе. В следующих 7 строках ввода находятся натуральные числа A1, A2, A3, A4, A5, A6, A7 соответственно (1 ≤ Ai ≤ 106).

Выходные данные
Выведите одно число — минимальную сумму денег в рублях, которая нужна для выполнения заказа. Гарантируется, что правильный ответ не будет превышать 2 × 10⁹.

Примеры

№	Входные данные	Выходные данные
1	980 1 9 90 900 1000 10000 10000	882
2	980 1 10 100 1000 900 10000 10000	900

Динамическое программирование: один параметр

✓ 21✗ 11900средняяВойти и решать

Самая опасная акула#38304

Как известно, не только люди любят принимать участие в различных соревнованиях. Среди рыб и моллюсков также проводится множество состязаний на дне океана. Акула Семён участвует в самом престижном соревновании Мирового океана на звание самой опасной акулы. Во время этого состязания акулы соревнуются в различных дисциплинах: плавание на скорость, маскировка, навигация по картам и многим другим. Сейчас Семён проходит испытание под названием «разрушение».

Во время этого испытания перед акулой ставят m доминошек. Все доминошки стоят на одной прямой, однако высоты доминошек могут различаться. Расстояние между соседними доминошками равно 1. Кроме того, у каждой доминошки есть своя стоимость, выраженная целым числом. Цель акулы — уронить все доминошки. Для этого акула может толкнуть любую доминошку влево или вправо, после чего она начнёт падать в этом направлении. Если во время падения доминошка задевает другие, они также начинают падать в ту же сторону, в которую падала исходная, таким образом начинается цепная реакция, в результате которой может упасть множество доминошек. Падающая доминошка задевает другую, если и только если расстояние между ними строго меньше высоты падающей доминошки, причем доминошки не обязательно должны быть соседними.

Разумеется, любая акула справится с тем, чтобы уронить все доминошки таким образом, поэтому оценивается не факт разрушения, а его стоимость. Стоимостью разрушения называется сумма стоимостей доминошек, которые акуле придётся толкнуть, чтобы все доминошки упали.

Семён уже победил в прошлых испытаниях, однако недостаточно умён, чтобы победить в этом. Помогите Семёну и определите, какая минимальная суммарная стоимость доминошек, которые ему придётся толкнуть, чтобы все доминошки упали.

Входные данные
Для уменьшения размера ввода высоты и стоимости доминошек задаются при помощи блоков.

В первой строке заданы два целых числа n и m (1 ≤ n≤ 250 000, 1 ≤ m ≤ 10⁷ ) — количество блоков и суммарное количество доминошек, которые надо уронить Семёну, соответственно.

Затем следует описание n блоков. Описание каждого блока состоит из трёх строк.

В первой строке описания блока с номером i содержится целое число k_i (1 ≤ k_i ≤ 250000, \(\sum_{i=1}^n {k_i ? 250 000}\) ) — количество доминошек в блоке.

Во второй строке описания блока с номером i содержатся ki целых чисел a_i,j (1 ≤ a_i,j ≤ m) — высоты доминошек в блоке.

В третьей строке описания блока с номером i содержатся ki целых чисел c_i,j (1 ≤ c_i,j ≤ 100000) — стоимости доминошек в блоке.

Далее следует описание последовательности доминошек, которые надо уронить Семёну, в порядке слева направо.

В первой строке описания последовательности задано целое число q (n ≤ q ≤ 250000) — количество блоков в последовательности доминошек, которые надо уронить.

В следующих q строках содержатся пары целых чисел id_i mul_i (1 ≤ id_i ≤ n, 1 ≤ mul_i ≤ 100000), обозначающие, что очередные k_idi в порядке слева направо доминошек — это доминошки блока id_i, чьи стоимости были умножены на число mul_i.

Гарантируется, что \(\sum_{i=1} ^q k_{id_i} = m\) , а также, что каждый блок встречается хотя бы один раз в последовательности доминошек, которые требуется уронить, то есть для всех i от 1 до n найдется j такое, что id_j=i.

Выходные данные
Выведите одно целое число — минимальную суммарную стоимость доминошек, которые надо толкнуть, чтобы все доминошки упали.

Примечание
В первом примере перед Семёном стоят 7 доминошек. Их высоты равны [3122122] , а стоимости равны [4363121] . Сначала Семёну следует уронить доминошку с номером 7 влево, она упадёт и заденет доминошку с номером 6. Доминошка 6, падая, заденет доминошку с номером 5, которая упадёт, но не заденет другие доминошки. Затем Семён должен уронить доминошку с номером 1 вправо, она, падая, заденет доминошки с номерами 2 и 3, а доминошка 3, падая, заденет доминошку 4, таким образом все доминошки упадут.

Во втором примере перед Семёном стоит одна доминошка стоимостью 10000000000.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	2 7 3 1 2 2 1 2 1 1 3 2 3 2 2 1 3 1 1	5	Перед Семёном стоят 7 доминошек. Их высоты равны [3122122] , а стоимости равны [4363121] . Сначала Семёну следует уронить доминошку с номером 7 влево, она упадёт и заденет доминошку с номером 6. Доминошка 6, падая, заденет доминошку с номером 5, которая упадёт, но не заденет другие доминошки. Затем Семён должен уронить доминошку с номером 1 вправо, она, падая, заденет доминошки с номерами 2 и 3, а доминошка 3, падая, заденет доминошку 4, таким образом все доминошки упадут.
2	1 1 1 1 100000 1 1 100000	10000000000	Перед Семёном стоит одна доминошка стоимостью 10000000000

Динамическое программирование: один параметр реализация

✓ 2✗ 11 000средняяВойти и решать

Словарь#38196

У Васи на клавиатуре не работает клавиша пробел. Поэтому все тексты он теперь набирает слитно. Напишите программу, которая будет разделять набранный Васей текст на слова из данного словаря.

Входные данные
Сначала на вход программы поступает текст, введенный Васей – одна строка из не более чем 100 латинских строчных букв. В следующей строке входных данных задается значение N – количество слов в словаре (N – натуральное число, не превосходящее 2000). В следующих N строках записаны слова из словаря – по одному слову в строке, каждое слово содержит не более 20 латинских строчных букв. Слова записаны в алфавитном порядке.

Выходные данные
Выведите Васин текст с пробелами между словами (пробел после последнего слова допустим). Если возможно несколько вариантов разбиения строки на слова, выведите любой их них. Гарантируется, что хотя бы один способ разбиения строки на словарные слова существует.

Примеры

№	Входные данные	Выходные данные
1	whatcanido 6 a an can do i what	what can i do

Бинарный поиск в массиве Динамическое программирование: один параметр

✓ 7✗ 17800средняяВойти и решать

Сумма чисел в массиве#33724

Дан массив произвольных целых чисел. Напишите программу, которая за один проход по массиву находит непрерывный кусок, сумма чисел в котором максимальна.
Примечание. Фактически требуется найти такие i и j (i<=j), что сумма всех элементов массива от a_i до a_j включительно будет максимальна. Индексация элементов начинается с 1.

Входные данные
В первой строке задается натуральное число n <= 100000 — количество элементов в массиве. В следующих n строках задаются сами элементы массива — целые числа, по модулю не превосходящие 30 000.

Выходные данные
Выведите пару искомых значений индексов. Если таких пар несколько, то j должно быть минимально возможным, а при равных j значение i должно быть максимально возможным. В первой строке выведите i, во второй - j.

Примеры

№	Входные данные	Выходные данные
1	5 -1 2 3 -2 2	2 3
2	7 2 -2 3 -1 5 -2 7	3 7

Алгоритмы обработки Динамическое программирование: один параметр

✓ 765✗ 4 064800средняяВойти и решать