Алгоритмы

2 280 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Шоколадка#33298
Двое играют в такую игру: перед ними лежит шоколадка размера NxM. За ход можно разломить имеющийся кусок шоколадки вдоль одной из сторон на 2 "непустых".
 
Однако, нельзя разламывать куски размером не больше, чем 1k (куски можно поворачивать; мы считаем, что один кусок "не больше" другого, если он равен ему или его части). Таким образом, нельзя разламывать куски размером 11, 12, , 1k, а остальные куски разламывать можно.
 
Проигрывает тот, кто не может сделать ход. Определите, кто же станет победителем в игре, если известны начальные размеры шоколадки.
 
Входные данные
Вводятся целые числа 0 < N, M, K <= 100.
 
Выходные данные
Вывести 1 или 2 - номер игрока, который выиграет при правильной игре.

Ввод Вывод
1 1 1 2
2 2 1 1

 

Функция Гранди
✓ 7✗ 281 100средняяВойти и решать
Охота на Снарка#33296
В начальный момент времени Снарк находится в точке прямой с целой неотрицательной координатой X. За ход он может оказаться в любой точке с целой координатой Y при условии, что |X-Y| <= S. Кроме того, Снарк не любит булочки, поэтому он никогда не прыгнет в клетку, где одна из этих противных штук лежит. Булочник не хочет, чтобы Снарк попал домой. После каждого хода Снарка Булочник может положить булочку в любую точку прямой при условии, что это не начало координат (дом Снарка) и в этой клетке нет Снарка. Определите, сможет ли Булочник помешать Снарку оказаться дома. Изначально в некоторых клетках лежат булочки.
 
Входные данные
В первой строке задаются целые числа 0 <= X < 10000, 0 < S <= 100 и 0 <= N < max(X-1, 0) - количество булочек, которые уже лежат на прямой. Далее идут N различных чисел 0 < bi < X - координаты точек, где лежит гадость.
 
Выходные данные
Выведите "YES", если Булочник сможет реализовать свои грязные планы, "NO" - если при любых действиях врага Снарк сможет припрыгать домой.

Ввод Вывод
1 1 0 NO
10 3 3
7 8 9
 YES

Простые игры
✓ 14✗ 4031 300средняяВойти и решать
Циклическая строка#33294
Строка S была записана много раз подряд, после чего из получившейся строки взяли подстроку и дали вам. Ваша задача определить минимально возможную длину исходной строки S.
 
Входные данные
На вход программы поступает строка, которая содержит только латинские буквы, длина строки не превышает 50000 символов.
 
Выходные данные
Требуется вывести одно число – ответ  на вопрос задачи.
 

 

Примеры
№ Входные данные Выходные данные
1 z 1
2 abcdef 6
Алгоритмы на строках
✓ 52✗ 177600лёгкаяВойти и решать
*Упорядочивания#33257
Сегодня у Кэрол выходной. Но даже в этот прекрасный весенний день она не отдыхает, а тренируется и готовится к сражениям со скруллами. Одним из важных навыков является умение быстро ориентироваться в незнакомых местах. Для того, чтобы отточить это умение, Кэрол пригласила своего наставника Йон-Рогга.
Кэрол и Йон-Рогг будут играть в следующую игру. Сначала Йон-Рогг нарисует на бумаге карту убежища скруллов. Карта представляет из себя n помещений, пронумерованных от 1 до n. Некоторые пары помещений соединены двусторонними переходами. Убежище устроено так, что от любого помещения до любого другого можно добраться, перемещаясь по коридорам. Для того, чтобы игра не была слишком сложной, Йон-Рогг нарисует ровно n − 1 переход между помещениями. Иными словами, карта убежища представляет собой дерево.
Известно, что для перевозки грузов между помещениями в убежище скруллы используют специальных роботов. Роботы довольно примитивны и плохо ориентируются в убежище. Для решения этой проблемы скруллы выбрали в каждом переходе ровно одно направление, вдоль которого могут перемещаться роботы.
После того, как Йон-Рогг нарисует на бумаге карту убежища, он также для каждого перехода отметит, в каком направлении по нему перемещаются роботы. Иными словами, Йон-Рогг ориентирует ребра нарисованного дерева.
Чтобы структурировать карту убежища, Кэрол должна составить список, состоящий из всех номеров помещений в некотором порядке. При этом должно выполняться следующее условие: в любом переходе роботы перемещаются от помещения, которое идет в списке раньше, к помещению, которое идет с писке позже. Более формально, Кэрол должна составить такую перестановку номеров помещений p1p2 . . . pn, для которой верно, что если роботы могут перемещаться по переходу от помещения pi к помещению pj , то i < j.
Пока Кэрол бьется над своим заданием, Йон-Роггу стало интересно, сколько всего решений существует у этой задачи. Иными словами, Йон-Роггу интересно, сколько перестановок удовлетворяют условию, описанному выше. Помогите ему узнать это. Так как ответ может быть очень большим, Йон-Рогг попросил вас сообщить лишь его остаток от деления на 998 244 353.

