на первую страницу

ЗАДАЧИ ДЛЯ ПРАКТИКИ

1. Сортировка и поиск последовательностей чисел
2. Поиск и подсчет подмножеств
3. Геометрия
4. Теория графов
5. Элементарная алгебра
6. Логика и синтаксический анализ

Сортировка и поиск последовательностей чисел

Задача 1.1. Четные - нечетные последовательности
Составитель В. Тарасов
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
Пусть задана последовательность из n (n Ј 100) целых чисел {a1, a2, ..., an} (1 Ј ai Ј 100), которая содержит m четных чисел и l - нечетных (m + l = n). Требуется получить последовательность из k пар (k = min(m, l)) {(x1, y1), (x2, y2), ..., (xk, yk)}, где x1, x2, ..., xk - взятые в порядке следования первые k четных членов последовательности {a1, a2, ..., an}, а y1, y2, ..., yk - взятые в порядке следования первые k нечетных членов последовательности {a1, a2, ..., an}.
Формат входных данных:
Входной файл INPUT.TXT состоит из двух строк. В первой строке содержится натуральное число n - длина последовательности. Во второй - идут целые числа a1, a2, ..., an, разделенные пробелами. Пример:
10
98 56 33 73 41 8 48 93 52 80
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать последовательность {(x1, y1), (x2, y2), ..., (xk, yk)}, расположенную в одной строке файла, числа должны быть разделены пробелами. Если исходная последовательность не содержит ни одного четного или ни одного нечетного члена, т.е. k = 0, то в файл необходимо вывести цифру 0 (нуль). Пример:
98 33 56 73 8 41 48 93

Задача 1.2. Pазличные числа
Составитель Д. Подкопаев
Задание:
Дан массив (достаточно большой), содержащий целые числа из диапазона -20000..20000. Сосчитать сколько различных чисел в этом массиве. Формат входных данных:
Во входном файле ARRAY.IN содержатся элементы массива (файл может содержать несколько строк). Пример:
5 7 -47 6 -193 5
7 9 14 5485 -193
Формат выходных данных:
В первой строке выходного файла ARRAY.OUT содержится число различных чисел. Далее следуют сами эти числа, записанные по 10 в строке в порядке возрастания. Пример:
8
-193 -47 5 6 7 9 14 5485

Задача 1.3. Kоробки
Составитель В. Кузнецов
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
Имеется M коробок, определяемых тремя размерами: высотой, шириной и длиной. Коробки можно поворачивать, при этом их размеры меняют порядок. Коробка Кi с размерами (вi, шi, дi) вкладывается в коробку Кj размерами (вj, шj, дj), если вi < вj, шi < шj и дi < дj. Допускается вкладывать одну коробку в другую, предварительно поворачивая ее. Требуется найти количество пар коробок, которые можно вложить друг в друга, и количество троек коробок, которые можно последовательно вложить друг в друга. Пример1: К1: (3, 5, 8); К2: (4, 6, 2). К2 вкладывается в К1, т.к. 2 < 3, 4 < 5, 6 < 8. Пример2: К1: (3, 5, 9); К2: (4, 6, 11); К3: (5, 7, 15). К1 вкладывается в К2, К2 вкладывается в К3, считается, что К1, К2, К3 последовательно вкладываются друг в друга Формат входных данных:
Входной файл INPUT.TXT содержит количество коробок M (целое) в первой строке, 1 Ј M Ј 100, далее размеры коробок в, ш, д (целые), разделенные пробелами, в одной строке расположены три размера для одной коробки, 1 Ј в, ш, д Ј 1000. Пример:
3
30 6 11
12 21 30
1 5 7
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать два целых числа по одному в строке. Первое число - количество пар коробок, которые можно вложить друг в друга, второе число - количество троек коробок, которые можно последовательно вложить друг в друга. Пример:
2
0

