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


ЗАМЕЧАНИЯ ПО РЕШЕНИЮ ИЗБРАННЫХ ЗАДАЧ

Замечание к задаче 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-й остатки дроби, мы легко и без больших затрат памяти можем найти ее период.

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