В данном разделе мы рассмотрим некоторые задачи, связанные с проблемой поиска информации. Это огромный класс задач, достаточно подробно описанный в классической литературе по программированию (см., например, книги Н.Вирта, Д. Кнута и другие).
Общий смысл задач поиска сводится к следующему: из данной информации, хранящейся в памяти ЭВМ, выбрать нужные сведения, удовлетворяющие определенным условиям (критериям).
Подобные задачи мы уже рассматривали. Например, поиск максимального числа в числовом массиве, поиск нужной записи в файле данных и т. п. Такой поиск осуществляется перебором всех элементов структуры данных и их проверкой на удовлетворение условию поиска. Перебор, при котором просматриваются все элементы структуры, называется полным перебором.
Полный перебор является «лобовым» способом поиска и, очевидно, не всегда самым лучшим.
Рассмотрим пример. В одномерном массиве X заданы координаты п точек, лежащих на вещественной числовой оси. Точки пронумерованы. Их номера соответствуют последовательности в массиве X. Определить номер первой точки, наиболее удаленной от начала координат.
Щелчок 2023 | Задание №19-21. Руками (Обзор задачи. Шаблон решения)
Легко понять, что это знакомая нам задача определения номера наибольшего по модулю элемента массива X. Она решается путем полного перебора следующим образом:
Полный перебор элементов одномерного массива производится с помощью одной циклической структуры.
А теперь такая задача: исходные данные — те же, что и в предыдущей; требуется определить пару точек, расстояние между которыми наибольшее.
Применяя метод перебора, эту задачу можно решать так: перебрать все пары точек из Ладанных и определить номера тех, расстояние между которыми наибольшее (наибольший модуль разности координат). Такой полный перебор реализуется через два вложенных цикла:
Очевидно, что такое решение задачи нерационально. Здесь каждая пара точек будет просматриваться дважды, например при i = 1, j = 2 и i = 2, j= 1. Для случая п = 100 циклы повторят выполнение 100 х 100 = 10000 раз.
Выполнение программы ускорится, если исключить повторения. Исключить также следует и случай совпадения значений i и j. Тогда число повторений цикла будет равно
. При n = 100 получается 4950.
Для исключения повторений нужно в предыдущей программе изменить начало внутреннего цикла с 1 на i +1. Программа примет вид:
Рассмотренный вариант алгоритма назовем перебором без повторений.
Замечание. Конечно, эту задачу можно было решить и другим способом, но в данном случае нас интересовал именно алгоритм, связанный с перебором. В случае точек, расположенных не на прямой, а на плоскости или в пространстве, поиск альтернативы такому алгоритму становится весьма проблематичным.
Щелчок 2023 | Задание №23 (все прототипы)
В следующей задаче требуется выбрать все тройки чисел без повторений, сумма которых равна десяти, из массива X.
В этом случае алгоритм будет строиться из трех вложенных циклов. Внутренние циклы имеют переменную длину.
For J:=I+1 To N Do
For K:=J+1 To N Do
А теперь представьте, что из массива Х требуется выбрать все группы чисел, сумма которых равна десяти. В группах может быть от 1 до п чисел. В этом случае количество вариантов перебора резко возрастает, а сам алгоритм становится нетривиальным.
Казалось бы, ну и что? Машина работает быстро! И все же посчитаем. Число различных групп из п объектов (включая пустую) составляет 2n. При п = 100 это будет 2100 ≈ 1030.
Компьютер, работающий со скоростью миллиард операций в секунду, будет осуществлять такой перебор приблизительно 10 лет. Даже исключение перестановочных повторений не сделает такой переборный алгоритм практически осуществимым.
Путь практической разрешимости подобных задач состоит в нахождении способов исключения из перебора бесперспективных с точки зрения условия задачи вариантов. Для некоторых задач это удается сделать с помощью алгоритма, описанного в следующем разделе.
Перебор с возвратом. Рассмотрим алгоритм перебора с возвратом на примере задачи о прохождении лабиринта (рис. 52).
Дан лабиринт, оказавшись внутри которого нужно найти выход наружу. Перемещаться можно только в горизонтальном и вертикальном направлениях. На рисунке показаны все варианты путей выхода из центральной точки лабиринта.
Для получения программы решения этой задачи нужно решить две проблемы:
• как организовать данные;
• как построить алгоритм.
Информацию о форме лабиринта будем хранить в квадратной матрице LAB символьного типа размером N x N, где N — нечетное число (чтобы была центральная точка). На профиль лабиринта накладывается сетка так, что в каждой ее ячейке находится либо стена, либо проход.
Матрица отражает заполнение сетки: элементы, соответствующие проходу, равны пробелу, а стене — какому-нибудь символу (например, букве М)
Путь движения по лабиринту будет отмечаться символами +.
Например, приведенный выше рисунок (в середине) соответствует следующему заполнению матрицы LAB:
Исходные данные — профиль лабиринта (исходная матрица LAB без крестиков); результат — все возможные траектории выхода из центральной точки лабиринта (для каждого пути выводится матрица LAB с траекторией, отмеченной крестиками).
Алгоритм перебора с возвратом еще называют методом проб.
Суть его в следующем:
1. Из каждой очередной точки траектории просматриваются возможные направления движения в одной и той же последовательности; договоримся, что просмотр будет происходить каждый раз против часовой стрелки — справа-сверху-слева-снизу; шаг производится в первую же обнаруженную свободную соседнюю клетку; клетка, в которую сделан шаг, отмечается крестиком.
2. Если из очередной клетки дальше пути нет (тупик), то следует возврат на один шаг назад и просматриваются еще не испробованные пути движения из этой точки; при возвращении назад покинутая клетка отмечается пробелом.
3. Если очередная клетка, в которую сделан шаг, оказалась на краю лабиринта (на выходе), то на печать выводится найденный путь.
Программу будем строить методом последовательной детализации. Первый этап детализации:
Процедура GO пытается сделать шаг в клетку с координатами х, у. Если эта клетка оказывается на выходе из лабиринта, то пройденный путь выводится на печать. Если нет, то в соответствии с установленной выше последовательностью делается шаг в соседнюю клетку. Если клетка тупиковая, то выполняется шаг назад. Из сказанного выше следует, что процедура носит рекурсивный характер.
Запишем сначала общую схему процедуры без детализации:
Для вывода найденных траекторий составляется процедура PRINTLAB.
В окончательном виде программа будет выглядеть так:
Еще один пример красивой программы с использованием рекурсивного определения процедуры (вспомните ханойскую башню!).
Схема алгоритма данной программы типична для метода перебора с возвратом. По аналогичным алгоритмам решаются, например, популярные задачи об обходе шахматной доски фигурами или о расстановке фигур на доске так, чтобы они «не били» друг друга; множество задач оптимального выбора (задачи о коммивояжере, об оптимальном строительстве дорог и т.п.).
Замечание. Из-за использования массива LAB в качестве параметра-значения в процедуре GO могут возникнуть проблемы с памятью при реализации программы на ЭВМ. В таком случае можно перейти к глобальной передаче массива.
Источник: studfile.net
Сложность алгоритмов перебора
Большим классом задач, которые часто решаются на компьютере, являются задачи поиска. Одну из таких задач мы уже рассматривали: поиск максимального элемента в массиве. Общий смысл задач поиска сводится к следующему: из множества данных, хранящихся в памяти компьютера, требуется выбрать нужные данные, удовлетворяющие определенным условиям (критериям). Такой поиск осуществляется перебором всех элементов структуры данных и их проверкой на удовлетворение условию поиска. Перебор, при котором просматриваются все элементы структуры, называется полным перебором.
На примере алгоритма поиска максимального элемента мы знаем, что полный перебор элементов одномерного массива производится с помощью одного цикла, число повторений которого пропорционально размеру массива.
Рассмотрим другой пример. В одномерном массиве X заданы координаты N точек, произвольно расположенных на вещественной числовой оси. Точки пронумерованы. Их номера соответствуют номерам элементов в массиве X. Нужно определить пару точек, расстояние между которыми наибольшее.
Применяя метод перебора, эту задачу можно решать так: перебрать все пары точек из N данных и определить номера тех точек, расстояние между которыми наибольшее (наибольший модуль разности координат). Такой полный перебор реализуется через два вложенных цикла:
for i:=l to N do
for j:= i+1 to N do
if Abs(X[i] — X[j]) > Abs(X[Numberl] — X[Number2])
Then
Begin
end;
Но очевидно, что такое решение задачи нерационально. Здесь каждая пара точек будет просматриваться дважды, например при i — 1, j = 2 и i = 2, j =1. Для случая N = 100 циклы повторят выполнение 100 • 100 = 10 000 раз.
Выполнение программы ускорится, если исключить повторения. Исключить также следует и совпадения значений i и j. Для исключения повторений нужно в предыдущей программе изменить начало внутреннего цикла с 1 на i + 1. Программа примет вид:
for i:=l to N do
for j:=i + 1 to N do
if Abs(X[i] — X[j]) >Abs(X[Numberl] — X[Number2])
Then
Begin
end;
В таком алгоритме число повторений цикла будет равно N(N — 1)/2. При N = 100 получается 4950. Рассмотренный вариант алгоритма назовем перебором без повторений.
Замечание. Конечно, эту задачу можно было решить и другим способом, но в данном случае нас интересовал именно переборный алгоритм. В случае же точек, расположенных не на прямой, а на плоскости или в пространстве, поиск альтернативы переборному алгоритму становится весьма проблематичным.
В следующей задаче требуется выбрать из массива X без повторений все тройки чисел, сумма которых равна десяти. В этом случае алгоритм будет строиться из трех вложенных циклов. Внутренние циклы имеют переменную длину.
for i:= 1 to N do
for j:= i + 1 to N do
for k:= j + 1 to N do
if X[i] + X[j] + X[k] = 10
then writeln(X[i], X[j], X[k]);
А теперь представьте, что из массивах требуется выбрать всевозможные группы чисел, сумма которых равна десяти. Количество чисел в группах может быть любым — от 1 до N. В этом случае количество вариантов перебора резко возрастает, а сам алгоритм становится нетривиальным.
Казалось бы, ну и что? Компьютер работает быстро! И все же посчитаем. Число различных групп из N объектов (включая пустую) составляет 2 N . При N = 100 это будет 2 100 ≈ 10 30 . Компьютер, работающий со скоростью миллиард операций в секунду, будет осуществлять такой перебор приблизительно 10 лет. Даже исключение перестановочных повторений не сделает такой переборный алгоритм практически осуществимым.
Путь практической разрешимости подобных задач состоит в нахождении способов исключения из перебора бесперспективных с точки зрения условия задачи вариантов. Для некоторых задач это удается сделать. К таким задачам относится задача поиска выхода из лабиринта, задача о восьми ферзях (расставить на шахматной доске восемь ферзей так, чтобы они не угрожали друг другу). Если бы шахматные программы составлялись методом полного перебора всевозможных ходов, то ни один суперкомпьютер не смог бы в реальном времени играть в шахматы. Очевидно, что в алгоритме программы заложены знания стратегии и тактики игры в шахматы, которыми владеют сильнейшие шахматисты, что существенно сокращает перебор возможных ходов.
Впечатляющим примером решения фундаментальной математической проблемы методом поиска является Проект GIMPS (Great Internet Mersenne Prime Search), направленный на поиск простых чисел Мерсенна — последовательности чисел, подчиняющихся закону 2 p -1, где р – простое число. В ноябре 2001 года в рамках данного проекта было найдено число Мерсенна, содержащее в своей десятичной записи более 4 млн цифр. Десятки тысяч компьютеров по всему миру, отдавая часть своих вычислительных ресурсов, работали над этой задачей два с половиной года.
Коротко о главном
В программировании используются два критерия сложности алгоритма: объемная сложность и временная сложность.
Объемная сложность связана с количеством данных, которые при обработке нужно хранить в оперативной памяти.
Временная сложность связана с количеством операций, выполняемых процессором в течение работы программы; количество операций пропорционально времени выполнения программы.
Временная сложность оценивается как функция зависимости числа операций от объема данных и может быть линейной, квадратичной и пр.
Задача перебора: из множества данных, хранящихся в памяти компьютера, требуется выбрать нужные данные, удовлетворяющие определенным условиям (критериям).
Временная сложность полного перебора может привести к превышению разумного времени выполнения программы на компьютере.
Оптимизация алгоритма перебора состоит в исключении анализа бесперспективных вариантов.
Вопросы и задания
1. Почему временная сложность алгоритма зависит от его объемной сложности?
2. Составьте алгоритм поиска для следующей задачи: на координатной плоскости заданы своими координатами N точек. Найти две самые удаленные друг от друга точки. Оцените временную сложность алгоритма. Рассмотрите два варианта алгоритма: с полным и с неполным перебором и сравните их.
3. Составьте алгоритм для решения задачи, аналогичной предыдущей, с учетом того что точки расположены в трехмерном пространстве.
Источник: cyberpedia.su
Динамическое программирование. Классические задачи
Здравствуй, Хабрахабр. В настоящий момент я работаю над учебным пособием по олимпиадному программированию, один из параграфов которого посвящен динамическому программированию. Ниже приведена выдержка из данного параграфа. Пытаясь объяснить данную тему как можно проще, я постарался сложные моменты сопроводить иллюстрациями.
Мне интересно ваше мнение о том, насколько понятным получился данный материал. Также буду рад советам, какие еще задачи стоит включить в данный раздел.
Во многих олимпиадных задачах по программированию решение с помощью рекурсии или полного перебора требует выполнения очень большого числа операций. Попытка решить такие задачи, например, полным перебором, приводит к превышению времени выполнения.
Однако среди переборных и некоторых других задач можно выделить класс задач, обладающих одним хорошим свойством: имея решения некоторых подзадач (например, для меньшего числа n), можно практически без перебора найти решение исходной задачи.
Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.
Последовательности
Классической задачей на последовательности является следующая.
Последовательность Фибоначчи Fn задается формулами: F1 = 1, F2 = 1,
Fn = Fn – 1 + Fn – 2 при n > 1. Необходимо найти Fn по номеру n.
Один из способов решения, который может показаться логичным и эффективным, — решение с помощью рекурсии:
int F(int n)
Используя такую функцию, мы будем решать задачу «с конца» — будем шаг за шагом уменьшать n, пока не дойдем до известных значений.
Но как можно заметить, такая, казалось бы, простая программа уже при n = 40 работает заметно долго. Это связано с тем, что одни и те же промежуточные данные вычисляются по несколько раз — число операций нарастает с той же скоростью, с какой растут числа Фибоначчи — экспоненциально.
Один из выходов из данной ситуации — сохранение уже найденных промежуточных результатов с целью их повторного использования:
int F(int n) < if (A[n] != -1) return A[n]; if (n < 2) return 1; else < A[n] = F(n — 1) + F(n — 2); return A[n]; >>
Приведенное решение является корректным и эффективным. Но для данной задачи применимо и более простое решение:
F[0] = 1; F[1] = 1; for (i = 2; i < n; i++) F[i] = F[i — 1] + F[i — 2];
Такое решение можно назвать решением «с начала» — мы первым делом заполняем известные значения, затем находим первое неизвестное значение (F3), потом следующее и т.д., пока не дойдем до нужного.
Именно такое решение и является классическим для динамического программирования: мы сначала решили все подзадачи (нашли все Fi для i < n), затем, зная решения подзадач, нашли ответ (Fn = Fn – 1 + Fn – 2, Fn – 1 и Fn – 2 уже найдены).
Одномерное динамическое программирование
Чтобы лучше понять суть динамического программирования, сначала более формально определим понятия задачи и подзадачи.
Пусть исходная задача заключается в нахождении некоторого числа T при исходных данных n1, n2, . nk. То есть мы можем говорить о функции T(n1, n2, . nk), значение которой и есть необходимый нам ответ. Тогда подзадачами будем считать задачи
T(i1, i2, . ik) при i1 < n1, i2 < n2, . ik < nk.
Далее мы будем о говорить об одномерном, двумерном и многомерном динамическом программировании при k = 1, k = 2, k > 2, соответственно.
Следующая задача одномерного динамического программирования встречается в различных вариациях.
Задача 1. Посчитать число последовательностей нулей и единиц длины n, в которых не встречаются две идущие подряд единицы.
При n = 1, n = 2 ответ очевиден. Допустим, что мы уже нашли Kn – 1, Kn – 2 — число таких последовательностей длины n – 1 и n – 2.
Посмотрим, какой может быть последовательность длины n. Если последний ее символ равен 0, то первые n – 1 — любая правильная последовательность длины
n – 1 (не важно, заканчивается она нулем или единицей — следом идет 0). Таких последовательностей всего Kn – 1. Если последний символ равен 1, то предпоследний символ обязательно должен быть равен 0 (иначе будет две единицы подряд), а первые
n – 2 символа — любая правильная последовательность длины n – 2, число таких последовательностей равно Kn – 2.
Таким образом, K1 = 2, K2 = 3, Kn = Kn – 1 + Kn – 2 при n > 2. То есть данная задача фактически сводится к нахождению чисел Фибоначчи.
Двумерное динамическое программирование
Классической задачей двумерного динамического программирования является задача о маршрутах на прямоугольном поле.
В разных формулировках необходимо посчитать число маршрутов или найти маршрут, который является лучшим в некотором смысле.
Приведем пару формулировок таких задач:
Задача 2. Дано прямоугольное поле размером n*m клеток. Можно совершать шаги длиной в одну клетку вправо или вниз. Посчитать, сколькими способами можно попасть из левой верхней клетки в правую нижнюю.
Задача 3. Дано прямоугольное поле размером n*m клеток. Можно совершать шаги длиной в одну клетку вправо, вниз или по диагонали вправо-вниз. В каждой клетке записано некоторое натуральное число. Необходимо попасть из верхней левой клетки в правую нижнюю. Вес маршрута вычисляется как сумма чисел со всех посещенных клеток.
Необходимо найти маршрут с минимальным весом.
Для всех таких задач характерным является то, что каждый отдельный маршрут не может пройти два или более раз по одной и той же клетке.
Рассмотрим более подробно задачу 2. В некоторую клетку с координатами (i,j) можно прийти только сверху или слева, то есть из клеток с координатами (i – 1, j) и (i, j – 1):
Таким образом, для клетки (i, j) число маршрутов A[i][j] будет равно
A[i – 1][j] + A[i][j – 1], то есть задача сводится к двум подзадачам. В данной реализации используется два параметра — i и j — поэтому применительно к данной задаче мы говорим о двумерном динамическом программировании.
Теперь мы можем пройти последовательно по строкам (или по столбцам) массива A, находя число маршрутов для текущей клетки по приведенной выше формуле. Предварительно в A[0][0] необходимо поместить число 1.
В задаче 3 в клетку с координатами (i, j) мы можем попасть из клеток с координатами
(i – 1, j), (i, j – 1) и (i – 1, j – 1). Допустим, что для каждой из этих трех клеток мы уже нашли маршрут минимального веса, а сами веса поместили в W[i – 1][j], W[i][j – 1],
W[i – 1][j – 1]. Чтобы найти минимальный вес для (i, j), необходимо выбрать минимальный из весов W[i – 1][j], W[i][j – 1], W[i – 1][j – 1] и прибавить к нему число, записанное в текущей клетке:
W[i][j] = min(W[i–1][j], W[i][j – 1], W[i – 1][j – 1]) + A[i][j];
Данная задача осложнена тем, что необходимо найти не только минимальный вес, но и сам маршрут. Поэтому в другой массив мы дополнительно для каждой клетки будем записывать, с какой стороны в нее надо попасть.
На следующем рисунке приведен пример исходных данных и одного из шагов алгоритма.
В каждую из уже пройденных клеток ведет ровно одна стрелка. Эта стрелка показывает, с какой стороны необходимо прийти в эту клетку, чтобы получить минимальный вес, записанный в клетке.
После прохождения всего массива необходимо будет проследить сам маршрут из последней клетки, следуя по стрелкам в обратную сторону.
Задачи на подпоследовательности
Рассмотрим задачу о возрастающей подпоследовательности.
Задача 4. Дана последовательность целых чисел. Необходимо найти ее самую длинную строго возрастающую подпоследовательность.
Начнем решать задачу с начала — будем искать ответ, начиная с первых членов данной последовательности. Для каждого номера i будем искать наибольшую возрастающую подпоследовательность, оканчивающуюся элементом в позиции i. Пусть исходная последовательность хранится в массиве A. В массиве L будем записывать длины максимальных подпоследовательностей, оканчивающихся текущим элементом. Пусть мы нашли все L[i] для 1 i k – 1. Теперь можно найти L[k] следующим образом. Просматриваем все элементы A[i] для 1 i < k – 1. Если
A[i] < A[k], то k-ый элемент может стать продолжением подпоследовательности, окончившейся элементом A[i]. Длина полученной подпоследовательности будет на 1 больше L[i]. Чтобы найти L[k], необходимо перебрать все i от 1 до k – 1:
L[k] = max(L[i]) + 1, где максимум берется по всем i таким, что A[i] < A[k] и
1 i < k.
Здесь максимум из пустого множества будем считать равным 0. В этом случае текущий элемент станет единственным в выбранной последовательности, а не будет продолжением одной из предыдущих. После заполнения массива L длина наибольшей возрастающей подпоследовательности будет равна максимальному элементу L.
Чтобы восстановить саму подпоследовательность, можно для каждого элемента также сохранять номер предыдущего выбранного элемента, например, в массив N.
Рассмотрим решение этой задачи на примере последовательности 2, 8, 5, 9, 12, 6. Поскольку до 2 нет ни одного элемента, то максимальная подпоследовательность содержит только один элемент — L[1] = 1, а перед ним нет ни одного — N[1] = 0. Далее,
2 < 8, поэтому 8 может стать продолжением последовательности с предыдущим элементом. Тогда L[2] = 2, N[2] = 1.
Меньше A[3] = 5 только элемент A[1] = 2, поэтому 5 может стать продолжением только одной подпоследовательности — той, которая содержит 2. Тогда
L[3] = L[1] + 1 = 2, N[3] = 1, так как 2 стоит в позиции с номером 1. Аналогично выполняем еще три шага алгоритма и получаем окончательный результат.
Теперь выбираем максимальный элемент в массиве L и по массиву N восстанавливаем саму подпоследовательность 2, 5, 9, 12.
Еще одной классической задачей динамического программирования является задача о палиндромах.
Задача 5. Дана строка из заглавных букв латинского алфавита. Необходимо найти длину наибольшего палиндрома, который можно получить вычеркиванием некоторых букв из данной строки.
Начнем решать задачу с самых простых подстрок. Для строки из одного символа (то есть подстроки вида S(i, i)) ответ очевиден — ничего вычеркивать не надо, такая строка будет палиндромом. Для строки из двух символов S(i, i + 1) возможны два варианта: если символы равны, то мы имеем палиндром, ничего вычеркивать не надо. Если же символы не равны, то вычеркиваем любой.
Пусть теперь нам дана подстрока S(i, j). Если первый (S[i]) и последний (S[j]) символы подстроки не совпадают, то один из них точно нужно вычеркнуть. Тогда у нас останется подстрока S(i, j – 1) или S(i + 1, j) — то есть мы сведем задачу к подзадаче: L[i][j] = max(L[i][j – 1], L[i + 1][j]). Если же первый и последний символы равны, то мы можем оставить оба, но необходимо знать решение задачи S(i + 1, j – 1):
L[i][j] = L[i + 1][j – 1] + 2.
Рассмотрим решение на примере строки ABACCBA. Первым делом заполняем диагональ массива единицами, они будут соответствовать подстрокам S(i, i) из одного символа. Затем начинаем рассматривать подстроки длины два. Во всех подстроках, кроме S(4, 5), символы различны, поэтому в соответствующие ячейки запишем 1, а в L[4][5] — 2.
Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали, ведущей из левого верхнего угла в правый нижний. Для подстрок длины 3 получаются следующие значения: в подстроке ABA первая и последняя буквы равны, поэтому
L[1][3] = L[2][2] + 2. В остальных подстроках первая и последняя буквы различны.
BAC: L[2][4] = max(L[2][3], L[3][4]) = 1.
ACC: L[3][5] = max(L[3][4], L[4][5]) = 2.
CCB: L[4][6] = max(L[4][5], L[5][6]) = 2.
CBA: L[5][7] = max(L[5][6], L[6][7]) = 1.
Продолжая далее аналогичные рассуждения, заполним все ячейки под диагональю и в ячейке L[1][7] = 6 получим ответ.
Если же в задаче необходимо вывести не длину, а сам палиндром, то дополнительно к массиву длин мы должны построить массив переходов — для каждой ячейки запомнить, какой из случаев был реализован (на рисунке для наглядности вместо числовых значений, кодирующих переходы, нарисованы соответствующие стрелки).
- динамическое программирование
- спортивное программирование
- олимпиадные задачи
Источник: habr.com