Задача 1.4.* Монотонная последовательность
Составитель В. Кузнецов
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
Задана последовательность целых чисел {A1, A2, A3, … , AN} (1 Ј N Ј 3000) произвольного знака, по модулю не превосходящих 10000. Неубывающей подпоследовательностью последовательности {A1, A2, A3, ... , AN} длины k назовем набор чисел Aj1, Aj2, Aj3, …, Ajk таких, что:
1 Ј j1 < j2 < j3 < … < jk Ј N
и
Aj1 Ј Aj2 Ј Aj3 Ј … Ј Ajk.
Требуется найти число элементов самой длинной неубывающей подпоследовательности для заданной последовательности. Исходные данные задачи - целое число N и последовательность целых чисел {A1, A2, A3, ..., AN} - по одному в строке. Результат работы программы - целое число, длина самой длинной подпоследовательности данной последовательности. Пример исходной информации:
7
91
-76
-28
99
99
-29
-75
Ответ для данного примера:
4

Задача 1.5.* Произведение с неограниченным числом множителей
Составитель В. Кузнецов
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
Среди всех способов представления целого числа M в виде суммы N целых положительных слагаемых:
M = x1 + x2 + ... + xN  (1)
(N Ј M) найти тот, который доставляет наибольшее значение произведению П:
П = x11 * x22 * ... * xNN   (2)
Количество слагаемых N в сумме (1) (и множителей в произведении (2)) произвольное. Исходная информация - целое число M (1 Ј M Ј 1000). Результат работы программы - целое число N слагаемых в первой строке и N целых чисел, разделенных пробелами во второй - искомое разбиение, обеспечивающее наибольшее значение произведению П. Пример исходной информации:
5
Ответ для данного примера:
3
1 2 2

Задача 1.6. Функция Аккермана
Составитель В. Кузнецов
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
Задана следующая функция Аккермана:
Требуется вычислить значение функции B(m, n) для заданной пары целых чисел m, n. Формат входных данных: Входной файл INPUT.TXT содержит m и n (два целых числа), расположенные в первой строке и разделенные одним пробелом, 0 Ј m Ј 4, 0 Ј n Ј 10. Пример:
2 1
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать значение функции Аккермана (целое число) для заданной пары целых чисел m, n. Пример:
5

Поиск и подсчет подмножеств

Задача 2.1. Считалка
Составитель Г. Шабаев
Задание:
В круг выстраивается N человек (N Ј 50000). Начиная с первого, неизменно движутся по кругу и исключают каждого m-ого. Когда кто-то выбывает, круг смыкается. Процесс продолжается, пока людей не останется ровно R. Формат входных данных:
В первой строке входного файла DATA.IN заданы величины N, m и R, разделенные пробелом. Пример:
41 3 1
Формат выходных данных:
В выходном файле DATA.OUT содержится список целых чисел - номеров оставшихся участников в порядке их возрастания (по 10 в каждой строке). Пример:
31

Задача 2.2. Перестановка чисел
Составитель С. Русаков
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
Имеется перестановка P{pi} чисел 1, 2, ..., N, где 1 * N * 100. Для каждой перестановки P существует последовательность T{ti}, в которой ti = {кол-во чисел, больших i, расположенных левее положения числа i в P{pi}}. По заданной последовательности T{ti} восстановить P{pi}. Формат входных данных:
Входной файл INPUT.TXT:
первая строка - значение N; вторая строка - t1; третья строка - t2; ... N + 1 -я строка - tN.
Пример:
5
0
1
1
1
0
Формат выходных данных:
Выходной файл OUTPUT.TXT:
строка содержащая изначальную перестановку чисел 1,2,...n, разделенных пробелами. Пример:
1 5 2 3 4

Задача 2.3. Палиндромы
Составитель В. Тарасов
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
Дана последовательность символов {s1, s2, ..., sn}, 1 Ј n Ј 200. si либо является пробелом, либо принадлежит множеству [A, B,..., Z, a, b,..., z]. Группы символов, разделенные пробелами (одним или несколькими) и не содержащие пробелов внутри себя, будем называть словами. Палиндромом назовем такое слово s1, s2, ..., sk (k Ј 30), что s1 = sk, s2 = sk-1, s3 = sk-2,... При сравнении регистр символов учитывается (т. е. A № a). Найти длину самого длинного палиндрома. Формат входных данных:
Входной файл INPUT.TXT содержит в первой строке целое число n - длину последовательности. Во второй строке идет последовательность символов s1, s2, ..., sn. Пример:
26
asDFr rtYUUYtr KLOPF vccv
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать длину самого длинного палиндрома. Если исходная последовательность не содержит ни одного палиндрома, файл должен содержать цифру 0 (нуль). Пример:
8

