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

Разбиения на сумму нечетных#26985

Напишите программу, которая по данному натуральному числу n будет находить число способов представить его в виде суммы нечетных слагаемых. При этом два разбиения числа, отличающиеся только порядком слагаемых, считаются одинаковыми.

Например, число 6 можно разложить на слагаемые следующими способами: 1+1+1+1+1+1, 1+1+1+3, 3+3, 1+5.

Формат ввода

На вход подается число n (1 n 1000).

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

Выведите одно число — ответ на задачу.

Пример

Ввод	Вывод
6	4

Примечания

Разбиение, состоящее из одного слагаемого, также считается разбиением.

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

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

Пути в музее#26978

Болик добрался до музея, здание которого представляет собой квадрат N × N, разбитый на N² равных квадратных залов. Вход в музей расположен в левом нижнем зале, а Лёлик ждет Болика в правом верхнем. Из каждого зала можно пройти в соседний с ним зал (два зала называются соседними, если у них есть общая стена).

Теперь Болик хочет определить сколько возможных путей до Лёлика у него есть. Конечно, его интересуют только пути кратчайшей длины.

Формат ввода

На вход подается одно натуральное число N (2 ≤ N ≤ 22).

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

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

Пример

Ввод	Вывод
3	6

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

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

Это Бомба#24906

Мише приснился страшный сон как будто ему очень быстро необходимо разминировать бомбу! На большом дисплее бомбы он видит одно число, рядом есть клавиатура с цифрами (явно для экстренной отмены взрыва), а где-то внизу уже идёт обратный отсчёт. По удачному стечению обстоятельств у него с собой есть инструкция для разминирования, в которой ему нужно срочно разобраться. В такой тяжялой ситуации мозги у Миши совсем отказали и ему явно нужна помощь.

Инструкция:

Посчитайте числовой код для числа на дисплее соответственно приведённым правилам и введите его. Применяется первое подошедшее правило:

1. Если число <= 2, то числовой код равен 1.

2. Если число заканчивается на 7, то нужно отнять от него 5. Посчитайте числовой код для нового числа и прибавьте 1.

3. Если число делится на 4 без остатка, его числовой код равен сумме кодов для числа,делённого на 4 и числа, делённого на 2.

4. Во всех остальных случаях к числу нужно прибавить 1. Посчитайте числовой код для нового числа и прибавьте 2.

Какой числовой код нужно ввести Мише?

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

В единственной строке содержится одно число от 1 до 10⁸, которое отображается на дисплее.

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

Выведите в ответ одно число, которое Мише нужно срочно ввести.

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

Выведите в ответ одно число, которое Мише нужно срочно ввести.

Ввод	Вывод
1	1
10	12

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

✓ 25✗ 16500лёгкаяВойти и решать

Максимальная прибыль#24755

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

Про каждую задачу известно время t_i, которое нужно затратить, чтобы сделать её, а также прибыль p_i, которую сделанная задача принесёт компании. Вы хотите включить в план некоторые задачи так, чтобы:

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

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

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

Входные данные

В первой строке находятся натуральные числа T (1 ≤ T ≤ 100 000) и n (1 ≤ n ≤ 10) - число единиц времени в месяце и число задач.

Следующие n строк содержат по два натуральных числа t_i и p_i (1 <= t_i, p_i <= 100 000) - время, которое необходимо затратить на выполнение i-й задачи и прибыль, которую можно получить, выполнив её.

Выходные данные

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

Примеры

№	Входные данные	Выходные данные
1	10 3 8 100 3 10 3 10	100
2	10 4 5 10 5 20 2 5 2 6	31

битмаски Задача о рюкзаке

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

Вупсень и Пупсень 2#24637

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

Подпалиндромом называется такая попоследовательность строки, которая читается справа налево также, как и слева направо.

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

В первой строке дана строка s, во второй строке строка t, состоящие из строчных латинских букв. 1 <= |s|, |t| <= 50.

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

