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

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

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

Задача 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. Выводится одна строка — результат анализа.
Примеры

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