Алгоритмы

2 310 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Шахматная доска#27315
Требуется найти число способов расставить на шахматной доске NxN K ладей так, чтобы они не били друг друга. Все ладьи считаются одинаковыми.
 
Входные данные
Во входном файле записаны натуральные числа N и K (\(1 <= N, K <= 8\)).
 
Выходные данные
В выходной файл выведите одно целое число - ответ задачи.
 

 

Примеры
№ Входные данные Выходные данные
1 8 8 40320
Сочетания
✓ 89✗ 228700средняяВойти и решать
Разность#27314
Вывести разность между количеством двоичных деревьев с N листьями и количеством разбиений N-угольника на треугольники.
 
Входные данные
На вход подаётся одно число - N (\(1 <= N <= 10\))
 
Выходные данные
Выведите одно число - искомую разность
 

 

Примеры
№ Входные данные Выходные данные
1 1 0

 

Комбинаторные структуры
✓ 72✗ 61500лёгкаяВойти и решать
Количество чисел Каталана#27313
Вывести N-ное число Каталана

Входные данные
Первая строка входных данных содержит одно число N (\(1 <= N <= 20\)).
 
Выходные данные
Выведите одно число - N-ное число Каталана
 

 

Примеры
№ Входные данные Выходные данные
1 1 1
Комбинаторные структуры
✓ 75✗ 184700средняяВойти и решать
Генерация ПСП#27312

Самой инновационной разработкой "British Scientists, Inc" является способ нахождения решения для любой задачи, которую возможно решить с помощью тильда-омега-лямбда-исчисления (то есть, для никакой). Для этого они перебирают все возможные скобочные последовательности длины x, где х - первая цифра секретной константы, использующейся во многих разработках компании. Если x нечётное, они просто прибавляют к нему единицу. Потом они используют продвинутые алгоритмы, использующие нейролингвистическое программирование и вычисленные по спирали Фибоначчи числа Каталана гуголдцатого порядка для определения местонахождения термов. Но эти алгоритмы уже реализованы и запатентованы. 

Ваша же задача - реализовать алгоритм перебора. 


Входные данные
На вход подаётся первая цифра секретной константы - x (\(1 <= x <= 9\)). 
 

Выходные данные
Нужно вывести все ПСП длины x (или x+1, если \(x \% 2 ==1\)) в лексикографическом порядке.

 

Примеры
№ Входные данные Выходные данные
1 1
( )
[ ]
{ }
Рекурсивный переборСтроки
✓ 8✗ 4501 200средняяВойти и решать
Тильда-омега-лямбда-исчисление#27311
Тильда-омега-лямбда-исчисление - ещё более инновационная разработка "British Scientists, Inc" в сфере функционального программирования. Его отличие от омега-лямбда-исчисления только в возможности ставить квадратные и фигурные скобки. Планировались также скобки в форме слоников, но стандарт ЮНИКОД у компании изменить не получилось. 
На вход подаётся тильда-омега-лямбда-выражение длиной не более 10^7 символов. Нужно вывести результат его тильда-иззи-редукции, работающей так же, как и иззи-редукция для омега-лямбда-выражений, но с учётом квадратных и фигурных скобок.

Напомним, иззи-редукция - одна из операций над такими выражениями. При её выполнении проверяется, является ли скобочная последовательность в выражении правильной. Термы при этом игнорируются. Если последовательность правильная - она превращается в терм gg, если нет - в терм wp. 
 

 

Примеры
№ Входные данные Выходные данные
1 main{izzy[lol](ttt)} gg
Конечные автоматыСтроки
✓ 96✗ 43500лёгкаяВойти и решать
27309#27309
Вы должны реализовать алгоритм или структуру данных, эффективно реализующих следующие запросы:
1)Добавление в массив элемента
2)Извлечение k-того по величине элемента массива (первым по величине будет считаться наименьший элемент)
Гарантируется, что каждый элемент встречается в массиве всего один раз
 
Входные данные:
В первой строке указано натуральное число n, за ним следует n целых чисел. 
Далее вводится натуральное m - количеств запросов.
В каждой из следующих m строк содержится слово "add" или "get" и целое число k.
Все численные значения по модулю не превосходят 1000. 
В первом случае вы должны дополнить массив элементом со значением k. Иначе - вывести k-тый элемент отсортированного текущего массива (индексация с единицы).
 
Выходные даннные: 
Вы должны ответить на запрос извлечения k-того элемента массива, а именно вывести его значение на экран.

(c) Ибрахим Ахмад, 2017
Двоичное дерево поискаПорядковые статистики
✓ 0✗ 41 300средняяВойти и решать
Хакер#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] является тандемным префиксом.
 
Входные данные
В первой строке дана строка, состоящая из строчных латинских букв. Длина строки не превышает 105.
 
Выходные данные
Выведите ответ, если он существует. Иначе выведите -1.
 
