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

Кластеры роботов - 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средняяВойти и решать

Возрастающие пути#44510

Дано дерево на n вершинах (связный неориентированный ациклический граф c n−1 рёбрами), где у каждого ребра есть вес w. Назовём простой путь длины k возрастающим , если существует такое целое x>=2, что вес первого ребра пути делится на x, второго ребра — делится на x², ……, вес k-го ребра делится на x^k.

Требуется найти максимальную длину k возрастающего пути, где k — количество рёбер в нём.

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

В первой строке вводится единственное целое число n (1 <= n <= 100000) - число вершин в дереве.

В следующих n−1 строках вводятся по три целых числа u, v, w ( 1<= v <= n, 1<= w <= n, u ≠ v, 1 <= w <= 10⁷) - номера вершин, которые соединяет очередное ребро, и его вес.

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

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

Примечание

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

В 1-м примере есть путь длины 2: 3 — 1 — 2. Тогда для него подходящий x = 2. Можно показать, что возрастающего пути большей длины не существует.

Во 2-м примере есть путь длины 3: 3 — 4 — 5 — 6. Тогда для него подходящий x = 2. Можно показать, что возрастающего пути большей длины не существует.

Примеры

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

Алгоритмы на графах Арифметические алгоритмы (Теория чисел)Обход в глубину Применение обхода в глубину

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

Мишины кубики#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средняяВойти и решать

Выборы#21952

Скоро в Соединенных Штатах Берляндии пройдут выборы президента. На эту ответственную должность претендуют два кандидата: Дядя Сэм и Дядя Фродо. Вы работаете аналитиком в пред- выборном штабе Дяди Сэма, и вам поручено помочь ему победить конкурента. Раздуть газетный скандал из одержимости оппонента бросанием колец в жерла вулканов не получилось, так что при- дётся воспользоваться математикой.

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

Как вы знаете, Соединенные Штаты Берляндии разделены на несколько административных ре- гионов первого уровня — штатов. Сначала в каждом из штатов проходят местные выборы, по итогам которых каждый штат отдаёт свой голос за одного из кандидатов. Если не менее половины штатов выбрало Дядю Сэма, то выигрывает он (в случае равенства голосов Дядя Сэм имеет преимущество как действующий президент), иначе побеждает Дядя Фродо. Все штаты, в свою очередь, состоят из административных регионов второго уровня, каждый из которых представлен выборщиком из административных регионов третьего уровня и так далее. Последний уровень состоит из отдельных жителей Берляндии. Всего в Берляндии N жителей и K уровней административных единиц. Одним из ключевых принципов этой страны является равенство, так что любой регион i-го уровня делится на одинаковое число регионов следущего уровня (в том числе содержит одинаковое число граждан).

Так получилось, что делением на регионы поручили заняться именно вам, то есть в ваших руках назначить, на сколько именно административных единиц i-го уровня делится (i−1)-ая администра- тивная единица.

Также у вас есть сильный инструмент влияния на выбор людей — нефтяные бурли. Чтобы заста- вить одного избирателя отдать свой голос за Дядю Сэма, достаточно дать ему скромный подарок в размере одного нефтяного бурля.

К несчастью, изначально все N жителей Соединённых Штатов Берляндии собираются отдать свой голос за Дядю Фродо. Требуется определить минимальное количество нефтяных бурлей, ко- торое достаточно потратить для победы на выборах.

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

В единственной строке ввода находятся два целых числа N и K (1 <= N <= 10¹⁵ , 1 <= K <= 10).

Формат выходных данных
Требуется вывести единственное число — минимальное количество нефтяных бурлей, которое придётся потратить на предвыборные подарки при наилучшем разбиении на регионы.

Примеры

Ввод	Вывод
9 2	4
12 3	2

Замечание
Берляндские законы не запрещают, чтобы страна состояла из одного штата, а город — одного жителя. Аналогично с остальными типами регионов.

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

Алгоритмы на графах Динамическое программирование Динамическое программирование: один параметр Простые числа и разложение на множители

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

Why Did the Cow Cross the Road III#90425

