Раздел «Алгоритмы».OlimpiadMinimum:

Теоретический и практический минимум для участия в олимпиадах

Во всех задачах: входной файл: input.txt выходной файл: output.txt ограничение времени: 5 сек

1. Длинная арифметика на натуральных числах вход: два длинных числа (первое число не меньше второго)<=10^200 выход: результат их сложения, вычитания, умножения, деления (частное и остаток) Рекомендуемое время: 15 мин

2. Длинная арифметика на целых числах вход: два длинных числа (первое число не меньше второго)<=10^200 выход: результат их сложения, вычмтания, умножения Рекомендуемое время: 15 мин

3. Быстрая сортировка вход: 1<=n<=10^5, массив из n чисел (extended) выход: отсортированный массив Рекомендуемое время: 3 мин

4. Комбинаторика: n! вход: 1<=n<=10; далее n пар целых чисел (по модулю <=30000) - координаты вершин на плоскости. выход: минимальная длина цикла, содержащего все вершины. Рекомендуемое время: 5 мин

5. Треугольники вход: 1<=n<=9, далее 6*n целых числа - координаты точек на плоскости. выход: минимальная площадь и далее тройки номеров точек, составляющих треугольник. Рекомендуемое время: 30 мин

6. Комбинаторика: С(n,k) вход: числа 1<=n<=25, 1<=k<=n. Далее идут (n+1) пара целых чисел (по модулю <=30000) - координаты точек на плоскости. Выбрать из первых n точек k так, чтобы сумма кубов расстояний от них до (n+1)-й было минимально. выход: номера выбранных точек в исходном множестве. Рекомендуемое время: 5 мин

7. Комбинаторика: 2^n вход: 1<=n<=25. Далее идут n натуральных чисел, не превосходящих 30000. Как нужно расставить знаки (+/-) между ними, чтобы полученная сумма была минимальна? выход: строка из (n-1) символа: + или - Рекомендуемое время: 5 мин

8. Пересечение отрезков вход: 8 целых чисел - координаты начал и концов отрезков. выход: в первой строке - YES или NO - есть пересечение или нет соотвественно, во второй строке - координаты точки пересечения с точностью до 10^-5. Рекомендуемое время: 5 мин

9. Пересечение выпуклых многоугольников вход: 1<=n,m<=100 - число вершин в многоугольниках. Далее идут целочисленные координаты вершин многоугольников, в порядке обхода против часовой стрелки. выход: k - количество вершин в многоугольнике-пересечении, далее - координаты вершин в порядке обхода против часов стрелки. Рекомендуемое время (с использованием решения предыдущей задачи): 10 мин

10. Выпуклая оболочка вход: 1<=n<=1000 - количество точек. Далее идут координаты этих точек (integer). выход: номера точек, входящих в выпуклую оболочку, в порядке обхода против часовой стрелки, а также площадь выпуклой оболочки. Рекомендуемое время: 10 мин

11. Калькулятор вход: строка-выражение (длиной не более 1000), состоящее из целых чисел и символов: +, -, *, /, (, ). Унарный минус разрешен. Гарантируется longint во время вычислений. выход: результат вычислений. В случае невозможности вычислений оставить выходной файл пустым. Рекомендуемое время: 15 мин

В нижеследующих задачах слова "граф задан списками смежности" означают, что задано число его вершин (n<=100), далее идут списки смежности для каждой вершины (число смежных вершин) и далее сами номера вершин. "Граф задан списком ребер" означает, что заданы два числа: n - число вершин, m - число ребер, а далее - описания ребер (номера начальной и конечной вершин, возможно, его вес, пропускная способность).

12. Поиск в ширину вход: ориентированный граф задан списками спежности. Даны номера начальной и конечной вершин. Найти кратчайший путь между ними. выход: длина кратчайшего пути (если пути не существует, вывести -1), далее номера вершин, входящих в путь. Рекомендуемое время: 5 мин

13. Поиск в глубину вход: неориентированный граф задан списками смежности. выход: вывести в первую строку число компонент связности,во вторую - является ли граф лесом (YES) или нет (NO), в третью - является ли граф двудольным (YES) или нет (NO). Рекомендуемое время: 5 мин

14. Поиск циклов вход: ориентированный граф задан списками смежности. выход: число циклов далее сами циклы в формате: число вершин в цикле, вершины, входяцие в цикл в порядке обхода. Рекомендуемое время: 5 мин

15. Мосты и точки раздела. вход: неориентированный граф задан списками смежности. выход: число мостов, далее сами мосты, заданные номера вершин; число точек раздела, далее сами точки раздела. Рекомендуемое время: 10 мин

16. Кратчайший путь вход: неориентированный граф задан списком ребер с указание веса каждого ребра (положительное целое число). Далее задаются номера начальной и конечной вершин. выход: длина кратчайшего пути (если пути нет, то вывести -1), далее число вершин, входящих в путь, и номера вершин. Рекомендуемое время: 10 мин

17. Кратчайший путь между каждой парой вершин. вход: неориентированный граф задан списком ребер с весами. выход: матрица nxn, элемент (i,j) которой - длина кратчайшего пути между i-ой и j-ой вершинами. Рекомендуемое время: 5 мин

18. Минимальное остовное дерево. вход: граф задан списком ребер с весами. выход: в первую строку выведите YES, если остовное дерево существует и NO в противном случае. Далее выведите ребра, входящие в минимальное остовное дерево, заданные номерами вершин. Рекомендуемое время: 15 мин

19. Максимальное паросочетание вход: двудольный граф в виде: число вершин в левой доле, число вершин в правой доле, число ребер. Далее ребра в виде: номер вершины в левой доле, номер вершины в правой доле. выход: число ребер в максимальном паросочестании, далее сами ребра с указанием соединяющих вершин. Рекомендуемое время: 15 мин

20. Максимальный поток вход: ориентированный граф задан списком ребер с указанием пропускной способности. выход: величина максимального потока Рекомендуемое время: 25 мин


Bonus pack

1. Бинарная куча без Кормена. Вход. - по задаче Рекомендуемое время: 3 мин

1+. Бинарная куча без Кормена с удалением по значению. Вход. - по задаче Рекомендуемое время: 6 мин

2. Красно-черное дерево Рекомендуемое время: 25 мин

3. Структура Румянцева Рекомендуемое время: 25 мин

4. Декартово дерево (структура Наливайко) Рекомендуемое время: 20 мин

5. Перебор всех вариантов Рекомендуемое время: ~25 мин

6. Гамильтонов путь самым быстрым алгоритмом. Рекомендуемое время: 15-35 мин (в зависимости от алгоритма)

7. acm.uva.es Рекомендуемое время: 1-2 месяца