Входные данные: Первая строка входных данных содержит единственное целое число n — количество помещений в убежище, нарисованном Йон-Роггом (1 <= n <= 3 000).
Каждая из следующих n − 1 строк содержит два целых числа a, b — номера помещений, соединенных очередным коридором (1 <= a, b <= n). Роботы перемещаются по коридору в направлении от помещения a к помещению b.
Гарантируется, что убежище представляет собой дерево, то есть от любого помещения можно добраться до любого другого, двигаясь по переходам (возможно, в направлении, противоположном направлению движения роботов в этом переходе).

Выходные данные: Выведите остаток от деления на 998 244 353 количества различных перестановок p1p2 . . . pn, для которых верно, что если роботы перемещаются по переходу от помещения pi к помещению pj , то i < j.
 
Примеры
№ Входные данные Выходные данные
1
3
1 2
1 3
 2
2
4
2 3
3 1
2 4
 3

Замечание
В первом тесте из примера Кэрол может выписать две перестановки: {1, 2, 3} или {1, 3, 2}.
Во втором тесте Кэрол может выписать три перестановки: {2, 3, 1, 4}, {2, 3, 4, 1} или {2, 4, 3, 1}.
 
Топологическая сортировка
✓ 3✗ 121 300средняяВойти и решать
*Рапорт#33253
Верс нужно подготовить рапорт о последнем боевом вылете. Она уже сочинила в голове текст, осталось лишь его записать. Рапорт будет состоять из двух частей: первая будет содержать n слов, i-е из которых состоит из ai букв, вторая — m слов, j-е из которых состоит из bj букв. Язык Крии не содержит никаких знаков препинания. Верс должна записать рапорт на клетчатом рулоне бумаги, шириной w клеток. Так как рапорт состоит из двух частей, она разделит вертикальной чертой рулон на две части целой ширины, после чего в левой части напишет первую часть, а в правой — вторую.
Обе части рапорта записываются аналогично, каждая на своей части рулона. Одна буква слова занимает ровно одну клетку. Первое слово записывается в первой строке рулона, начиная с самой левой клетки этой части рулона. Каждое следующее слово, если это возможно, должно быть записано в той же строке, что и предыдущее, и быть отделено от него ровно одной пустой клеткой.
Иначе, оно пишется в следующей строке, начиная с самой левой клетки. Если ширина части рулона меньше, чем длина какого-то слова, которое должно быть написано в этой части, написать эту часть рапорта на части рулона такой ширины невозможно.
Гарантируется, что можно провести вертикальную черту так, что обе части рапорта возможно написать. Верс хочет провести вертикальную черту так, чтобы длина рулона, которой хватит, чтобы написать рапорт, была минимальна. Помогите ей найти эту минимальную длину.
 
Входные данные: 
- в первой строке даны три целых числа w, n и m — ширина рулона, количество слов в первой и второй части рапорта (\(1 <= w <= 10^9\); \(1 <= n, m <= 100 000\));
- в следующей строке дано n целых чисел ai — длина i-го слова первой части рапорта \(1 <= a_i <= 10^9\);
- в следующей строке дано m целых чисел bj — длина j-го слова второй части рапорта \(1 <= b_j <= 10^9\).
Гарантируется, что возможно провести черту так, что обе части рапорта возможно написать.

Входные данные: в единственной строке выведите одно целое число — минимальную длину рулона, которой достаточно, чтобы написать рапорт.
 
Примеры
№ Входные данные Выходные данные
1
15 6 6
2 2 2 3 2 2
3 3 5 2 4 3
 3

