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

Кластеры роботов - 2#62562

На производстве расположены \(n\) роботов, пронумерованных от \(1\) до \(n\). Любая пара роботов может быть либо соединена проводом, либо нет. Известно, что \(i\)-й робот соединен с \(k_i\) другими роботами с номерами \(v_{i,1}, \ldots, v_{i,k_i}\). Провода двухсторонние, то есть если \(i\) связан с \(j\), то \(j\) связан с \(i\) (иными словами, \((i, j)\) и \((j, i)\) — это один и тот же провод).

Вы находитесь рядом с роботом номер \(n\). Роботом номер \(t\) можно управлять, если он связан с \(n\)-м некоторой цепочкой проводов, то есть

либо если \(t = n\);
либо если существуют такие \(i_1, \ldots, i_k\), что \(i_1 = n\), \(i_k = t\), и любые два соседних в этой последовательности робота \(i_j\) и \(i_{j + 1}\) связаны проводом.

Любому из роботов, которыми можно управлять, можно послать команду <<извлеки второй конец подключенного к себе провода и подключи его к другому роботу>>. Иными словами, если роботом номер \(t\) можно управлять, и есть провод, соединяющий его с роботом номер \(x\), то можно заменить провод \((t, x)\) на провод \((t, y)\) для любого \(y \neq t\), еще не связанного проводом с \(t\). Обратите внимание, что после этого вы можете потерять управление над \(t\)-м роботом, если единственная связь \(t\)-го с \(n\)-м проходила через \(x\)-й.

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

Формат входных данных
В первой строке записано целое число \(T\) (\(1 \le T \le 1000\)) — количество наборов входных данных в тесте.

Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(1 \leq n \leq 10^5\)) — количество роботов.

Затем следуют \(n\) строк, в \(i\)-й из которых записаны числа \(k_i\) (\(0 \le k_i \le n - 1\)) и \(v_{i,1}, \ldots, v_{i,k_i}\) (\(1 \le v_{i,j} \le n\); \(v_{i,j} \neq i\)) — количество проводов, подключенных к \(i\)-му роботу, и номера роботов на противоположных концах этих проводов. Гарантируется, что данные корректны: никакие два провода не соединяют одну и ту же пару роботов, и если \(j \in v_i\), то \(i \in v_j\).

Также гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\) и сумма количества проводов по всем наборам входных данных не превосходит \(1.5 \cdot 10^5\).

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

В следующих \(k\) строках выведите сами описания действий в формате <<\(y\) + \(t\) - \(x\)>> (\(1 \leq t, x, y \leq n\); \(x \neq y\)). Каждая такая строка соответствует замене провода \((t, x)\) на провод \((t, y)\).

Если возможных ответов несколько, выведите любой. Обратите внимание, что \(k\) при этом обязано быть наименьшим, при котором можно подключить максимальное количество роботов.

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

Кластеры роботов#62485

На производстве расположены \(n\) роботов, пронумерованных от \(1\) до \(n\). Любая пара роботов может быть либо соединена проводом, либо нет. Всего на производстве \(m\) проводов и \(i\)-й из них сейчас соединяет роботов с номерами \(a_i\) и \(b_i\).

Вы находитесь рядом с роботом номер \(1\). Роботом номер \(t\) можно управлять, если он связан с первым некоторой цепочкой проводов, то есть

либо если \(t = 1\);
либо если существуют такие \(i_1, \ldots, i_k\), что \(i_1 = 1\), \(i_k = t\), и любые два соседних в этой последовательности робота \(i_j\) и \(i_{j + 1}\) связаны проводом.

Первая строка каждого набора входных данных содержит целые числа \(n\) и \(m\) (\(1 \leq n \leq 10^5\); \(0 \leq m \leq 1.5 \cdot 10^5\)) — количество роботов и количество проводов, соответственно.

В следующих \(m\) строках дано описание проводов: в \(i\)-й строке даны целые числа \(a_i\) и \(b_i\) (\(1 \leq a_i, b_i \leq n\); \(a_i \neq b_i\)) — номера роботов, соединенных \(i\)-м проводом. Гарантируется, что никакие два провода не соединяют одну и ту же пару роботов.

