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

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

Тандемный префикс#27306

Егор Кубратов очень огорчен задачами с codeforces и олимпиады Иннополиса, поэтому теперь он сам придумывает задачи и сам же их решает. Сегодня он придумал следующую задачу:

“Тандемный префикс – это подстрока, образованная конкатенацией двух непустых, не обязательно одинаковых префиксов строки и не являющаяся префиксом строки*. Вам необходимо найти длиннейший тандемный префикс данной строки. Если вариантов несколько, выведите тот, вхождение которого самое раннее. Если тандемного префикса не существует, то выведите -1”

*Имеется в виду, что тандемный префикс не является подстрокой, начинающейся в первом символе строки. То есть по составу букв он может являться каким-то префиксом, но только если начинается не в первой позиции. Например, в строке “aaa” подстрока [2;3] является тандемным префиксом.

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

В первой строке дана строка, состоящая из строчных латинских букв. Длина строки не превышает 10⁵.

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

Выведите ответ, если он существует. Иначе выведите -1.

Ввод	Вывод
abcabac	aba

Подстроки abca и abcab являются конкатенациями двух префиксов, но они сами являются префиксами, что противоречит определению тандемного префикса, поэтому aba – единственный тандемный префикс данной строки.

(с) Курбатов Е., 2017

Z-функция. Префикс-функция строковые суфф. структуры

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

Уравнение#27304

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

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

На вход подается одна строка без пробелов и знаков переноса строки.

В ней могут содержаться такие символы:

x - переменная, относительно которой Курбат должен решить

уравнение. Может стоять где угодно.

+-*/= - соответствующие знаки арифметических операций. НЕ могут стоять в начале уравнения. Могут стоять после икса или констант.

^ - возведение в степень. Может стоять только после икса. После может стоять только константа.

Числа от -10^1000 до 10^1000 - константы. Могут стоять после иксов,

знаков арифметических операций и знака возведения в степень.

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

Если курбат может решить уравнение, то выведите "Yes", иначе выведите "No".

Ввод	Вывод
10x+x=7	Yes

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

Вывод формулы

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

Битая кодировка#27303

–Т—Л–≤–µ–і–Є—В–µ –і–≤–∞–і—Ж–∞—В—М –њ–µ—А–≤—Л—Е –њ—А–Њ—Б—В—Л—Е —З–Є—Б–µ–ї

Простые числа и разложение на множители реализация

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

Fencing the Herd#27299

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

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

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

Первая строка ввода содержит N (1 <= N <= 100000) и Q (1 <= Q <= 100000) разделённые одним пробелом. Это, соответственно, начальное количество коров в стаде и количество запросов.

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

Оставшиеся Q строк содержат запросы, либо добавляющие новую корову в стадо, либо проверяющие изгородь на применимость. Строка вида 1 x y означает, что новая корова добавляется в стадо на позицию x y. Строка вида 2 A B C означает, что ФД хочет проверить изгородь, описываемую прямой Ax+By=C.

Все позиции коров уникальны (-10⁹ <= x, x <= 10⁹). Кроме того, -10⁹ <= A, B <= 10⁹ и -10¹⁸ <= C <= 10¹⁸. Никогда не будет изгороди с A = B = 0.

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

Для каждой изгороди выведите YES, если она подходит и NO, в противном случае.

Ввод	Вывод
3 4 0 0 0 1 1 0 2 2 2 3 1 1 1 2 2 2 3 2 0 1 1	YES NO NO

Прямая 2x + 2y = 3 оставляет начальные 3 коровы по одну сторону. Однако корова (1,1) на другой стороне, поэтому после её добавления такая изгородь уже не подходит. Прямая Y=1 не подходит, поскольку коровы (0,1) и (1,1) находятся на ней.

Предупреждение: ввод-вывод для этой задачи очень большой. В С++ можно использовать scanf или ios_base::sync_with_stdio(false). В Java надо не использовать java.util.Scanner. Не делайте flush вывода (например? используя std::endl) после каждого запроса.

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

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

Деление пополам#27290

Дано действительное число a и натуральное n. Вычислите корень n-й степени из числа a.

Для решения используйте метод деления отрезка пополам.

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

Число a – действительное, неотрицательное, не превосходит 1000, задано с точностью до 6 знаков после запятой. Число n – натуральное, не превосходящее 10. Каждое число вводится в отдельной строке.

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

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

Примеры

№	Входные данные	Выходные данные
1	2 2	1.41421356237

Бинарный поиск значения функции

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

Двоичный поиск для монотонной функции (С++)#27283

