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

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

Олег и двоичные последовательности#30708

Олег очень любит двоичные последовательности — последовательности из нулей и единиц. Совсем недавно он написал в тетради очередную двоичную последовательность из n элементов.
Для выписанной последовательности Олег посчитал Z-функцию.

Z-функцией последовательности s₁, . . . , s_n называется массив z[1..n], в котором:

• z[1] = 0;
• Если i > 1, то z[i] равно длине наибольшего общего префикса последовательности s и суффикса последовательности s, начинающегося с i-й позиции. Иначе говоря, z[i] равно максимальному k, такому что s₁ = s_i , s₂ = s_i+1, . . . , s_k = s_i+k−1.

Например, для последовательности s = h0, 0, 1, 1, 0, 0, 1i Z-функция следующая: z = h0, 1, 0, 0, 3, 1, 0i.
Записав в тетради последовательность и ее Z-функцию, Олег лег спать. Пока он спал, его младший брат Егор прокрался в комнату и закрасил фломастером последовательность и некоторые значения Z-функции. Проснувшись, Олег заинтересовался, сколько различных двоичных последовательностей он мог вечером написать в тетради, чтобы незакрашенные значения Z-функции были правильными.

Найдите число искомых последовательностей и выведите его по модулю 10⁹ + 7. Заметьте, что Олег мог и ошибиться при вычислении Z-функции, в этом случае ни одна последовательность не подходит и ответ равен 0.
Формат входных данных
В первой строке входного файла находится целое число n — длина исходной двоичной последовательности (1 ≤ n ≤ 1000). Во второй строке входного файла находятся n целых чисел z[1], . . . , z[n], где z[i] — значение Z-функции в позиции i, или −1, если значение в i-й позиции было закрашено (−1 ≤ z[i] ≤ n).

Формат выходных данных
В выходной файл выведите единственное число — остаток от деления числа подходящих двоичных последовательностей на число 10⁹ + 7.

Ввод	Вывод
3 0 0 1	2
4 0 0 1 0	0
3 0 3 -1	0
3 -1 -1 -1	8

Пояснение
В первом примере подходят последовательности {0, 1, 0 } и { 1, 0, 1 }.
Во втором примере не существует ни одной двоичной последовательности длины 4 с заданной Z-функцией.
В третьем примере z[2] = 3, что противоречит определению Z-функции, поэтому ответ 0.
В четвертом примере подходит любая двоичная последовательность длины 3.

Обход в глубину Применение обхода в глубину Разбор случаев

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

Кладоискатель#27213

Кладоискателю Васе попалась карта древнего подземелья. Подземелье представляет собой лабиринт размера N×M (1 ≤ N, M ≤ 100 , N×M ≤ 100). Каждая клетка лабиринта либо пуста и по ней можно пройти, либо содержит стену. Из клетки можно переходить только в смежную по стене клетку (так, у каждой клетки может быть не более 4 смежных).

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

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

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

Первая строка содержит 2 числа N и M, задающие размеры лабиринта. Далее следует описание лабиринта: N строк по M символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).

В (N+2)-й строке находится число K (1 ≤ K ≤ NxM) -- количество входов в лабиринт. Далее в K строках содержатся координаты входов. Так, в i-й строке содержатся числа xi и yi, означающие,что i-й вход расположен в x_i-й строке и в y_i-м столбце (1 ≤ x_i ≤ N, 1 ≤ y_i ≤ M). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.

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

Необходимо вывести одно число - искомый номер входа (нумерация начинается с 1). Если до сокровища невозможно добраться, выведите -1.

Примеры

№	Входные данные	Выходные данные
1	5 5 00000 00000 10*00 01111 00000 4 1 1 1 5 4 1 5 5	1
2	3 3 010 1*1 010 4 1 1 1 3 3 1 3 3	-1

Алгоритм Флойда Обход в ширину

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

Есть ли цикл?#27212

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

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

В первой строке вводится число вершин N≤ 50. Далее в N строках следуют по N чисел, каждое из которых – 0 или 1. j-ое число в i-ой строке равно 1 тогда и только тогда, когда существует ребро, идущее из i-ой вершины в j-ую. Гарантируется, что на диагонали матрицы будут стоять нули.

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

Выведите 0, если в заданном графе цикла нет, и 1, если он есть.

Примеры

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

Алгоритм Флойда Обход в глубину

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

