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

Для приведенного ниже кода, найдите асимптотику:

#include <bits/stdc++.h>
using namespace std;

vector < vector<int> > g;
vector <int> color;

void dfs(int v, int p)
{
	color[v] = 1;
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i];
		if (to == p)
			continue;
		if (color[to] == 1)
		{
			cout << "YES";
			exit(0);
		}
		if (color[to] == 0)
			dfs(to, v);
	}
	color[v] = 2;
}

int main()
{
	int n, m, a, b;
	cin >> n >> m;

	g.resize(n);
	color.resize(n);

	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	dfs(0, -1);
	cout << "NO";
	return 0;
}

1) O(n) 2) O(m) 3) O(n + m) 4) O(nm)

Обход в глубину

800лёгкаяВойти и решать

Заполнение конем#31784

Дана шахматная доска nхn. Пусть конь стоит на клетке (1,1). Необходимо найти такую последовательность ходов коня, при которой он побывает на каждой клетке доски ровно по одному разу.

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

На вход программе подается натуральное число n (n ≤ 8).

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

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

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

Ввод	Вывод
3	0
5	1 1 20 17 12 3 16 11 2 7 18 21 24 19 4 13 10 15 6 23 8 25 22 9 14 5

Обход в глубину Рекурсия

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

Защищенное соединение#30707

В свете недавних новостей о прослушке каналов связи, два непримиримых интернет-гиганта Урагании <<Laim.UR>> и <<Xenda>> решили подписать соглашение об установлении защищенного канала связи между дата-центрами друг друга. В Урагании \(n\) городов, но, к сожалению, ни в одном городе нет дата-центров обоих гигантов. Поэтому для формирования защищенного канала придется прокладывать междугородние линии связи.

Специалисты компаний определили \(m\) пар городов, которые можно соединить, проложив сегмент канала связи, и оценили стоимость создания такого сегмента для каждой из этих пар.

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

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

Формат входных данных
В первой строке находятся целые числа \(n\) и \(m\) (\(2 \le n \le 5\,000\), \(1 \le m \le 10^5\)) — количество городов и количество пар городов, которые можно соединить сегментом канала связи.

Во второй строке находятся \(n\) целых чисел \(a_i\) (\(0 \le a_i \le 2\)). Если \(a_i = 0\), то в \(i\)-м городе нет дата-центра ни одного из гигантов. Если \(a_i = 1\), то в \(i\)-м городе есть дата-центр <<Laim.UR>>, а если \(a_i = 2\), то в \(i\)-м городе находится дата-центр <<Xenda>>. Гарантируется, что среди этих чисел есть как минимум одна единица и одна двойка.

В каждой из следующих \(m\) строк находится по три целых числа — \(s_i\), \(t_i\) и \(c_i\), которые означают, что города \(s_i\) и \(t_i\) (\(1 \le s_i, t_i \le n\), \(s_i \ne t_i\)) можно соединить сегментом канала связи стоимостью \(c_i\) (\(1 \le c_i \le 10^5\)). Каждую пару городов можно соединить не более чем одним сегментом канала.

Формат выходных данных
Если соединить защищенным каналом связи два дата-центра разных интернет-гигантов возможно, то выведите в выходной файл три числа: \(x\), \(y\) и \(d\), означающие, что между городами \(x\) и \(y\) возможно провести канал связи суммарной стоимостью \(d\). В городе \(x\) должен находиться дата-центр <<Laim.UR>>, в городе \(y\) — дата-центр <<Xenda>>. Если существует несколько оптимальных ответов, выведите любой. Если провести искомый канал невозможно, выведите \(-1\).

В первом примере оптимально построить канал связи из двух сегментов: \(3-2\) и \(2-4\).

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

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

Заправки-2#30702

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

В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в N-й, потратив как можно меньшее денег.

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

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

