 |
Замечания по решению избранных задач
|
|
|
|
ЗАДАЧИ ДЛЯ ПРАКТИКИ
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
ЗАМЕЧАНИЯ ПО РЕШЕНИЮ ИЗБРАННЫХ ЗАДАЧ
Замечание к задаче 1.2. Различные числа.
Для решения этой задачи необходимо отметить, что общее количество различных чисел не так велико (40001) и можно завести массив флагов - включено это число в массив или нет. Вот собственно и все...
Замечание к задаче 1.3. Коробки.
Для решения этой задачи необходимо провести некоторые предварительные рассуждения. Первое из них: при каких условиях первая коробка, размеры которой (в1, ш1, д1), вкладывается во вторую с геометрическими размерами (в2, ш2, д2)? Меняя порядок чисел (в1, ш1, д1) и (в2, ш2, д2), построим тройки чисел X1 < Y1 < Z1 и X2 < Y2 < Z2. Очевидно, самый большой размер первой коробки z1 в этом случае должен быть меньше самого большого z2. Но первая коробка не поместится во вторую, если при этом не будет выполняться неравенство y1 < y2 (почему?), а также x1 < x2.
Теперь решение задачи не представляет трудности - общее количество коробок М < 100 позволяет организовать двойной цикл проверки "вкладываемости" всех возможных пар коробок. Тройной цикл для троек коробок лучше организовать осторожно, проверяя возможность поместить третью коробку в меньшую из двух, уже вложенных в другую.
Эта задача может решаться для многомерных коробок, а также в варианте постановки "найти самую длинную последовательность вкладывающихся коробок" с использованием аппарата следующей задачи. Другая её особенность - возможность получить полезные выводы общего характера, среди которых такое: геометрические преобразования соответствуют перестановке размеров коробок. Поэтому прежде, чем исследовать размеры параллелепипеда, приведите вектор размеров к некоторой стандартной форме - разверните коробки в порядке их невозрастания, что может существенно упростить дальнейшую работу. Идея "инварианта" (не изменяющегося при геометрических преобразованиях значения) или "стандартной формы представления" (как, например, в этой задаче) очень важна при решении геометрических задач, когда допустимо или требуется движение объектов.
Замечания к задаче 1.4. Монотонная последовательность.
Очень красивая задача, опубликованная в книге Р. Арсака. Решение задачи для N = 1, 2 тривиально. Хотелось бы провести индуктивное рассуждение и научиться переходить от i < N к i+1, "достраивая" самую длинную последовательность. Но это не получается сразу. Действительно, в примере последовательности:
0, 10, 20, 11, 12, 13,...
при переходе от i=3 к 4 самая длинная подпоследовательность 0, 10, 20 остается прежней, а вот при больших значениях i выясняется, что продолжать следовало меньший отрезок ранее найденной 0, 10, 11, 12,... Поскольку неизвестно, на сколько элементов придется отступить и сколько раз придется это проделать, начинает казаться, что сложность решения этой задачи может быть сопоставима со сложностью просмотра всех последовательностей.
Однако это не так. Действительно, для построения алгоритма решения задачи, пригодного для больших N (в условиях N <= 3000), заметим, что индуктивный переход от i к i + 1 выполнять все же можно и полученная самая длинная последовательность будет представлять собой одну из самых длинных для некоторого меньшего значения i, но придется учитывать не только длину последовательности, но и величину ее последнего элемента (в представленном примере приходится "жертвовать" удлинением последовательности значением 20 в пользу предшествующего, но меньшего по величине 10).
Остается составить рекуррентное соотношение, связывающего интересующий нас объекты для i и i + 1, и выбрать необходимые для реализации структуры данных...
Замечание к задаче 1.5. Произведение с неограниченным числом множителей.
Эта задача может показаться простой с первого взгляда. Действительно, для ее решения достаточно определить все наборы целых чисел x1, x2,..., Xn, в сумме дающих М (соотношение (1) условий), вычислить указанное в условиях задачи произведение (2) (а может быть его логарифм?) и выбрать наибольшее значение. Полезно учесть, что максимум произведения может достигаться только, если выполняется: X1<=X2<=...<=Xn(почему?).
Однако смущает условие М <= 1000. Перебор вариантов представления такого большого числа в виде суммы натуральных потребует слишком много времени.
Попробуйте за счет рассуждения еще больше сократить перебор. Может ли среди чисел X1, X2,..., Xn, доставляющих наибольшее значение произведению (2), оказаться число 4 или 5? Это существенно упростит задачу.
Замечания к задаче 1.6. Функция Аккермана.
Решение этой задачи не составляет труда. Рекурсивная функция полностью соответствует ее определению, представленному в задаче. Решение задачи представлено в рекурсивной (более простой) и нерекурсивной форме. Попробуйте разобраться, как устроен стек параметров. Однако небезынтересно проследить последовательность вызовов этой функции, например для вычисления А(1,2). Полезно также вычислить значения этой функции для малых m:
А(1,n) = n + 2, A(2,n) = 2 * n + 3, A(3,n) = 2(n+3)-3 и т.д.
О скорости роста этой функции свидетельствует тот факт, что А(4,n) = h(n)-3, где h(n) = 2k(n-1). Как ни странно, существуют комбинаторные алгоритмы, сложность которых отличается от линейной на ничтожно малую величину, порядка 1+1/A(n,1), таким образом, эта фантастически быстро растущая функция находит применение в оценке сложности алгоритмов.
Исследование этой функции, включающей в себя сумму, произведение, степень, гиперстепень и т.д., выполнено Р. Хермесом в 1971 году. Оно развивает идеи В. Аккермана, построившего таким образом контрпример к одному из утверждений - проблем Гильберта. Для произвольных параметров эта функция не может быть вычислена с помощью конечного применения процессов подстановки и индукции ("примитивно - рекурсивно") и относится к классу "дважды-рекурсивных" функций.
Замечание к задаче 2.4. Фальшивая монета.
Решение этой задачи не составляет труда при правильно подобранной структуре данных. На языке Паскаль такой структурой мог бы быть массив
A: Array [-1:1,1:n] of Bit;
Первоначально его можно заполнить нулями. При этом A[-1,j] = 0 означает, что монета j может быть легче настоящей, A[1,j]=0 - тяжелее, A[0,j]=0 - что эта монета не фальшивая. Первоначально не исключены все возможные варианты для каждой монеты. Число вариантов будет сокращаться при каждом дополнительном взвешивании. Остается найти способ идентифицировать один из трех конечных исходов:
Фальшивая монета найдена.
Результаты взвешиваний противоречивы.
Информации для определения монеты недостаточно.
А это не представляет трудности.
Замечание к задаче 2.5. Дочери программиста.
Задачу, очевидно, можно переформулировать следующим образом: найти количество перестановок М элементов, содержащих ровно N инверсий (66 = 12*11/2). Задачу можно решать двумя способами. Первый из них - построить все перестановки с N инверсиями и пересчитать их (можно и даже удобнее строить векторы инверсий). Размерность позволяет успеть сделать это, если строить именно перестановки с данным количеством инверсий. А можно самостоятельно или, предварительно прочитав энциклопедию вычислительной математики Д. Кнута, получить рекуррентное соотношение для числа перестановок:
In(m)=In(m-1)+In-1(m), где n > 0 - число элементов, m > 0 - число инверсий ее элементов, и весьма удобно воспользоваться им.
Замечание к задаче 2.6. Расстановка ферзей.
Первая половина задачи - построение всех расстановок m ферзей на шахматной доске размерностью m*m - классическая и подробно описана в пр. источниках. Временное ограничение при заданной размерности несущественно.
Представляется более сложной задача геометрически неприводимых расстановок ферзей. Автор "эталонного" решения использовал для этой цели, как оказалось, не самый лучший алгоритм: строил 8 производных (симметриями и поворотом на 90 градусов) позиции по отношению к вновь полученной и сравнивал результат с ранее найденным. Процесс ускорялся за счет вычисления инварианта геометрического преобразования расстановки ферзей (суммы модулей произведения отклонений координат точек расстановки ферзей от центра доски). Если значение инварианта ранее не встречалось, то больше никакой другой проверки не требуется. Построением второго инварианта практически удалось "разделить" все геометрически неприводимые позиции. Однако эти средства годятся для экспериментаторов в спокойных условиях, а не в нервозной обстановке олимпиады.
Замечание к задаче 2.7. Покрытие домино.
Отметим два наблюдения, полезных при решении этой задачи:
1. Разобьем все наборы вырезанных на доске клеток на компоненты связности (две клетки смежны, если они имеют общее ребро). Тогда ни одно домино не может закрыть пару вырезанных клеток различных компонент связности. Следовательно, задача распадается на несколько, по числу компонент связности вырезанных клеток доски.
2. Раскрасим доску в шахматном порядке. Любое домино может закрыть либо одну (черную или белую клетку компоненты) или пару клеток различных цветов. Подсчитывая количество белых и черных клеток каждой из компонент и выбирая из этих значений наибольшее, найдем нижнюю границу требуемого количества домино.
... как правило, она реализуется. Далее перебор вариантов для каждой компоненты с редукцией числа элементов.
Замечание к задаче 3.3. Точки.
Идея решения очень проста: надо взять какую-нибудь крайнюю точку (например с минимальной ординатой) и далее выбирать точки, для которых угловой коэффициент прямой, проходящей через выбранные две точки, будет максимальным (обход по часовой стрелке) или минимальным, и продолжать - добавлять точки до тех пор, пока ломанная не замкнется...
Замечания к задаче 3.4. Путь на кубе.
Аналогичная задача, только не на кубе, а на параллелепипеде (автор - И. В. Романовский), была предложена участникам командного полуфинала чемпионата мира по программированию среди студентов в 1997 году. Ее не решил никто???
Вот основные идеи алгоритма:
1. Перестановкой координат и заменой, если нужно, координаты z на 10-z (т.е. поворотами и симметрией куба) одну из точек можно переместить на плоскость OXY - дно куба.
2. решение задачи теперь зависит от того, на какой грани вторая точка. Если на дне куба - работает теорема Пифагора. Если на боковой грани - снова работает теорема Пифагора, поскольку на развертке кратчайший путь, очевидно, превращается в отрезок. Если вторая точка окажется на верхней грани, снова можно использовать теорему Пифагора, но придется рассматривать большое количество вариантов развертки.
И все это представляется несложным. Но будьте внимательны, вариантов может оказаться больше, чем Вы думаете.
Замечание к задаче 4.1. Бумага с кляксами.
Если рассматривать не залитые чернилами линии и точки пересечения линий доски как граф, то задачу можно истолковать как задачу поиска кратчайшего расстояния из левой нижней в правую верхнюю вершину этого графа. Длины всех дуг равны 1, что существенно упрощает решение задачи. Однако для решения такой задачи бессмысленно применять известные методы Дейкстра и Флойда. Граф с 10000 вершин - это довольно большой граф.
Можно поступить проще:
1. Сообразить, что если путь из левого нижнего угла (вершины с координатами(0,0)) в клетку с координатами (i,j) существует, то он не длиннее 10000 единиц, и заполнить этим значением все элементы матрицы A[i,j] (0 <= i <= m, 0 <= j <= n), кроме A[0,0] = 0.
2. Последовательно, поочередно просматривая ее элементы, приводить матрицу A к матрице D кратчайших расстояний от вершины (1,1), воспользовавшись рекуррентным соотношением: D[i,j] = Min{D[i-1,j],D[i+1,j],D[i,j-1],D[i,j+1]}+1, которое выполняется для матрицы D (конечно, кроме D[0,0] и с исключением элементов, выходящих за пределы индексных множеств i и j).
Найденное кратчайшее расстояние будет распространяться дальше и дальше от вершины (0,0), пока не доберется до (m,n). Проблема заключается в скорости такого распространения. При большой размерности может возникнуть проблема времени вычислений. В чем она состоит и как с ней бороться?
Замечания к задачам 4.2. Прямоугольники и 4.5. Морской бой. Достаточно подсчитать число углов (например верхних левых). Небольшая тонкость заключается в обработке краев - проще всего окружить поле пустыми клетками.
Замечание к задаче 5.4. Период дроби.
Решение этой задачи может показаться трудным, если не отметить одной детали: пусть период дроби равен n, следовательно, тот же остаток будет и на месте 2n, 3n и т. д., следовательно, вычисляя и сравнивая n-й и 2n-й остатки дроби, мы легко и без больших затрат памяти можем найти ее период.
|
|
|