Также гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\) и сумма \(m\) по всем наборам входных данных не превосходит \(1.5 \cdot 10^5\).

В следующих \(k\) строках выведите сами описания действий по одному на каждой строке. Описание действия должно состоять из трех целых чисел \(t\), \(x\) и \(y\) (\(1 \leq t, x, y \leq n\); \(x \neq y\)), означающих, что робот номер \(t\) меняет провод \((t, x)\) на провод \((t, y)\).

Деревья Жадный алгоритм Конструктив Обход в глубину

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

Мишины кубики#43718

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

Строка x лексикографически меньше строки y только и только тогда, когда выполняется одно из следующих условий:
- x является префиксом y, но x != y;
- в первой позиции, где x и y различаются, в строке x находится буква, которая стоит в алфавите раньше, чем соответствующая буква y.

Входные данные
Программа получает на вход несколько строк. В первой строке записаны три числа: n - количество кубиков в первом ряду, m - количество кубиков во втором ряду, k - целое число(1 <= n, m, k <= 100). Во второй строке записана строка a длиной n - строка, образованная прочтением букв, написанных на кубиках первого ряда. В третьей строке - строка b длиной m - строка, образованная прочтением букв, написанных на кубиках второго ряда.

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

Примеры

№	Входные данные	Выходные данные
1	6 4 2 aaaaaa bbbb	aabaabaa

"Два указателя"Жадный алгоритм Задача на реализацию Использование сортировки Простые задачи на перебор

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

Эльфы и олени#38920

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

Но волшебные олени – строптивые животные, поэтому не любые два эльфа могут ехать на любом олене. А именно, каждый олень характеризуется некоторой строптивостью a_i, а каждый эльф – темпераментом b_i. Два эльфа j и k могут ехать на i-м олене в том и только в том случае, если либо b_j < a_i < b_k, либо b_k < a_i < b_j.

Чтобы его появление было максимально зрелищным, Санта-Клаус хочет, чтобы в его упряжке было как можно больше оленей. Про каждого оленя Санта знает его строптивость, а про каждого эльфа – его темперамент.

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

Входные данные
В первой строке вводятся два целых числа m и n – количество оленей и эльфов, соответственно ( 1 ≤ m, n ≤ 100 000).

Вторая строка содержит m целых чисел a_i – строптивость оленей ( 0 ≤ a_i ≤ 10⁹). В третьей строке записаны n целых чисел b_i – темперамент эльфов ( 0 ≤ b_i ≤ 10⁹).

Выходные данные
В первой строке выведите одно число k – максимальное количество оленей, которое Санта-Клаус может включить в свою упряжку. В следующих k строках выведите по три целых числа: d_i, e_i, 1, e_i, 2 – для каждого оленя в упряжке выведите его номер и номера эльфов, которые на нем поедут. Если решений несколько, выведите любое.

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

Примеры

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

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

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

Деревни#38444

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

Формат входных данных
Первая строка входного файла содержит два числа: N и P (1 ≤ P ≤ N ≤ 150). Все остальные строки содержат описания дорог, по одному на строке: описание дороги состоит из двух номеров деревень (от 1 до N), которые эта дорога соединяет. Все числа во входном файле разделены пробелами и/или переводами строки.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 2 1 2 3 2	1
2	11 6 1 2 1 3 1 4 1 5 2 6 2 7 2 8 4 9 4 10 4 11	2	группа деревень (1, 2, 3, 6, 7, 8) окажется изолированной от остальных, если разрушить дороги 1–4 и 1–5.

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

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

Красота фейерверка#33127

В лаборатории теоретической пиротехники изучают новые технологии организации

фейерверков. Фейерверк представляется как корневое дерево, а поскольку в мощном

фейерверке его элементы также взрываются, порождая новые фейерверки, то ученые вводят

операцию возведения корневого дерева в степень.

Корневое дерево содержит одну или несколько вершин. Одна из вершин выделена и

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

является родителем. При этом от любой вершины можно добраться до корня,

последовательно переходя от вершины к ее родителю. Вершина, которая не является

родителем никакой другой вершины, называется листом. Если вершина x является