Фермер Джон на старости лет стал параноиком. Он построил огромную изгородь вокруг фермы для защиты своих коров. Коровам такая идея не понравилась.

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

Для каждой из $N$ коров, посещающих ферму, вам сообщается время, когда она прибывает к воротам и количество времени, которое её требуется для ответов на вопросы. В каждый момент времени только одна корова опрашивается, поэтому, если много коров прибывает примерно в одно и то же время, они должны ждать своей очереди отвечать на вопросы. Например, если корова прибыла во время 5 и отвечает на вопросы 7 единиц времени, то другая корова, прибывшая во время 8 должна подождать до времени 12, что начать отвечать на вопросы.

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

ФОРМАТ ВВОДА (файл cowqueue.in):

Первая строка ввода содержит $N$, положительное целое число, не более 100. Каждая из последующих $N$ строк описывает одну корову, задавая время прибытия и время, которое требуется ей для ответов на вопросы. Каждое из этих чисел - положительное целое число не более 1,000,000.

ФОРМАТ ВЫВОДА (файл cowqueue.out):

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

Жадный алгоритм Задачи на моделирование Использование сортировки

—Войти и решать

Angry Cows#90387

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

Имеется $N$ стогов сена расположенных в целочисленных позициях $x_1, x_2, \ldots, x_N$ на числовой прямой. Если корова приземляется с энергией $R$ в позиции $x$, это вызывает взрыв "радиуса $R$", разрушающий все стоги сена в диапазоне $x-R \ldots x+R$.

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

ФОРМАТ ВВОДА (файл angry.in):

Первая строка ввода содержит $N$ ($1 \leq N \leq 50,000$) и $K$ ($1 \leq K \leq 10$). Каждая из оставшихся $N$ строк содержит целые числа $x_1 \ldots x_N$ (каждое в интервале $0 \ldots 1,000,000,000$).

ФОРМАТ ВЫВОДА (файл angry.out):

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

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

—Войти и решать

High Card Wins#90349

Корова Беси - фанат карточных игр. Однако у неё нет достойных противников. Все они играют в полностью предсказуемой манере. Однако надо ещё придумать, как выиграть у них.

Беси и Эльза играют в простую карточную игру, в которой имеется колода из $2N$ карт, последовательно пронумерованных $1 \ldots 2N$. Они делят её поровну - $N$ карт Беси и $N$ карт Эльзе. Затем они играют $N$ раундов, в каждом из которых Беси и Эльза выкладывают по одной карте, и тот, у кого карта больше, зарабатывает очко.

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

ФОРМАТ ВВОДА (файл highcard.in):

Первая строка ввода содержит значение N ($1 \leq N \leq 50,000$).

Следующие N строк содержат карты, которыми будет играть в каждом из последующих раундов игры. Заметим, что из этой информации легко определить карты, которые на руках у Беси.

ФОРМАТ ВЫВОДА (файл highcard.out):

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

Жадный алгоритм Задачи на моделирование Использование сортировки

—Войти и решать

Train Scheduling#90195

**Замечание: Ограничение по памяти для этой задачи 512MB, в два раза больше значения по умолчанию.**

Беси приняли на новую работу - диспетчером поездов. Имеется две железнодорожные станции $A$ и $B$. В связи с ограничением бюджета, эти станции соединены только одной дорогой. Если поезд отправляется от одной станции в момент времени $t$, тогда он прибудет на другую станцию в момент времени $t+T$ ($1\le T\le 10^{12}$).

Имеется $N$ ($1\le N\le 5000$) поездов для которых нужно установить время отправки. $i$-ый поезд должен покинуть станцию $s_i$ в момент времени $t_i или позже ($s_i\in \{A, B\}, 0\le t_i\le 10^{12}$). Запрещено иметь поезда, которые движутся в противоположных направлениях в один и тот же момент времени (поскольку они столкнутся). Однако разрешено иметь множество поездов, которые еду в одном направлении в одно и то же время (предполагаем, что поезда имеют пренебрежимо малые размеры)