Легкая, вариант -2#24896

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

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

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

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

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

В первой строке находится натуральное число n (2 ≤ n ≤ 100) — количество сотрудников в фирме.

Следующая строка содержит n-1 натуральное число — номера непосредственных начальников сотрудников с номерами от 2 до n в соответствующем порядке. Числа отделены друг от друга одним пробелом. Гарантируется, что номер непосредственного начальника очередного сотрудника меньше номера самого сотрудника.

Следующая строка содержит одно натуральное число x (1 ≤ x ≤ n) — номер отправляемого в командировку сотрудника.

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

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

Пример входных и выходных данных

Ввод	Вывод
9 1 2 1 4 4 2 7 8 2	4

Деревья Поиск компонент связности

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

Воздушные потоки#24765

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

Представим воздушные потоки как массив h[1..n] из n натуральных чисел — высот потоков. Для каждого 1 ≤ i ≤ n посчитаем G[i] — индекс ближайшего элемента слева, строго большего h[i]. Более формально, g[i] = max{j | j < i и h[j] > h[i]}. Если i = 1 или до h[i] нет ни одного элемента больше него, то G[i] считается равным 0.

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

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

Помогите Колобку сделать оптимальное изменение, которое позволит добиться, чтобы сумма S(h), описанная выше, после проделанного действия была минимальна.

Формат входного файла
В первой строке входного файла даны числа n, m (1 ≤ n ≤ 10⁵ , 1 ≤ m ≤ 10⁹ ) — количество воздушных потоков и максимальное значение, на которое можно увеличить высоту одного из них. Во второй строке даны высоты воздушных потоков h[i] (1 ≤ h[i] ≤ 10⁹ ). Гарантируется, что все высоты — чётные числа.

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

Ввод	Вывод
3 100 4 2 6	4
3 2 4 2 6	5
3 10 2 2 2	4

Деревья Наименьший общий предок Разреженные таблицы (sparse table)Структуры данных

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

Легкая, вариант-1#24758

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

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

В первой строке находится натуральное число n (2 ≤ n ≤ 100) — количество сотрудников в фирме.

Следующая строка содержит одно натуральное число x (1 ≤ x ≤ n) — номер отправляемого в командировку сотрудника.

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

выведите одно число — количество сотрудников, отправляющихся в командировку после выполнения описанной операции.

Пример входных и выходных данных

Ввод	Вывод
9 1 2 1 4 4 2 7 8 2	5

Деревья Поиск компонент связности

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

Топологическая сортировка#24753

Дан ориентированный невзвешенный граф. Необходимо его топологически отсортировать.

Входные данные: В первой строке содержатся два натуральных числа n и m (1≤n≤10⁵, 1≤m≤10⁵) — количество вершин и рёбер в графе соответственно. Далее в m строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно (нумерация вершин начинается с 1).

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

Примеры

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

Обход в глубину Топологическая сортировка

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

Пожар в НИИЧАВО#21953

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

НИИЧАВО состоит из N кабинетов, соединённых M коридорами. Кабинеты пронумерованы це- лыми числами от 1 до N, при этом кабинет Корнеева имеет номер A, а лаборатория изучения µ-поля расположена в кабинете номер B. Благодаря специальному искажению пространства внутри инсти- тута, все коридоры имеют одинаковую длину, которую можно пройти за 1 минуту, если двигаться быстрым шагом.

Ситуация усугубляется тем, что диван-транслятор — прибор, очень чувствительный к резким пе- репадам температуры. Внутри каждого коридора НИИЧАВО поддерживается свой температурный режим. Если абсолютная величина разности температур в двух последовательных коридорах на пути из кабинета Корнеева в лабораторию окажется больше D градусов, то диван-транслятор пе- рейдёт в нестабильное состояние, что может привести к катастрофическим последствиям. Обратите внимание, что на своём пути вы не заходите в сами кабинеты, а только переходите из коридора в коридор, поэтому климат внутри кабинетов не влияет на диван-транслятор. В силу причин магиче- ского характера, войдя в коридор, вы обязаны дойти до его конца, иными словами, останавливаться или разворачиваться посреди коридора запрещено. По каждому коридору можно перемещаться в обоих направлениях.

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