родителем вершины y, то вершина y является ребенком вершины x. Будем говорить, что

вершина и ее родитель соединены ребром.

На рис. 1 показан пример корневого дерева с корнем в вершине 1. Родителем вершин

2 и 3 является вершина 1, родителем вершины 4 является вершина 2. Вершины 2 и 3 — дети

вершины 1, а вершина 4 — ребенок вершины 2. Листьями являются вершины 3 и 4.

Рис. 1. Пример корневого дерева с корнем в вершине 1, листьями 3 и 4.

Фейерверк задается своим базовым деревом T и мощностью m. Фейерверк представляется деревом, которое получается в результате возведения дерева T в степень m. Операция возведения дерева в степень устроена следующим образом. Если m = 1, то результат T¹ — само дерево T. Для m > 1 рассмотрим дерево T^{m – 1} . Выполним следующую операцию: для каждого листа x дерева T^{m – 1} создадим копию дерева T и назначим лист x родителем корня соответствующей копии. Получившееся дерево будет деревом T^m .

На рис. 2 показано дерево, представленное на рис. 1, в степенях 1, 2 и 3.

Рис. 2. Пример возведения дерева в степени 1, 2 и 3

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

вершины соединены ребром. Все вершины в пути должны быть различны.

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

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

фейерверк. На рис. 3 приведен путь в дереве T², содержащий максимальное количество

вершин. Таким образом, красота фейерверка с базовым деревом T и мощностью 2 равна 10.

Рис. 3. Путь в дереве T² , содержащий максимальное количество вершин.
Требуется написать программу, которая по описанию дерева T и натуральному числу m определяет красоту фейерверка с базовым деревом T и мощностью m.

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

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

вершин в базовом дереве фейерверка T и его мощность (3 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000).

Вторая строка описывает дерево T и содержит (n – 1) целых чисел: p2, p3, …, pn —

номера родителей вершин 2, 3, …, n, соответственно (1 ≤ pi ≤ i – 1).

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

Требуется вывести одно целое число — красоту фейерверка, представляемого

деревом T^m.

Ввод	Вывод
4 2 1 1 2	10

Динамическое программирование Динамическое программирование Динамическое программирование на поддеревьях Обход в глубину Применение обхода в глубину

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

65817#65817

В далёком заснеженном города Снежнокрибирске очень мало пеших тропинок, так как город просто не успевает их чистить, потому люди передвигаются в основном только на внедорожниках: ездят в магазин, отвозят детей в школу, ездят на работу и так далее.
В один из последних дней перед зимними каникулами ребятам в школе задали проект на каникулы, который можно делать как самому, так и в группе, но не более 3 человек. Но так как проект связан с совместной работой, а в городе нет никакой связи: ни телефонной, ни интернета, то ребята решили собираться у кого-нибудь дома, чтобы делать проект вместе. Так как проект может делать до трёх человек, то ученики составили карту своих домов в городе, а также отметили на них тропинки. У них встал вопрос о том, как делать большинство проектов максимальным возможным количеством человек, но так, чтобы как можно меньше учеников делали проект одни. Помогите ребятам по описанию карты их города и тропинкам составить возможный план, как им лучше распределить проекты между собой.

Формат входных данных
На первой строке подаются два числа N, M (1 <= N,M <= 100) – количество домов и тропинок между ними соответственно.
Далее на M строках подаются дорожки в виде номеров домов (если существует дорога 1-2, то значит существует дорожка и 2-1).
Формат выходных данных
Выведите на первой строке количество учеников, которые делают проект в одиночку.
На второй – количество групп учеников, делающих проект в паре.
На третьей – количество групп учеников, делающих проект втроём.

Примечание: ребята стараются разбиться на группы по максимуму человек (по 3), если остался кто-то один, но он мог делать проект не один, то стараемся минимизировать одиночек.

Алгоритмы на графах Поиск компонент связности Применение обхода в глубину

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

Детский праздник#55065