Примечание
В тесте из примера рулон можно разделить на две части, проведя черту между 7 и 8 столбцом клеток, а затем записать по два слова в каждой строке в обеих частях рапорта.
Бинарный поиск по ответу
✓ 54✗ 7811 100средняяВойти и решать
Ослабление флота#33252
Кэрол Дэнверс, известная как Капитан Марвел противодействует флоту Скруллов. Каждый из
кораблей Скруллов имеет определенную мощность, выраженную натуральным числом.
Кэрол считает, что настолько сильна, что может не только вывести из строя флот, но и немного
развлечься. Внимательно изучив мощность корабля, она решила, что будет выводить их из строя
в следующем порядке: каждый раз Кэрол будет атаковать тот корабль из неатакованных ранее,
мощность которого является медианой мощностей оставшихся кораблей.
Медиану ряда чисел Кэрол вычисляет следующим образом:
• Если количество чисел в ряду нечетно, то медиана — число, стоящее посередине упорядоченного по возрастанию данного ряда.
• Если количество чисел в ряду чётно, то медианой ряда является:
– Меньшее из двух стоящих посередине чисел упорядоченного по возрастанию данного ряда, если два средних различны.
– Любое из двух стоящих посередине чисел упорядоченного по возрастанию данного ряда,
если два средних равны.
Помогите Капитану Марвел посчитать порядок, в котором нужно атаковать корабли.

Формат входных данных
В первой строке дано одно натуральное число n — число кораблей во флоте Скруллов (1 <= n <= 105).
Во второй строке содержатся n натуральных чисел ai — мощность i-го корабля (1 <= ai <=109).
Формат выходных данных
Выведите n чисел — мощности кораблей в том порядке, в котором Кэрол будет их атаковать.
 
Ввод Вывод
3
8 3 19
 
 8 3 19
4
4 2 2 1
 2 2 1 4


 
"Два указателя"
✓ 204✗ 374700средняяВойти и решать
Один конь#33251
На шахматной доске NxN в клетке (x1, y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2, y2), где растет вкусная шахматная трава. Какое наименьшее количество ходов он должен для этого сделать?
 
Формат входных данных
На вход программы поступает пять чисел: N, x1, y1, x2, y2 (\(5 <= N <= 20\), \(1 <= x_1,\ y_1,\ x_2,\ y_2 <= N\)). Левая верхняя клетка доски имеет координаты (1, 1), правая нижняя - (N, N).
 
Формат входных данных
Выведите единственное число K - наименьшее необходимое число ходов коня. 
Обход в ширину
✓ 590✗ 826600лёгкаяВойти и решать
Префикс-функция#33249
Дана непустая строка S, длина которой N не превышает \(10^6\). Будем считать, что элементы строки нумеруются от 1 до N.
 
Для каждой позиции i символа в строке нас будет интересовать подстрока, заканчивающаяся в этой позиции, и совпадающая с некоторым началом всей строки. Вообще говоря, таких подстрок будет несколько, не меньше двух. Самая длинная из них имеет длину i, она нас интересовать не будет. А будет нас интересовать самая длинная из остальных таких подстрок (заметим, что такая подстрока всегда существует — в крайнем случае, если ничего больше не найдется, сгодится пустая подстрока).
 
Значением префикс-функции \(\pi[i]\) будем считать длину этой подстроки.
 
Префикс-функция используется в различных алгоритмах обработки строк. В частности, с её помощью можно быстро решать задачу о поиске вхождения одной строки в другую («поиск образца в тексте»).
 
Требуется для всех i от 1 до N вычислить \(\pi[i]\).
 
Входные данные
Одна строка длины N, \(0 < N <= 10^6\), состоящая из маленьких латинских букв.
 
Выходные данные
Выведите N чисел — значения префикс-функции для каждой позиции, разделенные пробелом.
 

 

Примеры
№ Входные данные Выходные данные
1 abracadabra 0 0 0 1 0 1 0 1 2 3 4
Z-функция. Префикс-функция
✓ 93✗ 114400лёгкаяВойти и решать
Все кратчайшие маршруты#33229
Учёный-ботаник получил карту дорог страны Лимония. Чтобы составить план исследования этой страны, ему требуется найти кратчайшие расстояния между каждой парой городов этой страны (можно ехать только по проложенным дорогам). Помогите учёному – напишите программу, которая решает эту задачу.
 