Выведите одно целое число n - длину наибольшей общей подпоследовательности, являющейся палиндромом.

Примеры

Ввод	Вывод
mem kek	1
acab abca	3

(с) Буков Антон, 11и

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

✓ 1✗ 31 200средняяВойти и решать

Пустоты в кубе#23588

Жюри составило отчет об учебно-тренировочных сборах по информатике и собирается распечатать его на стандартном листе бумаги. Весь отчет набран одним моноширинным шрифтом, т.е. все символы (включая пробелы) имеют одинаковую ширину. Длина строки при печати этим шрифтом на листе бумаги равна S.

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

Для достижения требуемого расположения текста на бумаге разрешается заменять произвольную пробельную последовательность (т.е. непустую последовательность подряд идущих пробелов или символов перевода строки) любой другой пробельной последовательностью.

Входные данные

Первая строка входного файла содержит целое число S (1<=S<=80).

В последующих строках записан отчет, содержащий не более 500 слов.

Длина каждой строки отчета не превосходит 250 символов, а длина каждого слова не превос-ходит S.

Выходные данные

Вывести в первую строку выходного файла минимально возможную сумму

кубов пустот по всем строкам. В последующие строки следует вывести

искомое расположение текста на листе бумаги.

Пример входного файла

Победители летних учебно-тренировочных сборов по информатике 1997 г.:

Владимир Мартьянов,

Анатолий Пономарев,

Николай Дуров,

Андрей Лопатин.

Пример выходного файла

325

Победители летних

учебно-тренировочных сборов по

информатике 1997 г.: Владимир

Мартьянов, Анатолий Пономарев,

Николай Дуров, Андрей Лопатин.

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

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

Покупка билетов#23414

За билетами на премьеру нового мюзикла выстроилась очередь из N человек, каждый из которых хочет купить 1 билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно, приводя "постояльцев" очереди в отчаяние. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продаёт быстрее, чем когда эти же билеты продаются по одному.

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

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

Известно, что на продажу i-му человеку из очереди одного билета кассир тратит A_i секунд, на продажу двух билетов - B_i секунд, трех билетов - C_i секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели.

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

Входные данные:
- в первой строке записано число N - количество покупателей в очереди (\(1<=N<=5000\));
- далее идет N троек натуральных чисел A_i, B_i, C_i. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются начиная от кассы.

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

Примеры

№	Входные данные	Выходные данные
1	5 5 10 15 2 10 15 5 5 5 20 20 1 20 1 1	12
2	2 3 4 5 1 1 1	4

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

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

Шаблон и слово#23413

Требуется определить подходит ли заданное слово под заданный шаблон. Шаблон задается большими латинскими буквами, знаками "?" - любой символ, "*" - любая последовательность символов (даже пустая).

Входные данные
В первых двух строках записаны шаблон и слово: в одной из них записан шаблон - последовательность больших латинских букв, "?" и "*", в другой - слово, состоящее только из больших латинских букв (строки короче 100 символов).

Выходные данные
Вывести YES, если слово подходит, NO, если не подходит.

Примеры

№	Входные данные	Выходные данные
1	ABBCDA A*CDA	YES
2	AADAAVA ADAAA*	NO

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

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

Ход конем#23411

Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-4927. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.

Клавиатура телефона выглядит так:

7	8	9
4	5	6
1	2	3
	0

Напишите программу, определяющую количество телефонных номеров длины N, набираемых ходом коня.

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

Выходные данные: выведите файл искомое количество телефонных номеров.

Примеры

№	Входные данные	Выходные данные
1	2	16

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

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

Подпоследовательности#23409

Дана последовательность, требуется найти длину наибольшей возрастающей

подпоследовательности.

Входные данные

В первой строке входного файла записано число N - длина последовательности (1 <= N <= 1000). Во второй строке записана сама последовательность (через пробел). Числа последовательности - целые числа, не превосходящие 10000 по модулю.

