Задачи из книги "Олимпиадные задачи по программированию"
Ф. Меньшиков
Первая тренировка
Задача 1А. Простые числа
Вывести все простые числа от до
включительно.
Ограничения: , время 6 с.
Ввод из файла primes.in. В первой строке находятся разделенные пробелом и
.
Вывод в файл primes.out. Вывести числа в порядке возрастания, по одному в строке. Если между и
включительно нет простых - вывести "Absent".
Примеры. Ввод 2 5 Вывод 2 3 5 Ввод 4 4 Вывод Absent
Задача 1B. Выражение
Даны N целых чисел Х1, Х2, ..., XN. Расставить между ними знаки «+» и «-» так, чтобы значение получившегося выражения было равно заданному целому S.
Ограничения: 2 N
24, 0
Xi
50 000 000, -1 000 000 000
S
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 целых чисел Х1, Х2, ..., XN. Требуется вычеркнуть из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.
Ограничения: 1 N
10 000, 1
Xi
60 000, время 4 с.
Ввод из файла incseq.in. В первой строке находится число N. В следующей строке — N чисел через пробел.
Вывод в файл incseq.out. В первой строке выводится количество невычеркнутых чисел, во второй — сами невычеркнутые числа через пробел в исходном порядке. Если вариантов несколько, вывести любой.
Пример
Ввод
6
2 5 3 4 6 1
Вывод
4
2 3 4 6
Задача 1D. Треугольник и точка
В декартовой системе координат на плоскости заданы координаты вершин треугольника и еще одной точки. Определить, принадлежит ли эта точка треугольнику.
Ограничения: координаты вершин — целые числа, для любой точки выполняются следующие условия: -10 000x, у
10 000, время 1 с.
Ввод из файла tria-pt.in. В четырех строках находятся пары чисел — координаты точек. Числа в первых трех строках — это координаты вершин треугольника, в четвертой строке — координаты тестируемой точки.
Вывод в файл tria-pt.out. Вывести слово In, если точка находится внутри треугольника, или Out — если снаружи.
Примеры
Ввод 1 | Ввод 2 | Ввод 3 | Ввод 4 |
0 0 | 0 0 | 0 0 | 0 0 |
100 0 | 100 0 | 100 0 | 100 0 |
0 100 | 0 100 | 0 100 | 0 100 |
100 100 | 10 10 | 50 50 | 0 0 |
Вывод 1 Out | Вывод 2 In | Вывод 3 In | Вывод 4 In |
Задача 1E. Степень
Для натуральных чисел и
вычислить
.
Ограничения: 1 9, 1
7000, время 5 с.
Ввод из файла power.in. В первой строке находятся разделенные пробелом и
.
Вывод в файл 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. Выводится одна строка — результат анализа.
Примеры
Ввод 1 | Ввод 2 | Ввод 3 | Ввод 4 |
1 3 9 3 2 | 1 5 5 4 4 | 1 5 2 4 3 | 10 11 12 13 1 |
Вывод 1 | Вывод 2 | Вывод 3 | Вывод 4 |
One Pair | Two Pairs | Straight | Nothing |