Входные данные
В первой строке вводится количество городов N ( 1 ≤ N ≤ 100 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы весовой матрицы графа, который описывает схему дорог между городами: положительное число означает расстояние между городами, ноль говорит о том, что дороги нет.
 
Выходные данные
Программа должна вывести все кратчайшие маршруты между всеми городами в следующем формате:
 
(1->3): 1 2 3 (23)
 
Сначала выводятся номера начального и конечного города (в скобках), затем – последовательность номеров городов, составляющая оптимальный маршрут, затем (в скобках) длина этого маршрута. Если между какими-то городами нет дороги, нужно вывести число 0.
 
Ввод Вывод
4
0 0 0 0
0 0 2 1
0 2 0 4
0 1 4 0
(1,2): 0 
(1,3): 0 
(1,4): 0 
(2,3): 2 3 (2)
(2,4): 2 4 (1)
(3,4): 3 2 4 (3)

Алгоритм Флойдакратчайшие пути
✓ 1✗ 901 200средняяВойти и решать
33228#33228
В одной из деревень Центрального района решили построить новую школу, но никак не могут выбрать, в какой именно. Решили сделать так: подсчитать для каждой деревни суммарное расстояние, которое будут проходить все школьники Центрального района, если школа будет построена в этой деревне, и выбрать место, для которого эта сумма будет минимальной. В распоряжении администрации есть карта дорог Центрального района. Напишите программу, которая поможет выбрать место для школы. Если какой-то населенный пункт не имеет связи с другим населенным пунктом, где предполагается разместить школу, считайте, что доставка каждого ученика вертолётом "стоит" 10000 единиц расстояния.
 
Входные данные
В первой строке вводится количество деревень N ( 1 ≤ N ≤ 100 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы весовой матрицы графа, который описывает схему дорог: положительное число означает расстояние между деревнями, ноль говорит о том, что дороги нет. В последней строке вводится N чисел - количество школьников в каждой деревне.
 
Выходные данные
Программа должна вывести два числа: сначала номер деревни, где нужно построить школу, а затем (через пробел) – общее расстояние, которое будут проходить все школьники Центрального района, если школа будет построена в этой деревне.

Ввод Вывод
4
0 11 8 4
11 0 2 5
8 2 0 13
4 5 13 0
15 26 30 12
 2 255

Алгоритм Флойдакратчайшие пути
✓ 11✗ 66800средняяВойти и решать
Суммарная длина дорог#33227
Найдите суммарную длину всех дорог в городе Новые Васюки. Схема дорог задана в виде весовой матрицы графа. На некоторых дорогах введено одностороннее движение. Если длины дорог из пункта А в пункт Б разные, это означает, что есть две разные дороги.
 
Входные данные
В первой строке вводится количество перекрёстков в Новых Васюках N ( 1 ≤ N ≤ 1000 ). В следующих N строках записано по N чисел, разделённых пробелами – длины дорог между каждой парой перекрёстков. Ноль означает, что дороги между этими перекрёстками нет.
 
Выходные данные
Программа должна вывести одно число – суммарную длину дорог. Дороги с двусторонним движением нужно считать только один раз.

Ввод Вывод
5
0 2 3 4 0
2 0 5 0 7
3 6 0 8 0
0 0 0 0 0
0 7 0 9 0
 44

Алгоритмы на графах
✓ 457✗ 349500лёгкаяВойти и решать
Количество дорог#33226
Напишите программу, которая считает количество дорог в городе Новые Васюки. Схема дорог задана как матрица смежности графа. На некоторых дорогах введено одностороннее движение.
 
Входные данные
В первой строке вводится количество перекрёстков в Новых Васюках N ( 1 ≤ N ≤ 1000 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы матрицы смежности графа, который описывает схему дорог.
 
Выходные данные
Программа должна вывести одно число – количество дорог в Новых Васюках. Дороги с двусторонним движением нужно считать только один раз.

Ввод Вывод
5
0 1 1 1 0
1 0 1 0 1
1 1 0 1 0
0 0 0 0 0
0 1 0 1 0
 7

Алгоритмы на графах
✓ 434✗ 310500лёгкаяВойти и решать
Сортировка по цифрам числа 2#33207
Дано N трехзначных чисел (1<=N<=1000). Необходимо вывести их в порядке возрастания.

Нельзя использовать встроенную сортировку

Пример
Входные данные
9
639 265 915 993 436 202 573 906 490 

Выходные данные
202 265 436 490 573 639 906 915 993
Квадратичные сортировкиОдномерные массивы
✓ 49✗ 144600лёгкаяВойти и решать
Сортировка по цифрам числа 1#33206
Дано N двузначных положительных чисел. Необходимо вывести их в порядке увеличения первой цифры. Если первые цифры одинаковы, то вывести их в порядке следования в исходном массиве.

Формат входных данных
В первой строке записано натуральное число N (1<=N<=1000). Вторая строка содержит n двузначных положительных чисел numsi (1 ≤ i ≤ n, 10 ≤ numsi ≤ 99).

Формат выходных данных
Выведите ответ на задачу.
Квадратичные сортировкиОдномерные массивы
✓ 64✗ 88600лёгкаяВойти и решать
Пятый самый легкий#33205
Формат входных данных
В первой строке записано натуральное число n (n < 100). Вторая строка содержит n положительных целых чисел mi - вес i-го предмета (1 ≤ i ≤ n, 1 ≤ ai ≤ 105). 

Формат выходных данных
Напечатайте массу предмета, являющегося "пятым самым легким предметом".
Квадратичные сортировкиОдномерные массивы
✓ 167✗ 324400лёгкаяВойти и решать
Средние в шеренге#33203
Формат входных данных
В первой строке записано натуральное число n (n < 100, n - четное). Вторая строка содержит n положительных целых чисел mi - рост i-го учащегося (1 ≤ i ≤ n, 1 ≤ ai ≤ 105). 

Формат выходных данных
Напечатайте рост тех двоих людей, которые бы оказались в середине шеренги в случае построения ее по ранжиру (по убыванию роста).
Квадратичные сортировкиОдномерные массивы
✓ 306✗ 392400лёгкаяВойти и решать
Использование сортировки 2#33202
В каждом из двух классов учатся по n человек (10 <= n <= 30). Известны средний балл каждого ученика каждого класса, подсчитанные по ряду предметов (все значения целые). Определить, в каком классе у "третьего из самых успевающих учеников" средняя оценка больше. Вывести цифру "1" - для первого класса, "2" - для второго. Если оценки равны, вывести эту оценку.


Формат входных данных
В первой строке записано натуральное число n (n < 100) - количество учеников в каждом классе . Вторая строка содержит n положительных целых чисел class1i - средний балл i-го ученика первого класса (1 ≤ i ≤ n, 1 ≤ class1i ≤ 105). Третья строка содержит n положительных целых чисел class2i - средний балл i-го ученика первого класса (1 ≤ i ≤ n, 1 ≤ class2i ≤ 105).

Формат выходных данных
Выведите ответ на задачу.
Квадратичные сортировкиОдномерные массивы
✓ 51✗ 132700средняяВойти и решать
Банкет#33147
На банкет были приглашены N Очень Важных Персон (ОВП). Были поставлены 2 стола. Столы достаточно большие, чтобы все посетители банкета могли сесть за любой из них. Проблема заключается в том, что некоторые ОВП не ладят друг с другом и не могут сидеть за одним столом. Вас попросили определить, возможно ли всех ОВП рассадить за двумя столами.
 
Входные данные: В первой строке входных данных содержатся два числа: N и M (1 <= N,M <= 100), где N – количество ОВП, а M – количество пар ОВП, которые не могут сидеть за одним столом. В следующих M строках записано по 2 числа – пары ОВП, которые не могут сидеть за одним столом.
 
Выходные данные: Если способ рассадить ОВП существует, то  выведите YES в первой строке и номера ОВП, которых необходимо посадить за первый стол, во второй строке. В противном случае в первой и единственной строке выведите NO.

Примеры
№ Входные данные Выходные данные
1
3 2
1 2
1 3
 YES
1
Обход в глубину
✓ 435✗ 503600лёгкаяВойти и решать
Баобаб#33146
Дан неориентированный невзвешенный граф. Необходимо определить, является ли он деревом.
 
Формат входных данных
В первой строке содержится одно натуральное число N (N ≤ 100) - количество вершин в графе. Далее в N строках по N чисел - матрица смежности графа: в i-ой строке на j-ом месте стоит 1, если вершины i и j соединены ребром, и 0, если ребра между ними нет. На главной диагонали матрицы стоят нули. Матрица симметрична относительно главной диагонали.
 
Формат выходных данных
Вывести "YES", если граф является деревом, и "NO" иначе.
Обход в глубину
✓ 597✗ 878500лёгкаяВойти и решать
Ход конем - 2#33143
Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке:
 
Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.
 
Входные данные 
Во входной строке находятся два натуральных числа N и M (\(1 <= N,\ M <= 15\)).  
 
Выходные данные 
Выведите единственное число количество способов добраться конём до правого нижнего угла доски.
 
Примеры
№ Входные данные Выходные данные
1 4 4 2
2 7 15 13309
Динамическое программирование: два параметра
✓ 236✗ 392700средняяВойти и решать
Поделиться
Класснуть