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

Шоколад полезный#39245

Услышав, что шоколад полезен для мозга и нервной системы, ученик Василий решает закупить шоколад на весь учебный год. Василий решил закупить шоколада на R рублей. Он обошел в городе все N магазинов, которые продают различный шоколад. Василий сохранил в файл информацию о том, что в i-м магазине он может купить не более B_iплиток шоколада по A_i рублей каждая.
Запасливый ученик хочет потратить как можно больше своих денег (лучше даже сразу все) и купить на них как можно больше шоколада. Помогите Василию понять, сколько плиток шоколада он сможет купить на свои деньги и сколько будет стоить самая дорогая плитка, которую он сможет купить.

Входные данные
Первая строка в файле содержит два числа: N и R. В следующих N строках записана пара чисел: A_i и В_i.

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

Файл к заданию

1 400труднаяВойти и решать

Гимнастические ленты#39226

Для выступления гимнастки используют ленты, которые после выступления кладут на стол. Папа самой лучшей гимнастки Анны К., в ожидании награждения, решил записывать координаты начала и конца лент. Если лента свисала с левого края стола, то он ставил левую координату равной нулю, если лента свисала с правого конца стола, то он ставил правую координату равной нулю. Если лента свисала с двух сторон, то он записывал обе координаты равной нулю. У вас есть файл с данной информацией. Определите, в скольки точках стола получилась самая большая толщина покрытия и чему она равна. Стол имеет длину Lмм. По окончании выступления всех гимнасток, на столе оказалось N лент. У некоторых лент свисает со стола только один конец, у некоторых оба. Все ленты лежат горизонтально. Ленты складываются друг на друга.

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

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

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

Примеры

№	Входные данные	Выходные данные
1	39 4 3 21 3 15 2 20 3 17	4 13

Файл к заданию

ЕГЭ_информатика ЕГЭ-26. Обработка массива целых чисел. Сортировка Сортировка подсчетом

1 500труднаяВойти и решать

Суперстадион#39225

На планете Блук находится самый большой суперстадион Галактики. На суперстадионе 10 000 рядов, пронумерованных начиная с 1. В каждом ряду 10 000 мест, пронумерованных начиная с 1. К текущему моменту, на концерт Суперзвезды продали N билетов. В файле указана информация о проданных билетах: номер ряда и номер места в данном ряду. Определите, в каком ряду больше всего свободных мест, находящихся рядом. Если таких мест одинаковое количество в нескольких рядах, то укажите минимальный номер ряда. А также укажите минимальный номер места, с которого начинаются такие свободные места.

Входные данные
Первая строка входного файла содержит целое число N – общее количество проданных билетов. Каждая из следующих N строк содержит 2 целых числа: номер ряда и номер места в данном ряду.

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

Пример организации исходных данных во входном файле (при 5 рядах и 5 местах в ряду):

17 1 2 2 3 2 4 3 1 3 2 4 1 4 2 4 3 5 1 5 5 5 4 5 2 5 3 3 4 3 5 4 5 1 5

Ответ: 1 3

Файл к заданию

ЕГЭ_информатика ЕГЭ-26. Обработка массива целых чисел. Сортировка Использование сортировки

1 300труднаяВойти и решать

Анализ файла - 08#39159

Текстовый файл состоит из символов M, A, R, S. Определите максимальное количество идущих подряд символов в прилагаемом файле, среди которых нет идущих подряд символов M. Для выполнения этого задания следует написать программу.

Файл к заданию

ЕГЭ_информатика ЕГЭ-24. Обработка символьных строк Обработка текста

1 200труднаяВойти и решать

Отрезки - 11#39084

На числовой прямой даны три отрезка: B = [25; 80], C = [60; 75] и D = [70; 90]. Укажите наименьшую возможную длину такого отрезка A, для которого логическое выражение

\(((x \in C) \neq (x \in B)) \rightarrow (x \in D) \vee (x \in A)\)

истинно (т.е. принимает значение 1) при любом значении переменной х.

ЕГЭ_информатика ЕГЭ-15. Математическая логика Логика и множества

1 200труднаяВойти и решать

Отрезки - 10#39083

На числовой прямой даны три отрезка: B = [25; 80], C = [60; 75] и D = [35; 70]. Укажите наименьшую возможную длину такого отрезка A, для которого логическое выражение

\(((x \in C) \neq (x \in B)) \rightarrow (x \in D) \vee (x \in A)\)