Дано натуральное число x. Вычислите кубический корень из числа.

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

Число x – натуральное, не превосходящее \(10^6\).

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

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

Примеры

№	Входные данные	Выходные данные
1	2	1.259921

Бинарный поиск значения функции

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

Отрицательный цикл#27277

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

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

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

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

В первой строке выведите "YES", если цикл существует, или "NO", в противном случае.

Примеры

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

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

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

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

Количество релаксаций#27274

Дан взвешенный ориентированный граф. Необходимо найти минимальное количество фаз с релаксациями в работе алгоритма Форда-Беллмана при нахождении кратчайшего пути от вершины 1.

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

Программа получает на вход одно число количество вершин n (2 ≤ n ≤ 100) и количество ребер m (2 ≤m ≤ 10 000). В следующих m строках вводятся три числа: a, b и c, где a и b – начало ребра и его конец, а c – вес ребра (1 ≤ a, b ≤ n, 1 ≤ c ≤ 10 000).

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

Программа должна вывести единственное целое число - минимальное количество релаксаций в работе алгоритма Форда-Беллмана при нахождении кратчайшего пути от вершины 1.

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

(с) Шалдин В., 2017г.

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

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

Домой на электричках#27273

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

Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.

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

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

Во входных данных записаны сначала числа N (2 ≤ N ≤ 100) и E (2 ≤ E ≤ N). Затем записано число M (0 ≤ M ≤ 100), обозначающее число рейсов электричек. Далее идет описание M рейсов электричек. Описание каждого рейса электрички начинается с числа K_i (2 ≤ K ≤ N) — количества станций, на которых она останавливается, а далее следует K_i пар чисел, первое число каждой пары задает номер станции, второе — время, когда электричка останавливается на этой станции (время выражается целым числом из диапазона от 0 до 10⁹). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.

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

Выведите одно число — минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите –1.

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

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

Лабиринт знаний#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#27271

В ориентированном взвешенном графе вершины пронумерованы числами от 1 до n. Если i<j, то существует ребро из вершины i в вершину j, вес которого определяется по формуле \(wt(i,j)=(179i+719j)\ mod \ 1000 - 500\). Определите вес кратчайшего пути, ведущего из вершины 1 в вершину n.

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

Программа получает на вход одно число n (2≤n≤13000).

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

Программа должна вывести единственное целое число - вес кратчайшего пути из вершины 1 в вершину n в описанном графе.

Примеры

№	Входные данные	Выходные данные
1	2	117
2	3	-164

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

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

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

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

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

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

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

Примеры

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

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

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

Форд-Беллман: Начало (C++)#27268

Дополните программу, чтобы она верно решала следующую задачу.

Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.

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

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

Программа получает сначала число N (1 <= N <= 100) – количество вершин графа и число M (0 <= M <= 10000) – количество ребер. В следующих строках идет M троек чисел, описывающих ребра: начало ребра, конец ребра и вес (вес – целое число от -100 до 100).

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

Программа должна вывести N чисел – расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.

Примеры

№	Входные данные	Выходные данные
1	6 4 1 2 10 2 3 10 1 3 100 4 5 -10	0 10 20 30000 30000 30000

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

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

Форд-Беллман#27267

Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.

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

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

Программа получает сначала число N (1 <= N <= 100) – количество вершин графа и число M (0 <= M <= 10000) – количество ребер. В следующих строках идет M троек чисел, описывающих ребра: начало ребра, конец ребра и вес (вес – целое число от -100 до 100).

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

Программа должна вывести N чисел – расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.

Примеры

№	Входные данные	Выходные данные
1	6 4 1 2 10 2 3 10 1 3 100 4 5 -10	0 10 20 30000 30000 30000

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

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

Строка с минимальной суммой#27238

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

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

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

Двумерные массивы

✓ 2 455✗ 2 549300лёгкаяВойти и решать

Магический квадрат?#27237

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

Формат входных данных
В первой строке вводится размер матрицы N (0 < N <= 100) . В следующих N строках вводятся строки матрицы, по N значений в каждой, разделённые пробелами.

Формат выходных данных
Программа должна вывести слово 'YES', если матрица является магическим квадратом, и слово 'NO', если не является.

Двумерные массивы

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

Нестандартное заполнение - 2. Змейка#27236

Напишите программу, которая заполняет матрицу из N строк и M столбцов натуральными числами змейкой, как показано в примере.

Формат входных данных
Входная строка содержит числа N и M, разделённые пробелом (5 <= N, M <= 20).

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

Двумерные массивы

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