Организаторы детского праздника планируют надуть для него M воздушных шариков. С этой целью они пригласили N добровольных помощников, i-й среди которых надувает шарик за Ti минут, однако каждый раз после надувания Zi шариков устает и отдыхает Yi минут. Теперь организаторы праздника хотят узнать, через какое время будут надуты все шарики при наиболее оптимальной работе помощников, и сколько шариков надует каждый из них. (Если помощник надул шарик, и должен отдохнуть, но больше шариков ему надувать не придется, то считается, что он закончил работу сразу после окончания надувания последнего шарика, а не после отдыха).

Входные данные
В первой строке входных данных задаются числа M и N (0 <= M <= 15000, 1 <= N <= 1000). Следующие N строк содержат по три целых числа - T_i, Z_i и Y_i соответственно (1 <= T_i, Y_i <= 100, 1 <= Z_i <= 1000).

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

Бинарный поиск по ответу Задачи на моделирование Сканирующая прямая

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

Пазл#48921

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

Школьники Алиса и Ибрагим — лучшие друзья. У Ибрагима скоро день рождения, и по этому поводу Алиса решила подарить ему новый пазл. Пазл можно представить в виде матрицы из \(2\) строк и \(n\) столбцов, каждый элемент которой \(0\) или \(1\). За один ход можно поменять местами два элемента, стоящие в соседних клетках.

Более формально, будем считать, что строки матриц пронумерованы сверху вниз от \(1\) до \(2\), а столбцы — слева направо от \(1\) до \(n\). Обозначим клетку на пересечении строки \(x\) и столбца \(y\) за \((x, y)\). Будем считать две клетки \((x_1, y_1)\) и \((x_2, y_2)\) соседними, если \(|x_1 - x_2| + |y_1 - y_2| = 1\).

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

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

Формат входных данных
В первой строке вводится одно целое число \(n\) (\(1 \leq n \leq 200\,000\)) — количество столбцов в пазле.

Следующие две строки описывают рисунок, образованный пазлом в данный момент. В каждой строке вводятся \(n\) целых чисел, каждое из которых равно \(0\) или \(1\).

Следующие две строки описывают желаемый рисунок Алисы в том же формате.

Формат выходных данных
Если Алиса не ошиблась и её рисунок можно получить, найдите и выведите минимальное необходимое количество ходов, иначе выведите \(-1\).

В первом примере из условия подойдет следующая последовательность обменов:

\((2, 1), (1, 1)\)

\((1, 2), (1, 3)\)

\((2, 2), (2, 3)\)

\((1, 4), (1, 5)\)

\((2, 5), (2, 4)\)

Можно показать, что меньшим числом обменов обойтись нельзя, поэтому ответ равен \(5\).

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

Динамическое программирование Жадный алгоритм Паросочетания

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

Транзитный путь#38585

Вам дано дерево с N вершинами. Здесь дерево - это разновидность графа, а точнее, связный неориентированный граф с N−1 ребром, где N - количество его вершин. I-е ребро (\(1<=i<=N-1\)) соединяет вершины a_i и b_i и имеет длину c_i.
Вам также дано Q запросов и целое число K. Для каждого j-го запроса (\(1<=j<=Q\)) найдите длину кратчайшего пути от вершины x_j к вершине y_j через вершину K.

Входные данные
В первой строке записано целое число N (\(3<=N<=10^5\)). В следующих N строках записаны вершины a_i и b_i (\(1<=a_i,b_i<=N\), \(1<=i<=N-1\)) и длина между ними c_i(\(1<=c_i<=10^9\), \(1<=i<=N-1\))
Далее идут два числа Q и K (\(1<=Q<=10^5\), \(1<=K<=N\)). В последних Q строках записаны целые числа x_j, y_j(\(x_j \neq y_j\),\(x_j \neq K\), \(y_j \neq K\) \(1<=j<=Q\), ).
Заданный граф является деревом.