истинно (т.е. принимает значение 1) при любом значении переменной х.

ЕГЭ_информатика ЕГЭ-15. Математическая логика Логика и множества

1 300труднаяВойти и решать

Отрезки - 08#39081

На числовой прямой даны три отрезка: B = [0; 70], C = [30; 60] и D = [20; 90]. Укажите наименьшую возможную длину такого отрезка A, для которого логическое выражение

\((((x \in B) \rightarrow (x \in C)) \wedge (x \in D)) \rightarrow (x \in A)\)

истинно (т.е. принимает значение 1) при любом значении переменной х.

ЕГЭ_информатика ЕГЭ-15. Математическая логика Логика и множества

1 200труднаяВойти и решать

Отрезки - 07#39080

На числовой прямой даны три отрезка: B = [0; 50], C = [25; 60] и D = [35; 80]. Укажите наибольшую возможную длину такого отрезка A, для которого логическое выражение

\((x \in A) \rightarrow ((x \in B) \vee (x \in D)) \wedge (x \notin C)\)

истинно (т.е. принимает значение 1) при любом значении переменной х.

ЕГЭ_информатика ЕГЭ-15. Математическая логика Логика и множества

1 200труднаяВойти и решать

Тюрьма для Зедда#38918

Черный рейнджер нашел в жерле заброшенного вулкана n прямоугольных листов металла разного размера, i-й лист имеет размер a_i на b_i метров.
Зордон поручил построить Черному рейнджеру тюрьму для злобного генерала Зедда, и эта находка оказалась для него просто подарком судьбы. Тюрьма должна иметь вид прямоугольного параллелепипеда каждая грань которого представляет собой цельный лист металла. Так что рейнджер собирается взять 6 из найденных им листов металла, сложить из них параллелепипед, и показать его Зордону. Листы нельзя гнуть или разрезать, листы, из которых будет сложена тюрьма не должны выступать за её края.
Поскольку чем больше тюрьма, чем надежнее, параллелепипед должен иметь максимальный возможный объем. Помогите герою выбрать 6 листов прямоугольников так, чтобы собрать из них самую большую тюрьму.
Листы можно поворачивать, таким образом, например, листы 4 на 7 метров и 7 на 4 метра считаются одинаковыми.

Формат входных данных
В первой строке дано одно число n — количество листов металла у Черного Рейнджера (6 ≤ n ≤ 200 000).
В следующих n строках даны пары чисел a_i; b_i — размеры i-го куска металла (1 ≤ a_i; b_i ≤ 10⁶).

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

Примеры

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

Вывод формулы Задача на реализацию Разбор случаев

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

Радость Громозеки#38716

Громозека имеет последовательность целых чисел A длины N. Он сделает три среза в последовательности A и разделит ее на четыре (непустые) смежные подпоследовательности B, C, D и E. Положения срезов он выбирает произвольно. Пусть P, Q, R, S - суммы элементов в B, C, D, E соответственно. Громозека будет счастлив, когда абсолютная разница между максимумом и минимумом между P, Q, R, S будет минимальной. Найдите минимально возможную абсолютную разницу между максимумом и минимумом между P, Q, R, S.

Входные данные
В первой строке записано целое число N (1 <= N <= 2·10⁵). Во второй строке записано N целых чисел A_i (1 <= A_i <= 10⁹).

Выходные данные
Выведите на экран минимально возможную абсолютную разницу между максимумом и минимумом между P, Q, R, S.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	5 3 2 4 1 2	2	Если разделить A на B, C, D, E = (3), (2), (4), (1,2), то P = 3, Q = 2, R = 4, S = 1 + 2 = 3. Здесь максимум и минимум среди P, Q, R, S равны 4 и 2, с абсолютной разницей 2. Мы не можем сделать абсолютную разницу между максимумом и минимумом меньше 2, поэтому ответ - 2.
2	10 10 71 84 33 6 47 23 25 52 64	36
3	7 1 2 3 1000000000 4 5 6	999999994

"Два указателя"Алгоритмы обработки Массивы

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

То березка, то рябина…#38572

В целях улучшения ландшафтной архитектуры и экологической обстановки управление городского хозяйства разработало проект программы озеленения центрального проспекта. Согласно проекту, с одной стороны проспекта планируется высадить в ряд деревья K различных видов, для чего были закуплены саженцы деревьев, причем i-го вида было закуплено a_i саженцев.

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

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