Формат входных данных
В первой строке входных данных следуют три целых числа N, M и D (2 <= N <= 100 000, 1 <= M <= 200 000, 0 <= D <= 2 · 10⁸ ), обозначающие количество кабинетов, количество коридоров в НИИЧАВО и максимальный допустимый перепад температур для дивана-транслятора в граду- сах. В последующих M строках находятся описания коридоров. Каждая строка содержит по три целых числа ui , vi , ti — номера двух кабинетов, соединённых i-м коридором, и значение температуры в этом коридоре, выраженное в градусах (1 <= ui , vi <= N, −109 <= ti <= 10⁹ ). Как вы уже могли понять, НИИЧАВО — весьма необычное заведение, поэтому между двумя кабинетами может пролегать несколько коридоров, возможно с разными температурами, а некоторые коридоры могут соединять кабинет с самим собой. Гарантируется, что коридоры перечислены во входном файле в порядке неубывания ti . В следующей строке находится целое число Q (1 <= Q <= 50) — количество пар A и B, которые вам требуется обработать. В каждой из последующих Q строк находятся по два целых числа Ai , Bi , обозначающих номер кабинета Корнеева и номер кабинета, в котором расположена лаборатория (1 <= A_i , B_i <= N, A_i != B_i).

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

Примеры

Ввод	Вывод
6 9 5 6 6 -42 1 2 4 2 3 6 3 2 7 2 5 11 6 1 12 1 3 15 3 4 16 5 6 18 2 1 5 4 2	4 -1
6 9 7 6 6 -42 1 2 4 2 3 6 3 2 7 2 5 11 6 1 12 1 3 15 3 4 16 5 6 18 1 4 2	5

Замечание
Пояснение к тестам из условия. В обоих тестах план НИИЧАВО выглядит следующим образом:

Рассмотрим первый тест, в нём D = 5. В первом наборе A = 1, B = 5. В качестве воз- можного маршрута может выступить следующая последовательность переходов по коридорам:

Третьим шагом можно вернуться в кабинет 2 и по тому же коридору с t = 6 .
Во втором наборе A = 4, B = 2. Способа добраться из кабинета 4 в кабинет 2, ни разу не допустив перепад температуры больше, чем в 5 градусов, не существует.

Во втором тесте D = 7. В единственном наборе A = 4, B = 2 cтартовый и конечный кабинет те же, что и во втором наборе первого теста из условия, но допустимый перепад температур больше, благодаря чему подходит следующий маршрут:

Алгоритмы на графах Обход в ширину Структуры данных

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

План эвакуации#97010

Этаж здания представляет собой прямоугольник из $n\times m$ квадратных комнат. Из каждой комнаты есть проходы в соседние комнаты. В двух комнатах находятся лестницы. Необходимо разработать план эвакуации — указать для каждой комнаты направление движения в одну из соседних комнат так, чтобы, передвигаясь по комнатам только в указанных направлениях, можно было бы достичь одной из двух лестниц, пройдя минимальное расстояние.

На рисунке изображён возможный план эвакуации для примера из условия. Комнаты с лестницами обозначены звёздочками.

Первая строка входных данных содержит число $n$ — количество строк в плане эвакуации, $1\le n\le 100$. Вторая строка входных данных содержит число $m$ — количество столбцов в плане эвакуации, $2\le m\le 100$. Следующие две строки содержат числа $r_1$ и $c_1$ — номера строки и столбца комнаты, в которой находится первая лестница, $1\le r_1\le n$, $1\le c_1\le m$. Следующие две строки содержат числа $r_2$ и $c_2$ — номера строки и столбца комнаты, в которой находится вторая лестница, $1\le r_2\le n$, $1\le c_2\le m$. Гарантируется, что $r_1\ne r_2$ или $c_1\ne c_2$. Строки нумеруются сверху вниз числами от 1 до $n$, столбцы нумеруются слева направо числами от 1 до $m$.

Программа должна вывести $n$ строк, каждая строка должна содержать $m$ символов. Каждый символ соответствует одной комнате. В двух комнатах с лестницами должен находиться символ <<S>> (прописная английская буква). В остальных комнатах находятся символы, указывающие направление движения:

<<<>> (символ <<меньше>>) — налево.

<<>>> (символ <<больше>>) — направо.

<<^>> (символ находится на клавише <<6>>) — вверх.

<<v>> (строчная английская буква) — вниз.

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

Решения, правильно работающие, когда $n=1$, будут оцениваться в 20 баллов.

