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

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

13A. Двойная решетка
[dlattice]
В данной задаче можно использовать принцип сетки, который был описан при решении 6D. Текущая задача является логическим продолжением задач 11A и 12A, где мы имели дело с начальной ацикличной и последующей периодической частью. Здесь ацикличной части нет, но ситуация осложняется тем, что последовательности две: по оси OX и OY. Это пугать никак не должно. Обработку последовательностей будем проводить отдельно. В приведенной реализации предложен механизм обнаружения последнего элемента первого цикла. Используя этот подход, можно по аналогичной схеме решить задачу для N решеток. 
13B. Последовательность Фибоначчи
[fiboseq] Бинарный поиск
Если особо не углубляться в природу чисел Фибоначчи и пытаться решить эту задачу с наскоку, то решение с помощью бинарного поиска - то что надо. И нужно еще не забыть, что число n может быть меньше min(i,j).
[fiboseq] Формула
Если же немного углубиться в эту самую природу, то можно получить формулу, которая однозначно восстанавливает элемент рассматриваемый последовательности с индексом min(i,j) + 1. Этих данных более чем достаточно для получения ответа.
13C. Скобки (3)
[bracket3]
Очередная “волшебная” задача на ДП. Учитывая бесценный опыт, по решению прошлых задач на эту тематику, особых трудностей возникнуть не должно. На первом этапе заполняем квадратную матрицу размерностью N*N, где N – длина исходной строки, куда в элемента [i][j] кладем длину ответа на исходную задачу для интервала исходной строки с i-ого символа по j-ый. Затем в обратном порядке восстанавливаем ответ.
13D. Центр тяжести
[centgrav]
Были проблемы с мат. частью, поэтому я ознакомился с решением авторского разбора и привел реализацию по нему.
13E. Сумма произведений
Что требуется в задаче осилил не сразу. Привожу два решения 
[prodsum] O(N*N)
Суровый перебор. Такое решение не должно было пройти по задумке автора. Но сейчас мощности возросли и мы можем себе это позволить. Но стоит N увеличиться на порядок и нас может спасти только второе решение.
[prodsum] O(N)
Оказывается для получения ответа необходимо перебирать только количество нулей(z). Отсюда можно однозначно определить общее количество(k) единиц и минус единиц. Для получения количества единиц(p) необходимо решить квадратное уравнение(a*p*p + b*p + c = 0), где коэффициенты a,b,c выражаются через k и s. Весь смак в получении этого квадратного уравнения.
13F. Статическая сложность
[icomplex]
В последнее время прям нравятся задачи на разбор выражения. Здесь, как и в 12F был реализован рекурсивный спуск.


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