Входные данные
В первой строке вводятся два целых числа: K — количество различных видов деревьев (1 ≤ K ≤ 100 000), и P — требуемое количество подряд идущих деревьев разных видов (2 ≤ P ≤ K). Последующие K строк входных данных содержат целые числа ai, задающие количество закупленных саженцев деревьев i-го вида (1 ≤ a_i ≤ 10⁹), по одному числу в каждой строке.

Выходные данные
Выведите единственное число — максимальное количество деревьев, посадка которых в ряд в некотором порядке достигает эстетического совершенства.

Примеры

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

Бинарный поиск в массиве Бинарный поиск по ответу Жадный алгоритм

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

LinkedList's Bizarre Adventure#38501

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

Билли и Рикардо проходят стажировку в компании FlexDex в группе поддержки внутреннего анонимного форума с возможностью деанонимизации. Для представления последовательных сообщений в теме необходимо использовать список, где элементами будут являться эти сообщения, и два товарища решили написать свою быструю реализацию двусвязного списка FlexList.

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

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

Говорится, что граф является корректным графом, если в этом графе у каждой вершины не более двух вершин, связанных с ней ребром. Изначально же FlexList связи между сообщениями могут выглядеть в виде любого связного ацикличного графа, не обязательно корректного.

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

Это выглядит так — сначала Билли проверяет, что граф корректный. Если это не так, то он выбирает и удаляет некоторый лист (вершина, у которой есть ровно одна связь с другими вершинами), и отдает граф Рикардо, затем Рикардо делает то же самое и отдает граф Билли, и так продолжается до тех пор, пока кто-то не получит от товарища корректный граф. Как только один из двух друзей получает такой граф, то тут же показывает его тимлиду, с надеждой на похвалу и повышение в должности.

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

Входные данные
В первой строке содержится одно целое число n (1 ≤ n ≤ 300000) — число сообщений в примере тимлида. Следующие n−1 строк задают связи между сообщениями. Каждая из них содержит два целых числа a_i и b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i), которые показывают, что сообщения с номерами a_i и b_i связаны.

Выходные данные
Выведите "Billy" (без кавычек), если первым попадет к тимлиду Билли, иначе выведите "Ricardo" (без кавычек).

Примечание
В первом примере Билли первым ходом может удалить одну из вершин с номерами 2, 4 или 5, так как они являются листьями. Он не будет удалять вершину с номером 4 или 5, так как в таком случае он передаст Рикардо корректный граф и проиграет. Значит, он удалит вершину 2. В свою очередь, Рикардо может удалить вершины 1, 4 или 5, и, в любом случае, Билли получит от него корректный граф.

Во втором примере у Билли сразу есть корректный граф.

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

Примеры

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

Древовидные структуры данных Игры и выигрышные стратегии Простые игры

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

Порталы#38132

Беси расположена на сети из N (2≤N≤10⁵) вершин помеченных 1…N и 2N порталов помеченных 1…2N. Каждый портал соединяет две различных вершины u и v (u≠v). Множество порталов может соединять некоторую пару вершин.
Каждая вершина v соседняя для четырёх различных порталов. Список порталов вершины v задаётся как pv=[p_v,1,p_v,2,p_v,3,p_v,4].

Ваше текущее положение может быть представлено упорядоченной парой (current vertex,current portal); то есть парой (v,p_v,i) где 1≤v≤N и 1≤i≤4. Вы можете использовать одну из следующих операций для изменения своего текущего положения:

Изменить текущую вершину перемещением через текущий портал.
Переключить текущий портал. В каждой вершине первые два портала в списке объединены в пару и последние два портала в списке также объединены в пару. Поэтому если Ваше текущее состояние (v,p_v,2), то Вы можете переключиться чтобы использовать портал (v,p_v,1) и обратно. Аналогично, если Ваше текущее положение (v,p_v,3) Вы можете переключиться на портал (v,p_v,4) и обратно. никакие другие переключения не разрешены (например, Вы не можете переключиться с портала pv,2 на портал) p_v,4).
Всего имеется 4N различных состояний. К несчастью, может не оказаться, что что любое состояние достижимо из любого с помощью последовательности заданных операций. Поэтому, за цену cv (1≤c_v≤1000) мунов вы можете сделать перестановку списка порталов соседних вершине v, в любом желаемом Вами порядке. После этого первые два портала в списке объединяются в одну пару, а последние два портала - в другую пару.