Выходные данные

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

Примеры

№	Входные данные	Выходные данные
1	6 3 29 5 5 28 6	3

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

✓ 513✗ 959300лёгкаяВойти и решать

Гвоздики#23408

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

Входные данные:

- в первой строке записано число N - количество гвоздиков (\(2 <= N <= 100\));
- в следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).

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

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

✓ 665✗ 1 376600лёгкаяВойти и решать

Минимальный путь в таблице#23407

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

За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено).

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

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

Входные данные

В первой строке записаны два числа N и M - размеры таблицы (\(1<=N<=20\), \(1<=M<=20\)). Далее записаны N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (каждое число от 0 до 100).

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

Примеры

№	Входные данные	Выходные данные
1	3 4 1 1 1 1 5 2 2 100 9 4 2 1	8

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

✓ 725✗ 746400лёгкаяВойти и решать

**Столовские котлеты#23380

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

Конечно, введенное правило оставляет существенный произвол в числе котлет, получаемых очередным явившимся лицеистом, и это число не в последнюю очередь будет зависеть от предыдущего поведения лицеиста в столовой, а также от волшебных слов, произносимых им. Например, 6 котлет могут быть в результате распределены по одной из следующих четырех схем: 3+2+1 (три котлеты первому из пришедших школьников, две - второму и одну - третьему), 4+2, 5+1 и 6 (все котлеты съедает счастливчик, пришедший первым).

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

Входные данные

Входной файл содержит одно целое число N - количество приготовленных поваром котлет (0<=N<=200).

Выходные данные

Выходной файл должен содержать одно целое число, равное количеству возможных распределений котлет.

Примеры

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

Задача о рюкзаке

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

НВП на отрезке#23377

Нам дана числовая последовательность a₁, ..., a_n . Напишите программу, отвечающую на запросы вида "найти длину наибольшей строго возрастающей подпоследовательности, все элементы которой находятся на отрезке с l_i-ого по r_i-ый элемент".

Подпоследовательностью последовательности a₁ , ..., a_n называется последовательность, которую можно получить путем удаления нескольких элементов a_i (относительный порядок оставшихся элементов менять запрещается). Так, например, последовательность (2, 4) является подпоследовательностью последовательности (1, 2, 3, 4, 5) (можно удалить элементы 1, 3 и 5 ), а последовательность (5, 1) - нет.

Входные данные

В первой строке записано целое число n (1 <= n <= 3000 ) - число элементов в последовательности. Во второй строке записано n чисел, разделенных пробелами - элементы последовательности. Все элементы не превосходят по модулю 10⁹. В третьей строке записано одно целое число q (1 <= q <= 10⁵) - количество запросов. В следующих q строках описаны запросы. Описание i -ого запроса - два числа l_i и r_j (1 <= l_i <= r_i <= n) , записанные через пробел.

Выходные данные

Выведите q чисел - ответы на запросы. Числа следует выводить по одному на строке в том же порядке, в котором запросы описаны во вводе.

Примеры

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

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

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

По крышам!#23367

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

Инна любит гулять по крышам. Она стоит на крыше здания с номером 1 и хочет попасть на крышу здания с номером n.

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

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

Формат входных данных
В первой строке задано натуральное число n — число зданий в Иннополисе (n<= 10⁵). В следующих n строках заданы крыши зданий. Каждая из этих строк содержит четыре целых числа x_i1, y_i1, x_i2 и y_i2 — координаты противоположных вершин прямоугольника, описывающего крышу здания (x_i1 < x_i2; y_i1 < y_i2) Гарантируется, что никакие два прямоугольника не имеют общих точек. Все координаты — неотрицательные целые числа и <= 10⁹

Формат выходных данных
Выведите одно целое число — минимальное количество прыжков, которые Инна должна совер- шить, чтобы добраться с крыши здания 1 до крыши здания n. Если же Инна не может добраться до крыши n-го здания, выведите -1.