Помогите Беси спланрировать времена отправления так, чтобы не было столкновений, а общая задержка была минимальной. Если поезд спланирован на убытие в момент времени $a_i\ge t_i$, общая задержка определяется как $\sum_{i=1}^N(a_i-t_i)$.

ФОРМАТ ВВОДА (с клавиатуры):

Первая строка содержит $N$ и $T$.

Затем следуют $N$ строк, где i-ая строка содержит станции $s_i$ и время $t_i$, соответствующие $i$-ому поезду.

ФОРМАТ ВЫВОДА (на экран):

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

Жадный алгоритм Задачи на моделирование Теория расписаний

—Войти и решать

Icy Perimeter#90070

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

Конфигурация мороженого, которое производится машиной, может быть описано решёткой $N \times N$ grid ($1 \leq N \leq 1000$):

##....
....#.
.#..#.
.#####
...###
....##

Каждый символ '.' представляет пустое место, а каждый символ '#' представляет $1 \times 1$ квадратную ячейку мороженого.

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

ФД хочет найти площадь и периметр сгустка, который имеет наибольшую площадь. Площадь сгустка равна количеству символов '#' в его картинке. Если несколько сгустков имеют одинаковую площадь, он хочет знать минимальный периметр из них. На рисунке выше, маленький сгусток имеет площадь 2 и периметр 6, а больший сгусток имеет площадь 13 и периметр 22.

Заметим, что сгусток может иметь "дыру" внутри (пустое пространство, окружённое мороженым). В таком случае граница "дыры" также учитывается в периметре сгустка. Сгусток может находиться внутри другого сгустка, в этом случае они рассматриваются как независимые сгустки. Например, ниже представлен сгусток площади 1 внутри сгустка площади 16:

#####
#...#
#.#.#
#...#
#####

ФОРМАТ ВВОДА (файл perimeter.in):

Первая строка ввода содержит $N$, а следующие $N$ строк описывают вывод машины. Присутствует, как минимум, один символ '#'.

ФОРМАТ ВЫВОДА (файл perimeter.out):

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

Задачи на моделирование Клеточная геометрия Поиск компонент связности

—Войти и решать

Rental Service#90023

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

У ФД есть $N$ коров ($1 \leq N \leq 100,000$), каждая способна производить некоторое количество молока каждый день. $M$ магазинов ($1 \leq M \leq 100,000$) недалеко от фермы Джона покупают определённое количество молока, каждый по своей цене. Более того, $R$ ($1 \leq R \leq 100,000$) соседних фермеров заинтересованы в аренде коров по некоторой цене.

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

ФОРМАТ ВВОДА (файл rental.in):

Первая строка ввода содержит $N$, $M$, $R$. Каждая из следующих $N$ строк содержит целое число $c_i$ ($1 \leq c_i \leq 1,000,000$), указывающее, что $i$-ая корова ФД может произвести $c_i$ галлонов молока в день. Каждая из $M$ строк содержит два целых числа $q_i$ и $p_i$ ($1 \leq q_i, p_i \leq 1,000,000$), которые обозначают, что $i$-ый магазин готов купить $q_i$ галлонов молока по $p_i$ центов за галлон. Имейте ввиду, что ФД может продавать любое количество молока от 0 до $q_i$ галлонов в этот магазин. Каждая из следующих $R$ строк содержит целое число $r_i$ ($1 \leq r_i \leq 1,000,000$), означающее, что один из соседей ФД хочет арендовать корову за $r_i$ центов в день.

ФОРМАТ ВЫВОДА (файл rental.out):

Вывод должен содержать одну строку - максимальную прибыль ФД, которую он может получить за один день, доя или сдавая в аренду каждую из своих коров. Заметим, что ответ может оказаться большим, чтобы поместиться в 32-битное целое, поэтому Вы должны использовать тип как "long long" в C/C++.

Жадный алгоритм Задачи на моделирование Использование сортировки

—Войти и решать

Convention#89997

На ферме Джона состоится съезд по поеданию травы.