Решения, правильно работающие, когда $c_1=c_2$, будут оцениваться в 20 баллов.

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

Обход в ширину

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

B1. Мяу-мяу! - 1#91613

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

Многолетние исследования показали следующие примечательные черты Мурмурградска:

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

2. Между двумя домами есть котодорожка тогда и только тогда, когда котики в этих домах дружат.

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

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

У мэра слишком много дел, поэтому за помощью он обратился к вам! Он поставил перед вами следующую задачу: посчитать, сколько существует планов переезда, удовлетворяющих и критериям мэра, и критериям населения.

Так как это число может быть очень большим, необходимо посчитать его по модулю $998244353$.

Формат входных данных
В первой строке записано одно целое число $t$ — количество наборов входных данных. Далее следуют $t$ наборов входных данных.

Каждый набор данных состоит из нескольких строк. Первая строка набора данных содержит одно целое число $n$ — количество вершин в дереве. Далее идут $n - 1$ строк, каждая содержит два целых числа $u$ и $v$ ($1 \leq u, v \leq n$, $u \neq v$) — две вершины, которые соединены ребром.

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

Формат выходных данных
Для каждого набора входных данных выведите в отдельной строке одно целое число — количество подходящих планов переезда по модулю $998244353$.

Деревья

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

Why Did the Cow Cross the Road III#90434

Ферма Джона представляет собой квадратную решётку из $N \times N$ полей ($2 \leq N \leq 100$). Определённые пары соседних полей (север-юг или запад-восток) разделены дорогами, и высокий забор идёт вокруг периметра всей решётки, не давая коровам возможности покинуть ферму. Коровы могут свободно перемещаться с любого поля на любое соседнее поле (на сервер, юг, запад, восток), хотя они предпочитают переходить дороги только когда это абсолютно необходимо.

Имеется $K$ коров ($1 \leq K \leq 100, K \leq N^2$) на ферме, каждая расположена в различном поле. Пара коров называется "далёкой", если для того чтобы одна корова смогла посетить другую, необходимо перейти хотя бы одну дорогу. Помогите ФД посчитать количество пар удалённых коров.

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

Первая строка ввода содержит $N$, $K$, $R$. Следующие $R$ строк описывают $R$ дорог существующие между парами соседних полей. Каждая строка имеет вид $r$ $c$ $r'$ $c'$ (целые числа в интервале $1 \ldots N$), указывающих, что имеется дорога между соседними полями (строка $r$, колонка $c$ и строка $r'$, колонка $c'$). Последние $K$ строк описывают местоположение $K$ коров (строка, колонка).

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

Выведите количество пар "далёких" коров.

Поиск компонент связности

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

Why Did the Cow Cross the Road#90426

Ферма Джона представляет собой решётку из $N \times N$ квадратных полей ($3 \leq N \leq 100$), и $N-1$ дороги "север-юг" и $N-1$ дороги "запад-восток", проходящих внутри фермы и служащих разделителями между полями. Высокий забор вокруг фермы по её внешнему периметру, препятствует выходу коров за пределы фермы. Беси может свободно перемещаться с любого поля на любое соседнее поле (на север, юг, запад, восток). Ей требуется $T$ единиц времени на переход дороги ($0 \leq T \leq 1,000,000$).

Однажды ФД пригласил Беси посетить его дом поиграть в шахматы. Беси начинает с северо-западного углового поля фермы, а дом ФД находится на южно-восточном углу поля. Поскольку Беси становится голодной во время пути, она останавливается на каждом третьем поле, которое посетит, поесть траву (не включая стартовое поле, но включая возможно финальное поле, где расположен дом ФД). Некоторые поля травянистее, чем другие, поэтому количество времени, которое она потратит на еду на поле, зависит от поля, на котором она остановилась.

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

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

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

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

Выведите минимальное количество времени, которое требуется Беси чтобы добраться до дома ФД.

Алгоритм Дейкстры

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

Fenced In#90418

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