Выходные данные
Выведите ответы на запросы в Q строках. В j-й строке выведите ответ на j-й запрос.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 1 2 1 1 3 1 2 4 1 3 5 1 3 1 2 4 2 3 4 5	3 2 4	Кратчайшие пути для трех запросов следующие: Запрос 1: Вершина 2 → Вершина 1 → Вершина 2 → Вершина 4: Длина 1 + 1 + 1 = 3 Запрос 2: Вершина 2 → Вершина 1 → Вершина 3: Длина 1 + 1 = 2 Запрос 3: Вершина 4 → Вершина 2 → Вершина 1 → Вершина 3 → Вершина 5: Длина 1 + 1 + 1 + 1 = 4
2	7 1 2 1 1 3 3 1 4 5 1 5 7 1 6 9 1 7 11 3 2 1 3 4 5 6 7	5 14 22	Путь для каждого запроса должен проходить через вершину K = 2.
3	10 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 5 6 1000000000 6 7 1000000000 7 8 1000000000 8 9 1000000000 9 10 1000000000 1 1 9 10	17000000000

Алгоритмы на графах Кратчайшие пути в графе Обход в ширину

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

Автобусы#38571

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

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

Автобусная сеть страны охватывает N городов, занумерованных целыми числами от 1 до N.

Идеальное расписание содержит M ежедневных рейсов, i-й рейс начинается в городе F_i в момент времени X_i и заканчивается в некотором другом городе G_i в момент времени Y_i. Продолжительность каждого рейса ненулевая и строго меньше 24 часов. Рейс i выполняется одним из автобусов, находящихся в момент времени X_i в городе Fi.

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

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

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

Входные данные
В первой строке задаются целые числа N и М (1 ≤ N, M ≤ 100 000) — количество городов и рейсов автобусов соответственно.

В каждой из следующих M строк содержится описание рейса автобуса: номер города отправления F_i, время отправления X_i, номер города назначения G_i (Fi ≠ Gi), время прибытия Y_i, отделенные друг от друга одним пробелом. Время прибытия и отправления задается в формате HH:MM, где HH — часы от 00 до 23, MM — минуты от 00 до 59.

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

Примеры

№	Входные данные	Выходные данные
1	4 6 1 10:00 2 12:00 1 10:00 3 09:00 3 12:00 4 23:00 2 11:00 4 13:00 4 12:00 1 11:00 4 12:00 1 10:30	8

Жадный алгоритм Сканирующая прямая Сортировка подсчетом

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

Целые точки#38432

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

Формат входных данных
В первой строке содержится N (3 ≤N ≤1000) – число вершин многоугольника. В последующих N строках идут координаты (X_i, Y_i) вершин многоугольника в порядке обхода по часовой стрелке. X_i и Y_i - целые числа, по модулю не превосходящие 1000000.

Формат выходных данных
Вывести одно число – искомое число точек.

Примеры

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

Многоугольники. Выпуклые оболочки НОД и алгоритм Евклида Элементарная геометрия

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

Файловый менеджер#33310

Петя работает над очень большим проектом. Проект содержит N файлов. В процессе работы Пете часто приходится просматривать и редактировать файлы. Для ускорения работы Петя использует файловый менеджер Fur Manager, который отображает список имен файлов проекта в некотором порядке.

В текущей версии Fur Manager’a для перемещения по списку имен файлов есть следующие возможности:

можно нажать клавишу вниз, при этом курсор перемещается на следующий файл в списке, для последнего файла следующим считается первый;

можно нажать клавишу вверх, при этом курсор перемещается на предыдущий файл в списке, для первого файла предыдущим считается последний;

можно нажать клавишу Alt и, удерживая ее, набрать последовательность латинских букв. После этого клавишу Alt следует отпустить, и в этот момент курсор переместится на ближайший файл, имя которого начинается c заданной последовательности символов. Ближайший файл — это файл, на который можно переместиться за наименьшее количество нажатий клавиши вниз. Если заданная последовательность является началом имени текущего файла, или файла, имя которого начинается с этой последовательности, не существует, то курсор останется на месте.

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

Файлы пронумерованы от 1 до N в порядке их следования. После загрузки Fur Manager’а курсор находится на первом файле.

Петя знает, что ему сначала придется редактировать файл с номером a₁, затем с номером a₂ и так далее, а последним — файл с номером a_k. В последовательности a₁, a₂, ..., a_k один и тот же номер может встречаться несколько раз. При каждом перемещении от одного файла к другому Петя хочет нажимать как можно меньше клавиш.

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

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