Коровы со всего мира прибывают в местный аэропорт, чтобы посетить съезд и поесть траву. А именно $N$ ($1 \leq N \leq 10^5$) коров прибывают в аэропорт, и корова $i$ прибывает в момент времени $t_i$ ($0 \leq t_i \leq 10^9$). ФД организовал $M$ ($1 \leq M \leq 10^5$) автобусов для транспортировки коров из аэропорта. Каждый автобус может вместить до $C$ ($1 \leq C \leq N$) коров. ФД ждёт вместе с автобусами в аэропорту и собирается распределить прибывающих коров по автобусам. Автобус убывает из аэропорта в момент, когда прибывает последняя корова. ФД хочет, чтобы прибывающие коровы не ждали в аэропорту слишком долго. Каково наименьшее значение максимального времени ожидания из всех коров, если ФД оптимально назначит их по автобусам. Время ожидания коровы есть разность между временем её прибытия и временем отправления автобуса, в который она распределена.

Гарантируется, что $MC \geq N$.

ФОРМАТ ВВОДА (файл convention.in):

Первая строка содержит три разделённых одиночными пробелами целых числа $N$, $M$, $C$. Следующая строка содержит $N$ разделённых одиночными пробелами целых чисел, представляющих время прибытия каждой коровы.

ФОРМАТ ВЫВОДА (файл convention.out):

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

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

—Войти и решать

Tractor#89878

Одно из полей Фермера Джона весьма холмисто. И он хочет купить новый трактор для работы на этом поле. Поле описывается решеткой из N x N (1 <= N <= 500) неотрицательных целых высот ячеек. Трактор может перемещаться из ячейки в соседнюю (на один шаг на север, юг, запад или восток), с разницей их высот D ровно за D единиц денег.
ФД хочет заплатить достаточно, так чтобы его трактор, начиная с некоторой ячейки поля мог посетить как минимум половину ячеек поля. Если число ячеек в поле - нечетное, то половина, округленная вверх.
Определите минимальную стоимость покупки трактора способного выполнить эту задачу.

PROBLEM NAME: tractor
Формат входных данных
* Строка 1: Значение N.
* Строки 2..1+N: Каждая строка содержит N разделенных одиночными пробелами неотрицательных целых чисел (каждое не более миллиона), определяющих строку поля ФД.
Формат выходных данных
* Line 1: Минимальная стоимость трактора, который способен объехать не менее половины этого поля.
Примечание
Трактор стоимостью 3 способен перемещаться из ячейки с высотой 0 в ячейку с высотой 3. Поэтому он может посетить все ячейки с высотами 0 и 3. Вместе они представляют не менее половины фермы.

Бинарный поиск по ответу Обход в ширину Поиск компонент связности

—Войти и решать

65817#65817

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

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

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

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

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

Гигантский дракон#60878

Канеки смотрит на неориентированный граф на плоскости из $n$ вершин и $m$ ребер. В этом графе ему интересно найти самого большого дракона.

Назовем сегментом дракона три ребра графа $AL$, $AB$ и $AR$, имеющие общую вершину $A$, и обладающие следующими свойствами:

$0 < \measuredangle (BAL) < 45^\circ$ и направление поворота от $\overrightarrow{AB}$ к $\overrightarrow{AL}$ — по часовой стрелке;
$0 < \measuredangle (BAR) < 45^\circ$ и направление поворота от $\overrightarrow{AB}$ к $\overrightarrow{AR}$ — против часовой стрелки;
$|AB| \geqslant |AL|$ и $|AB| \geqslant |AR|$, то есть $AB$ — максимальное по длине из трех ребер.

При выполнении всех указанных условий вершины $A$ и $B$ называются началом и концом сегмента, а ребра $AL$, $AB$ и $AR$ — левой лапой, основанием и правой лапой сегмента, соответственно.

Определим дракона как последовательность сегментов, в которой

начало первого сегмента $A_1$, также называемое головой дракона, находится в вершине $S$;
$A_{i} = B_{i-1}$ для всех $i > 1$, то есть начало каждого следующего сегмента совпадает с концом предыдущего;
$\left|\measuredangle \left(\overrightarrow{A_{i-1} B_{i-1}}, \overrightarrow{A_i B_i}\right)\right| < 45^\circ$, то есть угол между векторами оснований соседних сегментов строго меньше $45^\circ$;
$\left|\measuredangle \left(\overrightarrow{A_1 A_i}, \overrightarrow{A_i B_i}\right)\right| < 45^\circ$, то есть угол между вектором от головы дракона $A_1$ до начала сегмента и основанием сегмента строго меньше $45^\circ$.

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