Поле представляет собой прямоугольник с угловыми вершинами в точках $(0,0)$ and $(A,B)$. ФД построил $n$ вертикальных изгородей ($0 \leq n \leq 25,000$) в различных позициях $a_1 \ldots a_n$ ($0 < a_i < A$); каждая изгородь проходит от точки $(a_i, 0)$ до точки $(a_i, B)$. Он также построил $m$ горизонтальных изгородей ($0 \leq m \leq 25,000$) в в различных позициях $b_1 \ldots b_m$ ($0 < b_i < B$); каждая изгородь, проходит из $(0, b_i)$ в $(A, b_i)$. Каждая вертикальная изгородь пересекается с каждой горизонтальной изгородью, разделив поле на $(n+1)(m+1)$ регионов.

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

Например, ФД мог построить изгороди так:

+---+--+
|   |  |
+---+--+
|   |  |  
|   |  |
+---+--+

и открыть их так:

+---+--+
|      |  
+---+  +  
|      |  
|      |
+---+--+

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

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

Первая строка ввода содержит числа $A$, $B$, $n$, and $m$ ($1 \leq A, B \leq 1,000,000,000$). Следующие $n$ строк содержат $a_1 \ldots a_n$. Следующие $m$ строк содержат $b_1 \ldots b_m$.

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

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

Минимальный каркас

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

Fenced In#90416

Поле представляет собой прямоугольник с угловыми вершинами в точках $(0,0)$ and $(A,B)$. ФД построил $n$ вертикальных изгородей ($0 \leq n \leq 2000$) в различных позициях $a_1 \ldots a_n$ ($0 < a_i < A$); каждая изгородь проходит от точки $(a_i, 0)$ до точки $(a_i, B)$. Он также построил $m$ горизонтальных изгородей ($0 \leq m \leq 2000$) в в различных позициях $b_1 \ldots b_m$ ($0 < b_i < B$); каждая изгородь, проходит из $(0, b_i)$ в $(A, b_i)$. Каждая вертикальная изгородь пересекается с каждой горизонтальной изгородью, разделив поле на $(n+1)(m+1)$ регионов.

Например, ФД мог построить изгороди так:

+---+--+
|   |  |
+---+--+
|   |  |  
|   |  |
+---+--+

и открыть их так:

+---+--+
|      |  
+---+  +  
|      |  
|      |
+---+--+

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

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

Минимальный каркас

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

Superbull#90410

Беси и её подружки участвуют в чемпионате. Всего имеется N (1 <= N <= 2000) команд. Каждой команде назначено уникальное ID в интервале 1...2^30-1. Чемпионат с выбыванием - после каждой игры ФД выбирает, какая команда выбывает из турнира, и она больше не участвует ни в каких играх. Турнир заканчивается, когда остаётся ровно одна команда.

ФД заметил необычное свойство счёта в матчах: В любой игре суммарный счёт двух команд всегда будет побитовым исключающим ИЛИ (XOR) ID этих команд. Например, если играют команды с ID 12 и 20, то 24 очка будет набрано в этой игре, поскольку 01100 XOR 10100 = 11000.

ФД верит, что чем больше очков набрано в игре, тем интереснее игра. Поэтому он хочет выбрать такую серию игр, чтобы максимизировать суммарное набранное количество очков. Помогите ФД организовать такие матчи.

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

Первая строка содержит одно целое число N. Последующие N строк содержат N ID команд.

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

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

Примечание Один способ набрать 37 таков: 3 и 9, 9 выиграла. В турнире остаются 6 9 10. Затем 6 и 9, побеждает 6. Остаются 6 и 10. Наконец 6 и 10 и 10 побеждает. Общее количество очков: (3 XOR 9) + (6 XOR 9) + (6 XOR 10) = 10 + 15 + 12 = 37. Замечание: Побитовый XOR, чато обозначаемый ^, это побитовая операция, которая выполняется независимо над каждой позицией двух двоичных представлений целых чисел. 1 в позиции получается только если в этой позиции в разных числах находятся разные значения (1 и 0 или 0 и 1). Например 10100 (десятичное 20) XOR 01100 (десятичное 12) = 11000 (десятичное 24)

Минимальный каркас

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

Cow Navigation#90394

Амбар описывается решёткой $N \times N$ ($2 \leq N \leq 20$) символов, некоторые из них пусты, некоторые заняты. Бесси начинает в левом нижнем углу (1,1) и должна пройти в правый верхний угол $N,N$. Вы можете управлять ею посредством последовательности инструкций вида "вперёд", "повернись влево на 90 градусов", "повернись вправо на 90 градусов". Вы хотите задать кратчайшую последовательность, которая приведёт ее к цели. Есл инструкицю выполнить невозможно, Бесси пропускает её и переходит к следующей инструкции.

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

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

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

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