В первой строке входных данных содержится целое число N (1 ≤ N ≤ 1000) — количество файлов в проекте.

В следующих N строках записаны имена файлов, по одному в каждой строке. Файлы перечислены в том порядке, в котором они отображаются файловым менеджером. Имена состоят только из строчных латинских букв. Длина каждого имени не превосходит 2000 символов. Все имена файлов различны.

Далее в следующей строке записано целое число k (1 ≤ k ≤ 10).

Последняя строка входных данных содержит k целых чисел a₁, a₂, ..., a_k (1 ≤ a_i ≤ N) — номера редактируемых файлов. Редактирование файлов выполняется в том порядке, в котором они встречаются в последовательности a₁, a₂, ..., a_k.

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

Выведите описание искомой последовательности нажатий клавиш в виде k блоков информации:

первый блок информации описывает перемещение от файла с номером 1 к файлу с номером a₁;

второй блок информации описывает перемещение от файла с номером a1 к файлу с номером a₂;

…

k-ый блок информации описывает перемещение от файла с номером a_k–1 к файлу с номером a_k.

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

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

Следующие L строк блока описывают нажимаемые клавиши. Каждая из строк содержит описание одной клавиши:

если нажимается клавиша вниз, то в строке записывается слово down;

если нажимается клавиша вверх, то в строке записывается слово up;

если нажимается клавиша Alt, то в строке записывается слово Alt;

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

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

Ввод	Вывод
6 a b c d e f 4 4 3 1 6	2 Alt d 1 up 2 Alt a 1 up

Алгоритм Дейкстры Быстрая сортировка Способы задания графа

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

Банды Фомина №2#30699

Банда Фомина состоит из n групп, в каждой из которых a_i человек. Планируется провести q рейдов. В i-ом рейде будет участвовать ровно один разбойник из каждой группы, номер которой лежит в отрезке \([l_i, r_i]\).

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

Входные данные
В первой строке дано число n (\(1 <= n <= 10^5\)) – количество групп в банде Фомина.
Во второй строке дано n натуральных чисел a_i (\(1 <= a_i <= 10^6\)) – количество человек в i-ой группе.
В третьей строке дано число q – количество рейдов.
Далее дано q строк, в каждой из которых дано два числа – l_i и r_i (\(1 <= l_i <= r_i <= n\)) – номера групп, участвующих в i-ом рейде.

Выходные данные
Выведите q чисел, каждое в отдельной строке – ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	6 1 3 7 1 4 100 3 1 3 3 4 2 6	21 7 8400

Быстрое возведение в степень Малая теорема Ферма Остатки Префиксные суммы(минимумы, ...)

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

Boolean Satisfiability#27116

Boolean satisfiability problem (SAT) is known to be a very hard problem in computer science. In this problem you are given a Boolean formula, and you need to find out if the variables of a given formula can be consistently replaced by the values true or false in such a way that the formula evaluates to true. SAT is known to be NP-complete problem. Moreover, it is NP-complete even in case of 3-CNF formula (3-SAT). However, for example, SAT problem for 2-CNF formulae (2-SAT) is in P.

#SAT is the extension of SAT problem. In this problem you need to check if it is possible, and count the number of ways to assign values to variables. This problem is known to be #P-complete even for 2-CNF formulae. We ask you to solve #1-DNF-SAT, which is #SAT problem for 1-DNF formulae.
You are given a Boolean formula in 1-DNF form. It means that it is a disjunction (logical or) of one or more clauses, each clause is exactly one literal, each literal is either variable or its negation (logical not). Formally:

Your task is to find the number of ways to replace all variables with values true and false (all occurrences of the same variable should be replaced with same value), such that the formula evaluates to true.

Input
The only line of the input file contains a logical formula in 1-DNF form (not longer than 1000 symbols). Logical operations are represented by ‘|’ (disjunction) and ‘~’ (negation). The variables are ‘A’ . . . ‘Z’ and ‘a’ . . . ‘z’ (uppercase and lowercase letters are different variables). The formula contains neither spaces nor other characters not mentioned in the grammar.

Output
Output a single integer — the answer for #SAT problem for the given formula

