Задачи из книги “Олимпиадные задачи по программированию”
Ф. Меньшиков

Первая тренировка

содержание задачника

Задача 1А. Простые числа

Вывести все простые числа от \(M\) до \(N\) включительно.
Ограничения: \(2\le M\le N\le 300000\), время 6 с.
Ввод из файла primes.in. В первой строке находятся разделенные пробелом \(M\) и \(N\).
Вывод в файл primes.out. Вывести числа в порядке возрастания, по одному в строке. Если между \(M\) и \(N\) включительно нет простых – вывести “Absent”.
Примеры. Ввод 2 5 Вывод 2 3 5 Ввод 4 4 Вывод Absent

Задача 1B. Выражение

Даны N целых чисел Х₁, Х₂, …, X_N. Расставить между ними знаки «+» и «-» так, чтобы значение получившегося выражения было равно заданному целому S.
Ограничения: 2 \(\le\) N \(\le\) 24, 0 \(\le\) X_i \(\le\) 50 000 000, -1 000 000 000 \(\le\) S \(\le\) 1 000 000 000, время З с.
Ввод из файла expr.in. В первой строке находятся числа N и S.В следующей строке — N чисел через пробел.
Вывод в файл expr.out. Если получить требуемый результат невозможно, вывести «No solution», если можно — то вывести равенство. Если решение не единственное, то вывести любое.

Примеры
Ввод
3 10
15 25 30
Вывод 15+25-30=10
Ввод
2 100
10 10
Вывод No solution

Задача 1С. Возрастающая последовательность

Даны N целых чисел Х₁, Х₂, …, X_N. Требуется вычеркнуть из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.
Ограничения: 1 \(\le\) N\(\le\) 10 000, 1 \(\le\) X_i \(\le\) 60 000, время 4 с.
Ввод из файла incseq.in. В первой строке находится число N. В следующей строке — N чисел через пробел.
Вывод в файл incseq.out. В первой строке выводится количество невычеркнутых чисел, во второй — сами невычеркнутые числа через пробел в исходном порядке. Если вариантов несколько, вывести любой.
Пример
Ввод
6
2 5 3 4 6 1
Вывод
4
2 3 4 6

Задача 1D. Треугольник и точка

В декартовой системе координат на плоскости заданы координаты вершин треугольника и еще одной точки. Определить, принадлежит ли эта точка треугольнику.
Ограничения: координаты вершин — целые числа, для любой точки выполняются следующие условия: -10 000\(\le\)x, у \(\le\) 10 000, время 1 с.
Ввод из файла tria-pt.in. В четырех строках находятся пары чисел — координаты точек. Числа в первых трех строках — это координаты вершин треугольника, в четвертой строке — координаты тестируемой точки.
Вывод в файл tria-pt.out. Вывести слово In, если точка находится внутри треугольника, или Out — если снаружи.
Примеры

Задача 1E. Степень

Для натуральных чисел \(a\) и \(n\) вычислить \(a^n\).
Ограничения: 1 \(\le a\le\) 9, 1 \(\le n\le\) 7000, время 5 с.
Ввод из файла power.in. В первой строке находятся разделенные пробелом \(a\) и \(n\).
Вывод в файл power.out Выводится одно число — результат без стоящих впереди нулей, стоящих впереди и позади пробелов.
Примеры
Ввод 3 20 Вывод  3486784401
Ввод 5 50 Вывод 88817841970012523233890533447265625

Задача 1F. Покер

Даны пять целых чисел. Среди них:
• если одинаковы 5, то вывести «Impossible», иначе;
• если одинаковы 4, то вывести «Four of a Kind», иначе;
• если одинаковы 3 и 2, то вывести «Full House», иначе;
• если есть 5 последовательных, то вывести «Straight», иначе;
• если одинаковы 3, то вывести «Three of a Kind», иначе;
• если одинаковы 2 и 2, то вывести «Two Pairs», иначе;
• если одинаковы 2, то вывести One «Pair», иначе;
• вывести «Nothing».
Ограничения: все числа от 1 до 13 включительно, время 1 с.
Ввод из файла poker.in. В первой строке находятся пять чисел через пробел.
Вывод в файл poker.out. Выводится одна строка — результат анализа.
Примеры

содержание задачника