Каждый символ или H (непроходимы стог сена) или E - пустая ячейка.

Гарантируется, что ячейки 1,1 и $N,N$ будут пустые, также гарантируется существование пути по пустым ячейкам из 1,1 в $N, N$.

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

На единственной выводной строке выведите длину кратчайшей последовательности команд, которая приведёт Бесси к цели, вне зависимости куда она смотри вначале, вверх или вправо.

ФОРМАТ ВВОДА:

3
EHE
EEE
EEE

ФОРМАТ ВЫВОДА:

В этом примере Инструкции "Вперёд, Вправо, Вперёд, Вперёд, Влево, Вперёд, Влево, Вперёд, Вперёд" приведут Бесси к назначению вне зависимости от начальной ориентации.

Problem credits: Brian Dean

Обход в ширину

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

Moocast#90367

$N$ ($1 \leq N \leq 200$) коров Фермера Джона хотят организовать безопасную сеть передачи сообщений.

Каждая корова получает "воки-токи". Каждый "воки-токи" имеет ограниченный радиус передачи: "воки-токи" с мощностью $P$ может передавать сигнал на расстояние не более $P$. Заметим, что "воки-токи" однонаправленный: чтобы получить сигнал от другого "воки-токи", нужно чтобы он имел соотвествующую мощность.К счастью, коровы могут передавать по эстафете сообщения другу другу (в том числе и чужие) и поэтому нет необходимости для каждой коровы быть способной непосредственно передать сообщение каждой другой.

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

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

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

Каждая из следующих $N$ строк содержат $x$ и $y$ координаты одной коровы ( целые числа в диапазоне $0 \ldots 25,000$) за которыми следует $p$, мощность "воки-токи" этой коровы.

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

Напишите одну строку - максимальное количество коров, которым можно передать информацию от одной коровы.

графы Поиск компонент связности

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

Moocast#90361

$N$ ($1 \leq N \leq 1000$) коров Фермера Джона хотят организовать безопасную систему для передачи важных сообщений.

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

Коровам нужно решить сколько денег необходимо потратить на "воки-токи". Если они потратят \$X, они получат "воки-токи", способно передавать на расстояние до $\sqrt{X}$. То есть, квадрат расстояния между коровами стоит не более $X$ чтобы обеспечить их коммуникацией.

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

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

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

Каждая из $N$ последующих строк содержит $x$ и $y$ координаты одной коровы. И то и другое - целое в интервале $0 \ldots 25,000$.

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

Напишите в одну строку целое $X$ - минимальное количество денег, которое коровы должны потратить на "воки-токи"

Бинарный поиск по ответу графы Поиск компонент связности

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

Lasers and Mirrors#90360

Коровы Фермера Джона любят производить лазерные шоу.

Для своего последнего шоу, они купили огромный мощный лазер - такой большой, что они не смогли перместить его легко из того места, где он был приобретен. Он хотят послать свет от лазера в амбар ФД. И лазер, и амбра могут рассматриваться как точки на плоскости - карте фермы ФД. В панах коров направить лазер так, чтобы он послал лч света горизонтально или вертикально (то есть вдоль оси x или вдоль оси y). Затем они планируют ментяь направление луча посредством зеркал, чтобы направить луч в амбар.

На этой ферме есть $N$ ($1 \leq N \leq 100,000$) точек изгороди, расположенных в различных точках на плоскости, (и отличающихся также от точек лазера и амбара), на которых могут крепится зеркала. Коровы могут выбрать не крепить зеркало к некоторым точкам, тогда луч просто проходит через эту точку без поворотов (не меняя направление). Если коровы монтируют зеркало в точке изгороди, они выравнивают его диагонально так / или так \, что соответсвенно пернаправляет горизонтальный в вертикальный и наоборот.

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

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

Первая строка ввода содержит 5 целых чисел, разделённых одиночными пробелами. $N, x_L, y_L, x_B, y_B$, где $(x_L, y_L)$ - это размещение лазера, $(x_B, y_B)$ - размещение амбара. Все координаты между $0$ и $1,000,000,000$.

Каждая из следующих $N$ строк содержит $x$ и $y$ - координаты точек изгороди - целые числа в интервале $0 \ldots 1,000,000,000$.

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

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

Обход в ширину

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