В первой строке вводится число N (1<=N<=100), в следующей строке идет N чисел, i-е из которых задает стоимость бензина в i-м городе (всё это целые числа из диапазона от 0 до 100). Затем идет число M – количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами – номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону), между двумя городами всегда существует не более одной дороги, не существует дорог, ведущих из города в себя.

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

Требуется вывести одно число – суммарную стоимость маршрута или -1, если добраться невозможно.

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

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

Количество способов топологической сортировки#29453

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

Найдите количество способов топологически отсортировать, зная только количество вершин.

Входные данные
Входная строка содержит одно натуральное число n - кол-во вершин (n <= 1000).

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

Примеры

№	Входные данные	Выходные данные
1	7	48

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

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

Лексикографически минимальная топологическая сортировка#29452

Дан связный ациклический ориентированный граф. Найдите его лексикографически минимальную топологическую сортировку.

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

В первой строке вводится количество вершин n (1 <= n <= 10000). Во второй строке водится n чисел a_i (0 <= a_i <= n, a_i != i). Значение a_i - предок вершины с номером i (вершины нумеруются с 1). Если a_i = 0, то вершина i является корнем и не имеет предков, гарантируется, что таких вершин ровно 1.

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

Решение должно вывести n чисел - лексикографически минимальную топологическую сортировку.

Примеры

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

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

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

Хакер#27307

Однажды юный хакер Шалдыга Севин решил совершить дерзкое преступление - сменить имя своего друга Максима Никитина на сильвере, пока тот был в ЛКШ Зима (Ливневая Коробка Шредингера), чтобы Наталья Владимировна поставила ему двойку. Для этого Шалдыга решил заразить вирусом базу данных сильвера.

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

Хакер хочет узнать минимальное количество дней, которое понадобится для того, чтобы заразить все компьютеры лицея. Однако выяснилась еще одна проблема - эта задача легко решается с помощью БФСа, но написать его меньше чем за 15 дней невозможно, а Хакеру еще нужно сделать 200 номеров по математике. Поэтому Шалдыга попросил Вас сделать невозможное - написать программу, отвечающую на его вопрос, за время этого контеста.

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

В первой строке на вход подаются два числа N и M - количество компьютеров в лицее и соединений между ними соответственно. 1 <= N, M <= 100

В следущих M строках Вам даются описания соединений между компьютерами, а именно 2 чила U и V, которые означают, что компьютеры U и V соединены.

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

Выведите ответ на вопрос Шалдыги

Ввод	Вывод
6 9 1 2 1 3 2 4 2 6 3 4 3 5 4 5 4 6 5 6	2

(с) Григорьев Е., 2017

графы Обход в ширину

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

Рейсы во времени#27276

Между \(N\) населенными пунктами совершаются пассажирские рейсы на машинах времени.

В момент времени 0 вы находитесь в пункте \(A\). Вам дано расписание рейсов. Требуется оказаться в пункте \(B\) как можно раньше (то есть в наименьший возможный момент времени).

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

Формат входных данных
Первая строка содержит число \(N\) — количество населенных пунктов (\(1 \le N \le 1000\)). Вторая строка содержит два числа \(A\) и \(B\) — номера начального и конечного пунктов. Третья строка содержит число \(K\) — количество рейсов (\(0 \le K \le 1000\)). Следующие \(K\) строк содержит описания рейсов, по одному на строке. Каждое описание представляет собой четверку целых чисел. Первое число каждой четверки задает номер пункта отправления, второе — время отправления, третье — пункт назначения, четвертое — время прибытия. Номера пунктов — натуральные числа из диапазона от 1 до \(N\). Пункт назначения и пункт отправления могут совпадать. Время измеряется в некоторых абсолютных единицах и задается целым числом, по модулю не превышающим \(10^9\). Поскольку рейсы совершаются на машинах времени, то время прибытия может быть как больше времени отправления, так и меньше, или равным ему.

Гарантируется, что входные данные таковы, что добраться из пункта \(A\) в пункт \(B\) всегда можно.