Ввод	Вывод
4 0 0 3 2 1 6 4 8 1 3 4 5 7 7 10 9	3
3 0 0 3 2 1 3 4 5 7 7 10 9	-1

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

✓ 0✗ 71 200средняяВойти и решать

Ведьмак#22027

По приезде Геральда в Каэр-Морхен уже наступила зима. Вокруг стояла тишина, а окна замка приветливо светились в темноте. Редкие факелы создавали теплую и согревающую атмосферу, освещая ровный белый ковер из снега. Среди этой красоты особенно порадовал Геральда отъезд Весемира, ведь теперь можно закатить грандиозную пьянку!
Для этого на кухонный стол достали n кружек. Геральд суетился и переставлял кружки с l по r в позицию i, Ламберт с упоением доливал Ривский эль в кружки с l по r по s литров в каждую, а вот Эскель , пока никто не видит, выпивал или доливал в каждую кружку с l по r столько, чтобы в них осталось ровно по k литров в каждой. Спустя почти час Йеннифер, которой порядком надоела брань Ламберта и Эскеля, спустилась вниз, чтобы узнать причину шума. После небольшой перепалки Йеннифер решила помочь отнести кружки в главную столовую, где бурное веселье ведьмаков не мешало бы ей спать. Но так как кружки очень тяжелые, то она может унести не более l литров. Естественно, она хочет пойти спать как можно быстрее, а значит собирается унести как можно больше эля, но общим весом не более l.

Помогите Йеннифер узнать, какой максимальный вес и количество кружек с таким весом она может унести?

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

Дано число n(1 <= n <= 10^4) количество кружек и q(1 <= q <= 10^4) – количество операция. Далее идет описание операций(1 <= l <= r <= 10^4)

• G l r i - Геральд переставляет кружки с l по r в позицию I (1 <= I <=10^4+1)(вставка отрезка производится перед указанным индексом)

• L l r s - Ламберт доливает в кружки с l по r по s литров (1 <= s <= 10^3)

• E l r k – Эскель выпивает из кружек с l по r так, чтобы в каждой оказалось по k литров (1 <= k <= 10^3)

Затем на новой строке идет число l(1 <= l <= 10^5) – количество литров которые может унести Йеннифер.

Изначально в кружках по 0 литров.

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

На первой строке через пробел вывести последовательность кружек после проделанных операций, а на второй строке максимальное количество кружек, которые сможет унести Йеннифер и их общий вес.

Пример входных данных	Пример выходных данных
5 7 L 2 5 10 G 1 3 5 L 1 4 3 L 3 3 4 E 2 3 2 E 2 2 4 E 5 5 15 15	13 4 2 13 15 2 15
5 6 E 1 1 1 E 2 2 2 E 3 3 3 E 4 4 4 E 5 5 5 G 5 5 1 10	5 1 2 3 4 4 10
5 8 E 1 1 1 E 2 2 2 E 3 3 3 E 4 4 4 E 5 5 5 G 5 5 1 G 1 1 6 G 1 5 1 10	1 2 3 4 5 4 10

Пояснения к 1 примеру

1. 0 10 10 10 10

2. 10 0 10 10 10

3. 13 3 13 13 10

4. 13 3 17 13 10

5. 13 2 2 13 10

6. 13 4 2 13 10

7. 13 4 2 13 15

Йеннифер может унести 15 литров. Это значит что она может взять либо одну кружку (15 литров или 13 литров), либо две кружки(4 и 2 литра или 13 и 2 литра). Так как она хочет унести как можно больше кружек, то ответ 2.

Пояснения к 3 примеру

1. 1 0 0 0 0

2. 1 2 0 0 0

3. 1 2 3 0 0

4. 1 2 3 4 0

5. 1 2 3 4 5

6. 5 1 2 3 4

7. 1 2 3 4 5

8. 1 2 3 4 5

Йеннифер может унести 10 литров. Наилучший вариант будет 4 и 3 и 2 и 1 литр. Ответ 4.