Input	Output
a	1
B\|~B	2
c\|~C	3
i\|c\|p\|c	7

Алгоритмы на графах Комбинаторика Конструктив

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

Мишина машина (В', В)#23371

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

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

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

Помогите Мише найти самый выгодный маршрут.

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

В первой строке содержатся два целых числа n и m количество городов и дорог соединяющих города в стране соответственно (1 <= n <= 10⁵, 0<= m <= 10⁵)

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

Гарантируется, что никакая дорога не соединяет город с самим собой и что нет двух дорог соединяющих одинаковые пары городов. Вершины нумеруются с единицы.

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

Выведите одно число максимальное количество монет которое Миша сможет получить.

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

Замечание

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

Кратчайшие пути в графе Обход в ширину Способы задания графа

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

Число способов#22015

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

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

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

Посчитайте, сколько есть способов у игрока попасть в правую

нижнюю клетку.

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

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

1<=M<=10).

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

В выходной файл запишите искомое число способов.

Примечание

При указанных ограничениях, число способов входит в тип Longint.

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

2 3

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

Пояснение

Если у нас есть таблица из 2 строк и 3 столбцов, то существуют следующие

способы попасть из левого верхнего угла в правый нижний:

1) вниз, вправо, вправо

2) вправо, вниз, вправо

3) вправо, вправо, вниз

Еще один пример входного файла

3 3

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

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

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

Ищем даты#67734

В заданном тексте, состоящем не более чем из 100 строк, найдите все даты в формате DD-MM-YYYY. Выведите эти даты в столбик в порядке их встречаемости в тексте. Валидность даты проверять не нужно.

Формат даты: DD-MM-YYYY, где:

DD - день (две цифры, 01-31)
MM - месяц (две цифры, 01-12)
YYYY - год (четыре цифры, обычно 0000-9999)
Разделитель: дефис "-"

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

Формат выходных данных
Выведите все искомые даты, каждая дата в отдельной строке.

Конечные автоматы Поиск подстроки в строке Строки

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

Шоколадная мудрость#60947

Шоколад помогает развивать ум и укреплять дух! Старец Летовец после своих занятий угощает своих учеников шоколадом. На следующем занятии у него будет M учеников и каждому из них Старец хочет дать по одной плитке шоколада.

Чтобы купить нужное количество шоколада, старец отправил своего праправнука Летовёнка разузнать, какое минимальное количество денег ему понадобится.
Оказывается, каждый магазин продаёт шоколад по разной цене. В i-м магазине можно купить не более B_i плиток шоколада по цене А_i рублей за плитку. Летовец хочет потратить как можно меньше денег, но при этом купить ровно M плиток шоколада.

Помогите Летовёнку посчитать какую минимульную сумму на шоколад потратит старец Летовец.

Формат входных данных
В первой строке заданы два числа: N и M (1 <= N, M <= 10⁵). Следующие N строк содержат по 2 числа: A_i (1 <= A_i<= 10⁹) и B_i (1 <= В_i <= 10⁵). \(B_1 + B_2 +... + B_N >= M\).

Формат выходных данных
Выведите минимальную сумму денег, необходимую для покупки M плиток шоколада.

Примеры

№	Входные данные	Выходные данные
1	2 5 4 9 2 4	12
2	4 30 6 18 2 5 3 10 7 9	130
3	1 100000 1000000000 100000	100000000000000

Алгоритмы сортировки Использование сортировки

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

Летовецкие числа#60944

Летовецкие числа — это положительные целые числа, которые делятся на a, b или c.

Напишите программу, которая находит n-е по счёту летовецкое число.

Формат входных чисел
Программа получает на вход четыре целых положительных числа n, a, b, и c. Каждое число записано в отдельной строке.
Ограничения на входные данные

1 <= n, a, b, c <= 10⁹
1 <= a * b * c <= 10¹⁸
Гарантируется, что результат находится в диапазоне [1, 2 * 10⁹].

Формат выходных чисел
Ваша программа должны вывести одное число - n-е по счёту летовецкое число.

Бинарный поиск по ответу Остатки теория чисел

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

Input	Output
a	1
B\|~B	2
c\|~C	3
i\|c\|p\|c	7