Формат выходных данных
Выведите минимальное время, когда вы сможете оказаться в пункте \(B\).

Алгоритм Флойда

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

Авиаперелеты#27275

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

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

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

В первой строке находятся числа N (количество городов), M (количество авиарейсов), K (количество оставшихся ночей), S (номер города, в котором живет профессор), F (номер города, в котором проводится конференция).

Ограничения: 2≤N≤100, 1≤M≤10⁵, 1≤K≤100, 1≤S≤N, 1≤F≤N.

Далее идет M строк, задающих расписание авиарейсов. i-я строка содержит три натуральных числа: S_i, F_i и P_i, где S_i - номер города, из которого вылетает i-й рейс, F_i- номер го-рода, в который прилетает i-й рейс, P_i - стоимость перелета i-м рейсом. 1≤S_i≤N, 1≤F_i≤N, 1≤P_i≤106.

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

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

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

Алгоритм Форда-Беллмана кратчайшие пути

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

Лабиринт знаний#27272

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

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

Первая строка входных данных содержит целые числа N (1 <= N <= 2000) – количество комнат и M (1 <= M <= 10000) – количество дверей. В каждой из следующих M строк содержится описание двери – номера комнат, из которой она ведет и в которую она ведет (через дверь можно ходить только в одном направлении), а также целое число, которое прибавляется к количеству знаний при прохождении через дверь (это число по модулю не превышает 10000). Двери могут вести из комнаты в нее саму, между двумя комнатами может быть более одной двери.

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

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

Примеры

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

Алгоритм Форда-Беллмана

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

Отрицательный цикл-2#27269

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

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

В первой строке содержится число N (1 <= N <= 100) – количество вершин графа. В следующих N строках находится по N чисел – матрица смежности графа. Веса ребер по модулю меньше 100000. Если ребра нет, соответствующее значение равно 100000.

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

В первой строке выведите "YES", если цикл существует, или "NO", в противном случае. При наличии цикла выведите во второй строке количество вершин в нем (считая одинаковые – первую и последнюю), а в третьей строке – вершины, входящие в этот цикл, в порядке обхода. Если циклов несколько, то выведите любой из них.

Примеры

№	Входные данные	Выходные данные
1	3 100000 100000 -51 100 100000 100000 100000 -50 100000	YES 4 3 2 1 3

Алгоритм Флойда

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

Pink Floyd#27233

Группа Pink Floyd собирается дать новый концертный тур по всему миру. По предыдущему опыту группа знает, что солист Роджер Уотерс постоянно нервничает при перелетах. На некоторых маршрутах он теряет вес от волнения, а на других - много ест и набирает вес.

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

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

Первая строка входного файла содержит три натуральных числа n, m и k - количество городов в мире, количество рейсов и количество концертов, которые должна дать группа соответственно (n≤100, m≤10⁴, 2≤k≤10⁴). Города пронумерованы числами от 1 до n. Следующие m строк содержат описание рейсов, по одному на строке. Рейс номер i описывается тремя числами b_i, e_i и w_i - номер начального и конечного города рейса и предполагаемое изменение веса Роджера в миллиграммах (1≤b_i,e_i≤n, −10⁵≤w_i≤10⁵). Последняя строка содержит числа a1, a2, ..., ak - номера городов, в которых проводятся концерты. В начале концертного тура группа находится в городе a1.Гарантируется, что группа может дать все концерты.

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

Первая строка выходного файла должна содержать число s - количество рейсов, которые должна сделать группа. Вторая строка должна содержать s чисел - номера используемых рейсов. Если существует такая последовательность маршрутов между концертами, что Роджер будет набирать вес неограниченно, то первая строка выходного файла должна содержать строку “infinitely kind”.

Ввод	Вывод
4 8 5 1 2 -2 2 3 3 3 4 -5 4 1 3 1 3 2 3 1 -2 3 2 -3 2 4 -10 1 3 1 2 4	6 5 6 5 7 2 3
4 8 5 1 2 -2 2 3 3 3 4 -5 4 1 3 1 3 2 3 1 -2 3 2 -3 2 4 10 1 3 1 2 4	infinitely kind