Задача 2.4. Фальшивая монета
Составитель В. Кузнецов
Задание:
Имеется n (n Ј 20) монет, занумерованных целыми числами от 1 до n. Все они имеют одинаковый вес, кроме одной фальшивой , которая может быть легче или тяжелее остальных. Выполнен ряд взвешиваний на чашечных весах одинаковых по числу множеств монет и получены результаты. Требуется, имея некоторый набор взвешиваний, определить номер фальшивой монеты и будет она легче или тяжелее. Формат входных данных:
В первой строке входного файла MONEY.IN задано n - число монет. Далее следуют записи вида:
k c
l1 l2 ... lk
r1 r2 ... rk, где k - число монет в одной чашке весов (правой или левой), c = -1, если левая чашка весов с монетами тяжелее, c = 0, если весы находятся в равновесии, c = +1, если тяжелее правая чашка весов li и ri - списки, содержащие номера монет слева и справа. Пример:
6
2 -1
3 5
4 6
Эта запись означает, что всего монет 6, взвешивалось по 2 монеты - слева 3 и 5, справа 4 и 6, причем левая чашка весов (с монетами 3 и 5) тяжелее. Формат выходных данных:
В выходном файле MONEY.OUT содержится единственное число m - номер монеты или 0, если невозможно определить номер монеты. Пример:
0

Задача 2.5. Дочери программиста
Составитель В. Кузнецов
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
У программиста было M дочерей - красавиц, но очень обидчивых. Среди них не было двойняшек. По заведенной традиции программист поочередно выдавал девиц замуж. Однако, при этом он не всегда придерживался правильной очередности и могло случиться так, что младшая сестра выходила замуж раньше старшей. В этом случае все старшие незамужние сестры страшно обижалась на отца и писали в независимый профсоюз программистов анонимное письмо, что их отец развратник, пьяница и работает с использованием не лицензированных программных средств. Когда все дочери вышли замуж, программисту отдали все анонимные письма и оказалось, что их ровно N. Требуется определить число способов, которыми программист мог поженить все свое многочисленное семейство. Формат входных данных:
Во входном файле находятся разделенные пробелами целые числа M и N, (1 Ј M Ј 12, 0 Ј N Ј 66). Пример:
5 1
Формат выходных данных:
Целое число - искомое количество вариантов. Пример:
4

Задача 2.6.* Расстановка ферзей
Составитель В. Кузнецов
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
Определить количество попарно геометрически неприводимых правильных расстановок N ферзей на доске размерности N x N. Расстановка шахматных фигур считается правильной, если эти фигуры не бьют друг друга. Две расстановки называются попарно геометрически неприводимыми, если одну из них нельзя получить из дугой последовательностью геометрических преобразований симметрий или поворотов на 90 градусов. Формат входных данных:
Исходные данные задачи - целое число N, (1 Ј N Ј 12). Пример:
5
Формат выходных данных:
Целое число - количество расстановок. Пример:
2

Задача 2.7.* Покрытие домино
Составитель В. Кузнецов
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
Негодяи вырезали часть клеток прямоугольного поля, содержащего M x N квадрaтных клеток размера 1 x 1. Какое минимальное количество домино размера 1 x 2 потребуется для того, чтобы покрыть все оставшиеся клетки? Допускается накладка домино или выход их клеток за пределы оставшейся части поля. Формат входных данных: Первая строка файла - пара целых чисел M и N, (1 Ј M, N Ј 40). Последующие M строчек содержат по N целых чисел 0 и 1, разделенных пробелами. Значение 0 соответствует вырезанной клетке, 1 - оставшейся. Пример:
5 5
0 0 1 0 0
0 0 1 0 0
1 1 1 1 1
0 0 1 1 1
1 0 1 0 0
Формат выходных данных:
Целое число - искомое количество необходимых домино. Пример:
7

Геометрия