Ввод Вывод
abcabac aba

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

(с) Курбатов Е., 2017
Z-функция. Префикс-функциястроковые суфф. структуры
✓ 1✗ 91 300средняяВойти и решать
Кедор и Гихаил#27305
Меллерт Гихаил сегодня был в прекрасном настроении до того, как его одноклассник Фусков Кедор не заговорил о политике. Гихаил очень сильно разозлился, поэтому придумал задачу по информатике для Кедора, чтобы тот начал решать и наконец-то заткнулся. 
Задача была такая:  “Существует n логических функций, которые зависят от одного и того же множества переменных. Даны n чисел, битовое представление которых определяет таблицу истинности для каждой функции. Вам необходимо найти такой порядок расположения функций, чтобы из каждой функции логически следовала любая из последующих или сказать, что это  невозможно. Если ответ существует, то необходимо найти лексикографически минимальный порядок. Можно показать, что размер множества переменных, от которого зависят функции, не влияет на решение задачи”.
 Кедор – ваш лучший друг, а Гихаил – заклятый враг, поэтому вы решили помочь с решением задачи, а затем вместе с Кедором возобновить разговоры о политике, чтобы Гихаил от злости улетел на Луну.
 
Входные данные
В первой строке дано число n (1 <= n <= 10) – кол-во функций. 
Во второй строке дано n чисел в диапазоне [0; 10^9] – таблицы истинности функций, переведенные в десятичную систему счисления. 
Выходные данные
Если порядок существует, в первой строке выведите “YES”, во второй лексикографически минимальную перестановку из всех возможных. Если порядка нет, то выведите “NO”.

Пример
Ввод Вывод
3
3 1 7
 YES
2 1 3
2
1 2
NO
 

(с)  Курбатов Е., 2017
 
битмаскиПереборРазбор случаев
✓ 3✗ 171 200средняяВойти и решать
Building a Ski Course#27301
Фермер Джон помогает превратить его большое поле в лыжный маршрут для предстоящих Му-олимпийских игр. Поле имеет размеры M x N (1 <= M,N <=100) и его целевое финальное состояние описывается решеткой из M x N символов таких как:
 
RSRSSS
RSRSSS
RSRSSS
 
Каждый символ описывает состояние снега на этом участке R – грубый, S – гладкий (организаторы считают, что в таком случае - чередования грубых и гладких участков, гонка будет интересней).
 
Для выполнения этой задачи ФД планирует модифицировать свой трактор так, чтобы тот мог «отштамповать» любой фрагмент размером B x B (B<=M,B<=N) грубым снегом или гладким снегом.
ФД хочет сделать B как можно большим. С B=1 он может подготовить поле, штампуя индивидуально квадраты в соответствии с заданным финальным состоянием. Однако для бОльших значений B может оказаться невозможным выполнить задачу. Каждый квадрат поля должен быть обработан трактором. Невозможно оставить ячейку поля в исходном состоянии.
 
Помогите ФД определить максимально возможное значение B, которое он сможет успешно использовать.
 
INPUT FORMAT:
 
* Строка 1: Два разделённых пробелом целых числа M и N.
 
* Строки 2..M+1: M строк ровно по N символов (каждый R или S),
        описывающих желаемое финальное состояние поля.

 
OUTPUT FORMAT:
 
* Строка 1: Максимальное значение B, которое ФД может использовать, чтобы создать нужное поле.
 
 
Ввод Вывод
3 6
RSRSSS
RSRSSS
RSRSSS
 3


 
OUTPUT DETAILS:
 
ФД может отштамповать R колонках 1-3, затем S в колонках 2-4, затем R в колонках 3-5, и наконец,  S в колонках 4-6.
 
Двумерные массивыКонструктив
✓ 0✗ 41 200средняяВойти и решать
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.
Все позиции коров уникальны (-109 <= x, x <= 109). Кроме того, -109 <= A, B <= 109 и -1018 <= C <= 1018. Никогда не будет изгороди с 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≤105, 1≤K≤100, 1≤S≤N, 1≤F≤N.
 
Далее идет M строк, задающих расписание авиарейсов. i-я строка содержит три натуральных числа: Si, Fi и Pi, где Si - номер города, из которого вылетает i-й рейс, Fi - номер го-рода, в который прилетает i-й рейс, Pi - стоимость перелета i-м рейсом. 1≤Si≤N, 1≤Fi≤N, 1≤Pi≤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 рейсов электричек. Описание каждого рейса электрички начинается с числа Ki (2 ≤ K ≤ N) — количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе — время, когда электричка останавливается на этой станции (время выражается целым числом из диапазона от 0 до 109). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.
 
Формат выходных данных
Выведите одно число — минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите –1.
 
Алгоритм Дейкстры
✓ 167✗ 174700средняяВойти и решать
Поделиться
Класснуть