Например, если Вы переставить порталы вершины v в порядке [p_v,3,p_v,1,p_v,2,p_v,4], Это означает. что если Вы в вершине v,

Если Вы в портале p_v,1, Вы можете переключиться на портал p_v,3 и обратно
Если Вы в портале p_v,2, Вы можете переключиться на портал p_v,4 и обратно
Теперь Вы не можете переключаться с портала p_v,1 на p_v,2, или с портала p_v,3 на портал p_v,4 и обратно.
Вычислите минимальное количество мунов, требуемых для модификации сети таким образом, чтобы сделать достижимым каждое состояние из каждого состояния. Гарантируется, что тестовые данные сконструированы таким образом, что существует хотя бы один способ такой модификации сети.

Входные данные:
Первая строка содержит N.
Каждая из следующих N строк описывает вершину. Строка v+1 содержит 5 разделённых одиночными пробелами целых чисел c_v,p_v,1,p_v,2,p_v,3,p_v,4.
Гарантируется, что для каждой v все p_v,1,p_v,2,p_v,3,p_v,4 различны, и каждый портал появляется в списках ровно двух вершин.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 10 1 4 8 9 11 1 2 5 6 12 9 10 2 3 3 4 3 6 7 15 10 8 7 5	13	Достаточно сделать перестановку списков вершин 1 и 4. Это требует c1+c4=13 мунов. Перестановки такие: p1=[1,9,4,8] и p4=[7,4,6,3].

Древовидные структуры данных Минимальный каркас Система непересекающихся множеств

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

Анализ файла - 07#33407

В первой строке текстового файла указано количество строк в файле, содержащих различные символы английского алфавита (от A до Z). Определите количество строк, в которых количество символов, обозначающих гласную букву английского алфавита больше, чем количество символов, обозначающих согласную букву. В ответе укажите одно число.

Для выполнения этого задания следует написать программу.

Файл

task24-2.txt

ЕГЭ_информатика ЕГЭ-24. Обработка символьных строк Обработка текста

1 200труднаяВойти и решать

Splash Bomb#33297

Имеется клетчатое поле размером NxM. В каждой клетке может лежать либо реактив A, либо B, либо ничего не лежать - 0. За ход можно положить в некоторую клетку реактив A, причем преобразование вещества идет по следующему правилу: 0+A->A, A+A->B, B+A->0. При этом в результате последней реакции происходит взрыв, а в соседние непустые клетки по сторонам света (если они есть), попадает по порции реактива A. Очки за ход = количество взрывов минус 1. Очки за отдельные ходы суммируются. Требуется очистить поле и при этом набрать максимальное количество очков.

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

В первой строке вводятся N и M (1 <= N, M <= 3). Далее идут N строк по M символов из алфавита (0, A, B) - описание поля.

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

Выведите единственное число - максимальное количество очков, которое можно набрать.

Комментарий ко второму примеру: за первый ход не произошло ни одного взрыва, очки=0-1=-1; за второй ход произошел один взрыв и поле очистилось, очки=1-1=0; итого очков: 0+(-1)=-1

Ввод	Вывод
1 1 0	0
1 1 A	-1

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

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

Обработка больших данных#33128

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

позволяющая эффективно обрабатывать большие объемы данных.

Суперкомпьютер имеет 2^k ячеек памяти, пронумерованных от 0 до 2^{k– 1}. Отрезком

[L, R] называется последовательность подряд идущих ячеек памяти с номерами от L до R,

включительно.

Некоторые отрезки памяти являются корректными. Отрезок памяти [L, R] является

корректным, если его длина (R – L + 1) равна 2i для некоторого i, а число L делится на 2i.

Например, если k = 3, то ячейки памяти пронумерованы от 0 до 7, а корректными являются

отрезки [0, 7], [0, 3], [4, 7], [0, 1], [2, 3], [4, 5], [6, 7], [0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6,

6] и [7, 7].

Ключевой операцией в новой архитектуре является операция STORE, которая за одно

действие присваивает одно и то же значение всем ячейкам памяти некоторого корректного

отрезка.

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

на суперкомпьютере программу обработки данных, но перед её запуском необходимо

инициализировать память определенным образом. А именно: первые с1 ячеек памяти

необходимо заполнить значениями v1, следующие c2 ячеек — значениями v2, и так далее,