Задача 3.1. Линии
Составитель А. Веретин
Задание:
Задано множество прямых на плоскости коэффициентами уравнений типа y=A*x+B. Найти и подсчитать количество точек пересечения этих прямых. Формат входных данных:
В первой строке входного файла LINES.IN задано количество прямых. Далее в каждой строке заданы коэффициенты A и B, разделенные пробелом, для одной прямой. Пример:
3
0 6
5 0
0 3
Формат выходных данных:
В каждой строке выходного файла LINES.OUT выведены координаты точек пересечения прямых. В последней строке файла выведено количество точек пересечения в формате "Всего n точек пересечения прямых", где n - количество точек пересечения. Вещественные числа выводятся с точностью шесть знаков после запятой. Хвостовые пробельные символы в конце строк не допускаются. За точкой последней строки сразу идет символ конца файла. Пример:
x=0.6 y=3
x=1.2 y=6
Всего 2 точек пересечения прямых.

Задача 3.2. Точки
Составитель А. Веретин
Задание:
На плоскости задано N точек их координатами (X,Y) и M прямых коэффициентами уравнений типа y=A*x+B. Из заданных точек найти две такие (различные), что проходящая через них прямая параллельна наибольшему количеству заданных прямых. Формат входных данных:
В первой строке входного файла POINTS.IN задано количество точек на плоскости. Далее заданы координаты точек X и Y (по одной точке в каждой строке), разделенные пробелом. Затем следует строка задающая количество прямых на плоскости. После нее заданы коэффициенты A и B, разделенные пробелом (по одной прямой в каждой строке). Все координаты и коэффициентами могут быть вещественными от -1000 до 1000. Пример:
4
2 3
0 43
45 54
12 56
4
1.5 0
4 5
34 6
3 5
Формат выходных данных:
В первой строке выходного файла POINTS.OUT выведено число прямых, параллельных прямой, проходящей через найденные 2 точки. Далее координаты этих точек, по одной точке в каждой строке. Ответы округлить до 2 знаков после запятой. Пример:
1
2.00 3.00
12.00 18.00

Задача 3.3. Точки (2)
Составитель А. Бедорев
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
Даны координаты N точек на плоскости. Требуется соединить определенные точки таким образом, чтобы получилась геометрическая фигура наибольшей площади, при этом некоторые точки могут оставаться внутри фигуры. Гарантируется, что более двух точек не лежат на одной прямой одновременно. Координаты точек являются целочисленными и могут изменяться в интервале
1 * X * 300 для абсциссы
1 * Y * 300 для ординаты
Число точек может изменяться в диапазоне: 3 * N * 100
Формат входных данных:
Входной файл INPUT.TXT содержит в первой строке количество точек N. Последующие строки содержат координаты точек (абсциссу и ординату) через пробел. Пример:
7
4 9
1 8
2 4
3 6
4 5
6 6
5 2
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать матрицу соединений построенной фигуры. Элемент мат-рицы соединений mi,j равен 1, если точка i соединена с точкой j, и 0 в противном случае. Номером точки является номер строки входного файла, в которой указаны координаты точки. Каждая строка выходного файла содержит строку матрицы соединений. Матрица соединений является симметричной относительно главной диагонали. Например, для указанного выше примера входных данных (4 9), (1 8), (2 4), (3 6), (4 5), (6 6), (5 2) Должны быть соединены точки, в следующей последовательности 2 * 1 * 6 * 7 * 3 * 2 Пример:
0 1 0 0 0 1 0
1 0 1 0 0 0 0
0 1 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
1 0 0 0 0 0 1
0 0 1 0 0 1 0

Задача 3.4.* Путь на кубе
Составитель В. Кузнецов
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Задание:
На поверхности куба размера 10*10*10, установленного одной из вершин в начале декартовой системы координат с ребрами параллельно координатным осям задана пара точек A и B с целочисленными координатами: A(XA, YA, ZA) и B(XB, YB, ZB). Требуется определить квадрат кратчайшего расстояния по поверхности куба между этими точками. Исходная информация - координаты точек A и B - тройки целых чисел, (точки обязательно лежат на поверхности куба) Результат работы программы - целое число, квадрат кратчайшего расстояния по поверхности куба между этими точками. Пример исходной информации:
10 5 4
0 5 6
Ответ для данного примера:
404

Председатель жюри:
Дьяконов Максим Валерьевич
e-mail: mdia{at}cs.karelia.ru