(с) Аксенов Владимир 10и

Задача о рюкзаке реализация

✓ 1✗ 31 200средняяВойти и решать

Минимальный путь в таблице#22016

В прямоугольной таблице NxM (в каждой клетке которой записано

некоторое число) в начале игрок находится в левой верхней клетке.

За один ход ему разрешается перемещаться в соседнюю клетку

либо вправо, либо вниз (влево и вверх перемещаться запрещено).

При проходе через клетку с игрока берут столько у.е., какое число

записано в этой клетке (деньги берут также за первую

и последнюю клетки его пути).

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

попасть в правый нижний угол.

Входные данные

Во входном файле задано два числа N и M - размеры таблицы (1<=N<=20,

1<=M<=20). Затем идет N строк по M чисел в каждой - размеры штрафов

в у.е. за прохождение через соответствующие клетки (числа от 0 до 100).

Выходные данные

В выходной файл запишите минимальную сумму, потратив которую можно попасть

в правый нижний угол.

Пример входного файла

3 4

1 1 1 1

5 2 2 100

9 4 2 1

Пример выходного файла

Динамическое программирование на таблицах

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

Чемпионат по поиску в сети Меганет#21889

Для проведения чемпионата мира по поиску в сети Меганет организаторам необходимо ограничить доступ к некоторым адресам. Адрес в сети Меганет представляет собой строку, состоящую из имени сервера и имени раздела.

Имя сервера представляет собой строку, содержащую от одной до пяти частей включительно. Каждая часть представляет собой непустую строку, состоящую из строчных букв латинского алфавита. Части разделены точкой. Примеры корректных имен сервера: «a», «ab.cd», «abacaba», «a.b.c.d.e».

Имя раздела представляет собой строку, которая может быть либо пустой, либо содержать от одной до пяти частей включительно. Каждая часть начинается с символа «/», после которого следует одна или несколько строчных латинских букв. Примеры корректных имен разделов: «», «/a», «/aba», «/a/b/c/d/e». Адрес формируется приписыванием имени раздела в конец имени сервера. Например, корректными адресами являются строки: «a», «aba/d/f/g/h», «a.b», «aba.caba/def/g», «c.d.e.f.g/a/b/c/d/e».

Для ограничения доступа к некоторым адресам сети Меганет организаторы чемпионата подготовили несколько фильтров. Фильтр, как и адрес, состоит из двух частей: фильтра сервера и фильтра раздела.

Фильтр сервера состоит из имени сервера, перед которым может также идти строка «*.». Если фильтр сервера представляет собой только имя сервера, то этому фильтру соответствует только сервер, имеющий точно такое же имя. Если фильтр сервера представляет собой строку «*.S », где S — имя сервера, то ему соответствуют сервера, удалением нуля или более начальных частей от имени которых можно получить строку S.