Алгоритм Флойда графы кратчайшие пути

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

Столовая#27231

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

Помогите найти такое здание!

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

В первой строке находятся два числе N и M - количество зданий и количество дорог, соединяющих здания (1<=N<=100, 0 <=M<=(N(N−1))/2. Далее в M строках расположены описания дорог: 3 целых числа s_i, e_i, l_i - здания, в которых начинается и заканчивается дорога и длина дороги соответственно (1<=s_i,e_i<=N, 0<=l_i,=100, дороги двунаправленные).

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

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

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

Алгоритм Флойда кратчайшие пути

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

Флойд - существование#27226

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

Комментарий: Кратчайший путь может не существовать по двум причинам:

Нет ни одного пути
Есть пути сколь угодно маленького веса

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

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

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

Выведите N строк по N чисел. j-е число в i-й строке должно соответствовать кратчайшему пути из вершины i в вершину j. Число должно быть равно 0, если пути не существует, 1, если существует кратчайший путь, и 2, если пути существуют, но бывают пути сколь угодно маленького веса.

Примеры

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

Алгоритм Флойда

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

Where's Bessie?#27222

Фермер Джон тестирует новую камеру, которая может "схватить картинку" и автоматически вычислить положение коров. К несчастью, у камеры не очень хороший алгоритм поиска коров и ФД нуждается в Вашей помощи.

Картинка, получаемая камерой, может быть описана решёткой из N×N символов, каждый в интервале A…Z, представляющих один из 26 возможных различных цветов. ФД считает наилучшим такой алгоритм распознавания коров: PCL (возможное размещение коровы) - это прямоугольник на решётке (возможно вся решётка) со сторонами параллельными сторонам решётки, не содержащий внутри других PCL и обладающий следующим свойством: внутри этого прямоугольника должны присутствовать ровно два цвета, один формирует непрерывный регион, а другой формирует два или более непрерывных регионов.

Например, такой образ

AAAAA

ABABA

AAABB

есть PCL, поскольку символы A формируют непрерывный регион, символы B форрмируют более одного непрерывного региона. Интерпретация - это корова с цветом A и с пятнами цвета B.

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

По заданному образу камеры ФД определите количество PCL.

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

Первая строка ввода содержит N, размер решётки (1≤N≤20). Следующие N строк описывают образ, каждая состоит из N символов.

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

Количество PCL в образе.

Ввод	Вывод
4 ABBC BBBC AABB ABBC	2

Задача на реализацию Обход в глубину Перебор

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

Транспортировка#27126

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

Имея привычку делать важные дела в самый последний момент, дизайнер закончил работу над макетом за два дня до начала школы. Ещё день уйдёт у завода-изготовителя на то, чтобы изготовить кружки и нанести на них изображение. Нато, чтобы довезти кружки от завода-изготовителя до ЛКШ,остаётся всего 24 часа.

Заказ на 10000000 экземпляров кружек (а именно столько заказали организаторы), конечно же, за один рейс не увезти. Однако, за первый рейс хочется привезти максимальное количество кружек. Для перевозки был заказан один большегрузный автомобиль. Но есть один нюанс: на некоторых дорогах установлено ограничение на вес автомобиля. Поэтому если автомобиль нагрузить кружками под завязку, то, возможно, не удастся воспользоваться самым коротким маршрутом, а придётся ехать в объезд. Может случиться даже так, что из-за этого грузовик не успеет доехать до лагеря вовремя, а этого допустить никак нельзя. Итак, сколько же кружек можно погрузить в автомобиль, чтобы успеть привезти этот ценный груз вовремя, и не нарушая правил дорожного движения?

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

В первой строке находятся числа n (1≤n≤500) и m - количество узловых пунктов дорожной схемы и количество дорог, соответственно. В следующих m строках находится информация о дорогах. Каждая дорога описывается в отдельной строке следующим образом. Сначала указаны номера узловых пунктов, которые соединяются данной дорогой, потом время, которое тратится на проезд по этой дороге, и, наконец, максимальный вес автомобиля, которому разрешено ехать по этой дороге. Известно, что все дороги соединяют различные пункты, причем для каждой пары пунктов есть не более одной дороги, непосредственно их соединяющей. Все числа разделены одним или несколькими пробелами.

Узловые пункты нумеруются числами от 1 до n. При этом завод по производству кружек имеет номер 1, а ЛКШ - номер n. Время проезда по дороге задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что одна кружка весит 100 грамм, а пустой грузовик - 3 тонны.

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

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

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

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

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

Одуванчики#26996

У Ани есть поле размером N×M клеток. На этом поле Аня разводит одуванчики. Аня заметила, что если в некоторой клетке поля растёт одуванчик, то на следующий день в четырёх клетках рядом с ним (севернее, восточнее, южнее и западнее) вырастает по одуванчику. Однако за пределами поля одуванчики не вырастают.

Сейчас на поле растёт несколько одуванчиков (не меньше одного). Определите, через сколько дней всё поле будет в одуванчиках. Известно, что Аня хорошо заботится о выросших одуванчиках, поэтому ни один из них не погибнет.

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

На первой строке находятся числа N и M (1<=N, M <= 100) размеры поля. Далее идут N строк, каждая из которых по M элементов. Эти строки обозначают поле. Символ «.» в строке означает, что данная клетка поля пуста, а символ «*» что в клетке находится одуванчик. Других символов в строках быть не может.

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

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

Частичные решения, работающие при случаях, когда N = 1 или M = 1, получат не менее 30 баллов.

Ввод	Вывод
3 3 ... .*. ...	2
4 3 ... ... ... *..	5

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

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

Путь в никуда#24761

Колобку снится странный сон.
В нём Колобок находится на клетчатом поле размера n × m в клетке с координатами (x, y).
Изначально Колобок смотрит вдоль положительного направления оси X. Затем он начинает идти по полю со следующей закономерностью:
• Пройти на одну клетку вперед. Повернуть на 90^oвправо.
• Пройти на одну клетку вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на четыре клетки вперед. Повернуть на 90^o вправо.
• И так далее...

Движение продолжается до тех пор, пока Колобок не выйдет за границы поля. После этого Колобок просыпается.

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

Формат входного файла
В первой строке входного файла находятся два натуральных числа n, m (1 ≤ n, m ≤ 10⁹ ) — размеры доски вдоль оси X и оси Y соответственно. Во второй строке находятся два натуральных числа x, y (1 ≤ x ≤ n; 1 ≤ y ≤ m) — координаты стартовой позиции колобка.

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

Вывод	Ввод
7 6 3 4	36
2 2 1 1	2
2 2 1 2	4

Комментарий
На рисунке наглядно показан первый пример.

Бинарный поиск Деревья Префиксные суммы(минимумы, ...)Разреженные таблицы (sparse table)Структуры данных

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

Orders#24733

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

Входные данные
В первой строке на вход подается числа n и m - количество приказов, которые отдал Блейз, и количество команд, которые понимают его войска соответственно. (1 <= n, m <= 5000)
В следующей строке на вход подаются m слов - команды, которые понимают войска Блейза.
В следующих n строках на вход подаются слова - приказы, которые отдает Блейз.
Все строки длиной не превышают 100.

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

Выведите n строк: в строке номер i содержится ответ на задачу для приказа Блейза номер i. Строки, являющиеся ответом на этот запрос, выводятся через пробел в одну строку.

Пример
Ввод

5 5
is in if on of
it
in
of
ij
op

Вывод
if in is
if in is on
if of on
if in is
of on

(с) Евгений Григорьев

Бор Обход в глубину Перебор

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

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