Мощностью дракона будем считать сумму квадратов длин оснований его сегментов, то есть $\sum |A_i B_i|^2$. В заданном графе помогите Канеки найти дракона максимальной мощности с головой в вершине $S$.

Формат входных данных
В первой строке входных данных даны три числа $n, m, S$ ($2 \leqslant n \leqslant 2\cdot 10^5$; $1 \leqslant m \leqslant 4\cdot 10^5$; $1 \leqslant S \leqslant n$) — количество вершин и ребер в заданном графе и номер вершины, являющейся головой дракона.

В следующих $n$ строках дано описание вершин графа. Каждая строка содержит два целых числа $x_i$ и $y_i$ — координаты $i$-й вершины ($0 \leqslant x_i, y_i \leqslant 10^9$). Гарантируется, что все вершины графа различны, то есть не существует двух вершин, обе координаты которых совпадают.

Далее следует пустая строка.

В следующих $m$ строках дано описание ребер графа. Каждая строка содержит два целых числа $u_i$ и $v_i$ — номера вершин, соединенных $i$-м ребром ($1 \leqslant u_i, v_i \leqslant n$; $u_i \neq v_i$). Гарантируется, что граф не содержит кратных ребер.

Формат выходных данных
В первой строке выходных данных выведите два числа $k$ и $ans$ — количество сегментов в драконе, имеющем максимальную мощность, и само значение его мощности.

В следующих $k$ строках выведите описание сегментов в том порядке, в котором они образуют дракона. В качестве описания сегмента $i$ выведите номера вершин $L_i$, $B_i$ и $R_i$.

Будем считать, что дракон может состоять только из вершины $S$. В таком случае количество сегментов и его мощность следует считать нулями.

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

В первом тесте в качестве максимального дракона можно взять весь граф целиком;
Во втором тесте ни одна тройка ребер не может быть взята в сегмент, так как не выполняется одно из обязательных условий;
В третьем тесте максимальный дракон состоит из двух сегментов с основаниями $9 \to 5$ и $5 \to 1$ с лапами $(9 \to 8, 9 \to 7)$ и $(5 \to 3, 5 \to 2$).

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

✓ 1✗ 0—Войти и решать

Левый лабиринт#55694

В спортзале размером NxM метров построили современный аттракцион под названием "Левый лабиринт". Для этого на полу спортзала с интервалом в 1 метр начертили линии, параллельные стенам спортзала. Таким образом, спортзал разбили на NxM клеток. Дальше некоторые из этих клеток покрасили в черный цвет.

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

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

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

Входные данные
Во входном файле сначала записано число K — количество разрешенных поворотов направо (целое число из диапазона от 0 до 5), затем записаны числа N и M, задающие размеры спортзала — натуральные числа, не превышающие 20. Далее записано N строк по M чисел в каждой. Число 0 обозначает непокрашенную клетку, число 1 — покрашенную, число 2 — клетку, откуда стартует участник и число 3 — клетку, куда нужно добежать (клетки, помеченные 2 и 3 являются непокрашенными). В лабиринте всегда есть ровно одна начальная клетка и ровно одна клетка, в которую нужно попасть.

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

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

✓ 2✗ 3—Войти и решать

Трехцветные таблицы#55402

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

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

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

Входные данные
Вводятся числа N и M — количество строк и столбцов таблицы (1≤N≤30, 1≤M≤30). Далее записано N строк по M чисел в каждой, задающие цвета, в которые должны быть окрашены клетки:

0 — клетка может в итоге быть любого цвета

1 — клетка должна быть синей

2 — клетка должна быть желтой

3 — клетка должна быть зеленой

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

Обход в глубину Обход в ширину Способы задания графа

✓ 1✗ 6—Войти и решать