последние cn ячеек памяти необходимо заполнить значениями vn, где 1 ≤ vi ≤ m.

Ученым надо выяснить, какое минимальное количество операций STORE необходимо

выполнить, чтобы проинициализировать память требуемым образом.

Например, если k = 3, n = 3, m = 2, c1 = 1, v1 = 1, c2 = 2, v2 = 2, c3 = 5, v3 = 1, то итоговое

содержимое памяти должно быть следующим: [1, 2, 2, 1, 1, 1, 1, 1]. В этом случае для

инициализации памяти достаточно трех операций STORE:

- STORE([0, 7], 1), после этой операции все ячейки памяти содержат значение 1;

- STORE([1, 1], 2), после этой операции содержимое памяти [1, 2, 1, 1, 1, 1, 1, 1];

- STORE([2, 2], 2) , после этой операции содержимое памяти [1, 2, 2, 1, 1, 1, 1, 1],

как и требуется.

Заметим, что операцию STORE([1, 2], 2) выполнить нельзя, потому что [1, 2] не

является корректным отрезком памяти.

Требуется написать программу, которая по заданному содержимому памяти

определяет минимальное количество операций STORE, которое необходимо выполнить для

инициализации памяти заданным образом.

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

Первая строка входных данных содержит три целых числа: k, n и m (0 ≤ k ≤ 30,1 ≤ n ≤ 10

5, 1 ≤ m ≤ 10⁹).

Следующие n строк содержат по два целых числа, i-я из этих строк содержит числа ci

и vi (1 ≤ ci ≤ 2^k, 1 ≤ vi ≤ m, c1 + c2 + … + cn = 2^k).

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

Требуется вывести одно целое число – минимальное количество операций STORE,

которое необходимо выполнить для инициализации памяти заданным образом.

Ввод	Вывод
3 3 2 1 1 2 2 5 1	3

Динамическое программирование Множества Структуры данных

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

Мониторинг труб#33124

Газораспределительная система одного региона устроена следующим образом. Она

содержит n узлов, пронумерованных от 1 до n, некоторые узлы соединены односторонними

трубами. Узел с номером 1 соответствует центральному газохранилищу.

Система узлов описывается числами от p2, p3, …, pn. Для всех i от 2 до n узел с

номером pi соединен односторонней трубой с узлом i, газ по этой трубе передается от узла pi

к узлу i. Известно, что возможно доставить газ по трубам от центрального газохранилища до

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

используются трубы различных типов, тип трубы обозначается буквой английского алфавита

от «a» до «z». Труба, соединяющая узел pi с узлом i, имеет тип ci.

Для проверки качества труб используется специальный робот. Он помещается в

систему труб в одном из узлов и перемещается по трубам, каждый раз проверяя трубу, по

которой он перемещается. Робот может перемещаться по трубам только в том же

направлении, в котором по трубе передается газ. Совершив одно или несколько

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

Каждый запуск робота должен соответствовать одной из m заданных спецификаций,

пронумерованных от 1 до m. Спецификация с номером t представляет собой строку st,

состоящую из строчных букв английского алфавита. Запуск соответствует спецификации st,

если количество перемещений робота по трубам во время запуска совпадает с длиной st, и

для всех j от 1 до длины st на j-м шаге робот перемещается по трубе, тип которой совпадает с

st[j] —символом на позиции j в спецификации.

Если запуск робота соответствует спецификации с номером t, то стоимость этого

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

можно запускать робот несколько раз. Каждый раз выбирается спецификация и маршрут

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

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

минимальна. Одну и ту же трубу можно проверять несколько раз.

Требуется написать программу, которая по описанию системы труб и списку

спецификаций определяет минимальную суммарную стоимость запусков робота, в

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

запусков (по требованию).

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

В первой строке входных данных находятся три целых числа n, m и t — количество

узлов системы труб, количество спецификаций запусков робота и параметр, указывающий,

требуется ли вывести список запусков робота или только их минимальную суммарную

стоимость (1 ≤ n ≤ 500, 1 ≤ m ≤ 10⁵, t равно 0 или 1).

В последующих (n – 1) строках содержится информация о трубах, (i – 1)-я из этих

строк содержит разделенные пробелом значения pi и ci, где pi — целое число, задающее

номер узла, из которого ведет труба в i-й узел, а ci — строчная буква английского алфавита,

задающая тип этой трубы (1 ≤ pi ≤ i – 1).

