Тренировка #12 [Меньшиков]

[Условия задач]                   [Список тренировок]

12A. Последовательность (2)
[seq2]
Данная задача, решается аналогично 11A. Есть два принципиальных отличия. Во-первых, цикл в данной последовательности наступит тогда, когда повторится тройка подряд идущих цифр. Поэтому, максимальное количество элементов в цикле не более 1000. Во-вторых, экспериментальным путем было выявлено, что в данной последовательности нет ацикличной начальной части, т.е. первая повторяющаяся тройка совпадает с первой тройкой последовательности. Правда второе наблюдение не было отражено в решении, сохраняя общность подхода к решению подобных задач. 
12B. Гирлянда
[garland]
Интересная задача. Долго не мог понять условия. Главное уловить принцип прогибающейся гирлянды: чем ближе находится самый нижний из узлов гирлянды к оси OX, тем ниже будет находится точка B. Подход к решению аналогичен 11B.
12C. Головоломка умножения
[mpuzzle]
Хорошее двумерное ДП. Суть подхода – ищем ответ на поставленную задачу сначала для интервала длины 2, постепенно увеличивая длину. Когда длина интервала будет равно длине первоначальной последовательности – решение найдено. Остается главное – продумать переход от меньших интервалов к более большим.
12D. Точки в многоугольнике
[polygonp]
Несложная задача, если знаешь мат.часть, которая в данном случае заключается в формуле Пика.

S = В + Г/2 − 1

где
S – Площадь многоугольника (4D),
Г – Количество целочисленных точек на границе(10D),
B – Количество целочисленных точек внутри многоугольника.
Учитывая полученную информацию, найти значение B – дело техники.
12E. Водопровод
Оба подхода делают примерно одно и тоже. Пытаемся набрать длины dx = |x2-x1| и dy = |y2-y1|, используя набор предложенных труб.
[wpipe] Рекурсивный перебор с отсечением
В первом решении сначала пытаемся набрать длину dx, и только если это удалось – пытаемся набрать длину dy из оставшихся труб. Итак как можно набрать длину dx? Предположим, что имеем дело с крайним случаем, т.е. имеется 4 типа труб. Рассмотрим формулу:

a*L[0] + b*L[1] + c*L[2] + d*L[3] = dx

где a,b,c,d некоторые коэффициенты, которые по модулю не превышают C[0], C[1], C[2] и C[3] соответственно.
L[i] – длина трубы типа i.
C[i] – количество труб типа i. 1<=i<=K.
Перебор можно уменьшить, если перебирать только первые K-1 коэффициентов, т.к. последний K-ый коэффициент однозначно можно восстановить по первым K-1 коэффициентам и значению dx. Итак для нахождения замощения длины dx понадобится максимум 20*20*20 = 8000 итераций. Аналогично для dy - тоже 8000 итераций. Общее количество действий будет значительно меньше 8000*8000 действий.
[wpipe] Нерекурсивный перебор с использованием ДП
Второе решение начнем с того, как можно представить набор труб, которыми можно набрать определенную длину, если положить все трубы на одной прямой. Очевидно, что это будет картеж максимум из 4 элементов: {X,Y,Z,P}, где X<=C[0], Y<=C[1], Z<=C[2] и P<=C[3]. Если используем все трубы, то получаем картеж {10,10,10,10} в худшем случае. Если не используем ни одной трубы, то – {0,0,0,0}. Такой картеж можно упаковать в десятичное число равное числу XYZP в 11-ричной системе счисления. Картеж {10,10,10,10} будет эквивалентен 14640.
Если выложить все трубы в одном направлении, то получим длину не более MAX_LEN = 4*10*1000 = 40000.
Заполним рванную матрицу vector<vector<int> > dp(MAX_LEN * 2), где в dp[len] будут хранится упакованные в число наборы труб, которыми можно набрать длину len.
После чего достаточно будет взять наборы dp[dx] и dp[dy] и перебрать все возможные пары в поисках нужного ответа.
12F. Химические реакции
[chem]
Первая задача на рекурсивный спуск. Также эту задачу можно было сделать с помощью конечного автомата. Для начала нужно ознакомится с нотацией Бэкуса-Наура а дальше проявить внимательность и аккуратность. В таких задачах я практикую принцип “Тише едешь – дальше будешь”. Исходных код ответит на все остальные вопросы.

[Все решения]