Задачки по программированию

question

Тут я хочу собирать интересные, на мой взгляд задачи, из разных предметных областей

Примеры задач, которые часто встречаются на олимпиадах по программированию (школьные, ICPC-стиль, региональные этапы):

Задача: Чётное или нечётное Дано целое число N. Определить, является ли оно чётным.

Усложнение: Вывести "YES", если число делится и на 2, и на 3.

Задача: Второй максимум Дан массив из N чисел. Найти второй по величине элемент.

Усложнение: Сделать за O(N) без сортировки.

Задача: Пара с заданной суммой Дан отсортированный массив и число K. Найти, есть ли пара чисел с суммой K.

Сложность: O(N)

Задача: Поиск корня Дано число X. Найти sqrt(X) с точностью 10^-6.

Идея: бинарный поиск по вещественным числам.

Задача: Кузнечик Кузнечик прыгает по клеткам от 1 до N. Может прыгать на 1 или 2 клетки. Сколькими способами он может добраться до клетки N?

(Это классическая задача, сводится к числам Фибоначчи.)

Задача: Проверка связности Дан неориентированный граф. Проверить, является ли он связным.

Алгоритм: DFS или BFS.

Задача: Минимальный путь Дан взвешенный граф без отрицательных рёбер. Найти кратчайшее расстояние от вершины S до всех остальных.

Алгоритм: Дейкстра.

Задача: Анаграммы Даны две строки. Определить, являются ли они анаграммами.

Задача: Быстрое возведение в степень Вычислить a^b mod m, где a, b, m до 10^18.

Алгоритм: бинарное возведение в степень.

Задача: Отрезки Дано N отрезков на прямой. Найти количество пар пересекающихся отрезков.

Решение: сортировка + sweep line + структуры данных (Fenwick / segment tree).

Keyboard shortcuts