Аналогично, фильтр раздела представляет собой имя раздела, после которого может идти строка «/*». Фильтру раздела, который представляет собой просто имя раздела R, соответствуют только разделы, в точности совпадающие с R. Если фильтр раздела представляет собой строку «R/*», то ему соответствуют все разделы, удалением от имен которых нуля или более конечных частей можно получить строку R. Адрес соответствует фильтру, если его имя сервера соответствует фильтру сервера, а его имя раздела соответствует фильтру раздела.

Примеры фильтров и соответствующих им адресов приведены в таблице ниже.

ab.c/d/e	ab.c/d/e
*.a	a ax.a efg.a
*.a/b/c	a/b/c x.a/b/c e.fg.a/b/c
x.yz/a/*	x.yz/a x.yz/a/b/c x.yz/a/xyz
.a/	a x.a e.fg.a a/b/c x.a/ddd/c e.fg.a/b/c/g/haha/i
.a/b/c/	a/b/c x.a/b/c e.fg.a/b/c a/b/c/xxx e.fg.a/b/c/d/e/f

Требуется написать программу, которая по заданному набору фильтров и списку адресов определяет для каждого адреса, какому числу фильтров соответствует этот адрес.

Пример:
Ввод:
2 0
a.bb/c
bb/c/d
4
a.bb
bb/c/d
a.bb/c/d
bb/c

Вывод:
0
1
0
0

Вывод:
4 0
*.bb/c
*.bb/c/*
bb/c/*
bb/c/*
6
bb
bb/c
bb/c/d
a.bb
a.bb/c
a.bb/c/d

Вывод:
0
4
3
0
2
1

Динамическое программирование Задача на реализацию Конструктив Строки Структуры данных

✓ 1✗ 101 300средняяВойти и решать

Удаление#21845

У Гудвина есть последовательность чисел из которой он хочет удалить три элемента так, чтобы последовательность была наиболее симпатичной.

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

После удаления из последовательности трех элементов все остальные сдвигаются на нужные места. Например, из последовательности {1, 2, 3, 4, 5} можно получить последовательность {2, 4}.

Входные данные

В первой строке записано целое число n (4 ≤ n ≤ 10⁶) — количество элементов в исходной последовательности. Во второй строке записаны n разделенных пробелами целых чисел — члены последовательности, разделенные пробелами. Все числа в последовательности по модулю не превышают 10⁹.

Выходные данные

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

Примеры тестов

Входные данные

4
1 2 3 4

Выходные данные

Входные данные

5
1 2 3 4 5

Выходные данные

-4

Примечание

Тесты разделены на группы, но оцениваются отдельно

n ≤ 81 — 20 баллов
n ≤ 300 — 10 баллов
n ≤ 5000 — 20 баллов
Без дополнительных ограничений — 50 баллов

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

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

Завоевание#21812

Лорд Петир собирает армию для похода на соседнее королевство. Он хочет, чтобы в его армию вошли все воины каждого из n городов его королевства. Петир выяснил, что в i-м городе ищут работу a_i воинов, которых он может завербовать в свою армию.

Исходно в армии Лорда нет ни одного воина. Чтобы воин вошел в армию, Петир может заплатить этому воину. Для вербовки одного воина из i-го города, необходимо заплатить ему c_i золотых монет. При этом воины из больших городов ценят свою работу дороже, поэтому если для i-го и j-го города выполнено a_i < a_j , то ci ≤ c_j . Однако есть еще один способ добиться того, чтобы воины присоединились к армии. Если в какой-то момент оказывается, что в армии Лорда Петира уже строго больше воинов, чем осталось в некотором городе, то все воины этого города бесплатно присоединяются к армии Лорда.
Помогите Лорду Петиру выяснить, какое минимальное количество золотых монет он должен заплатить воинам, чтобы все воины из всех городов оказались в его армии.

Входные данные

В первой строке входного файла находится целое число n (1 ≤ n ≤ 1000) — количество городов, в которых Лорд Петир намерен набирать себе воинов. В следующих n строках входного файла находится по два целых числа a_i и c_i (1 ≤ a_i ≤ 100, 1 ≤ c_i ≤ 10 000) — количество воинов в i-м городе и число монет, которое необходимо заплатить одному воину в этом городе, чтобы он присоединился к армии. Для всех пар i и j выполнено условие, что если a_i < a_j , то c_i ≤ c_j .

Выходные данные

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

Примеры

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

В приведенном примере Лорду необходимо действовать следующим образом. Сначала он платит 2 монеты воину из второго города, и 3 монеты воину из третьего города, чтобы они присоединились

к его армии. Теперь в армии Лорда 2 воина, а в городах осталось 1, 1 и 3 воина, соответственно. Воины из первого и второго городов бесплатно присоединяются к армии Лорда Петира, в его армии становится 4 воина, после чего и оставшиеся 3 воина из третьего города бесплатно присоединяются к его армии.

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

✓ 6✗ 1021 200средняяВойти и решать