В последующих m строках содержится информация о спецификациях, i-я из этих

строк содержит разделенные пробелом целое число wi — стоимость запуска робота в

соответствии с этой спецификацией, и состоящую из строчных букв английского алфавита

строку si — саму спецификацию (1 ≤ wi ≤ 10⁹). Суммарная длина строк si не превышает 10⁶.

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

Первая строка выходных данных должна содержать одно число — минимальную

суммарную стоимость запусков робота, в результате которых все трубы будут проверены.

Если проверить все трубы невозможно, требуется вывести «–1».

Если t = 0, то больше ничего выводить не требуется.

Если t = 1 и проверить трубы возможно, то далее следует вывести список описаний

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

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

следующих k строках необходимо вывести по три целых числа ai, bi и ci — номер узла, в

котором начинается запуск, номер узла, в котором заканчивается запуск, и номер

спецификации, которой соответствует запуск.

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

Ввод	Вывод
3 3 0 1 a 2 b 3 a 4 b 2 a	6
7 3 1 1 a 2 a 3 b 3 b 1 b 6 b 3 aab 5 b 2 ab	15 4 1 4 1 2 5 3 1 6 2 6 7 2

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

Система труб, заданная во втором примере входных данных, и оптимальный способ

проверки всех труб для этого случая приведены на рисунке ниже.

Необходимо обратить внимание на следующие моменты:

- трубу можно проверять несколько раз, так в приведенном примере дважды

проверена труба из узла 2 в узел 3;

- одну и ту же спецификацию разрешается использовать несколько раз, в

приведенном примере вторая спецификация используется дважды, для

проверки труб из узла 1 в узел 6 и из узла 6 в узел 7;

- робот может перемещаться по трубам только в том же направлении, по

которому по трубе передается газ, спецификацию «ab» нельзя использовать

для проверки труб по маршруту 2→1→6, так как робот не может

переместиться из узла 2 в узел 1.

Алгоритмы на графах Деревья Динамическое программирование

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

RSA: Расшифровка#31923

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

Входные данные
В первой строке вводятся p и q (\(3<=p,q<10\)), далее вводится сообщение состоящее из натуральных чисел, каждое не превышающее 100. Сообщение заканчивается нулем.

Выходные данные
Выведите расшифрованное сообщение.

Примеры

№	Входные данные	Выходные данные
1	3 7 1 11 12 0	123

Быстрое возведение в степень МЦКО-10. RSA Расширенный алгоритм Евклида

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

RSA. Расшифровать небольшое сообщение.#31918

Даны два простых числа p и q. Надо расшифровать сообщение длинной N с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (3<=p,q<10), далее вводится длина N (N<10) и сообщение состоящее из натральных чисел не превышающее 10.

Ввод	Вывод
3 7 3 1 11 12	1 2 3

Быстрое возведение в степень МЦКО-10. RSA Остатки

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

Censoring#27298

Фермер Джон купил подписку журнала Good Hooveskeeping для своих коров. К сожалению, последний номер содержит неподходящую статью - как приготовить бифштекс. ФД не хочет, чтобы его коровы её читали.

ФД взял текст журнала, создал строку S длиной не более чем 10^5 символов. У него есть список слов t_1, t_2, ..., t_N, которые он хочет удалить из S. Поэтому ФД находит ближайшее вхождение слова из списка T (то есь с наименьшим индексом) и удаляет его из S. Затем он продолжает это процесс опять, пока в S не останется слов из T. Заметим, что удаление слова может создавать новое вхождение свлоа из T, которое не существовало ранее.

ФД заметил, что слова из списка T обладают таким свойством, что никакое из них не является подстрокой другого слова из T. В частности, это означает, что ранее вхождение слова из T в S всегда определено однозначно. Пожалуйста, помогите ФД определить финальное содержание строки S.

INPUT FORMAT:

Первая строка содержит S. Вторая строка содержит N - количество удаляемых слов. Последующие N строк содержат строки t_1, t_2, ..., t_N. Каждая строка содержит только маленькие латинские буквы (a..z) и суммарная длина всех строк не превысит 10^5.

OUTPUT FORMAT:

Строка S после всех удалений. Гарантируется, что S не станет пустой.

Ввод	Вывод
begintheescapexecutionatthebreakofdawn 2 escape execution	beginthatthebreakofdawn

Строки Структуры данных Хеш

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