Задача . D. Передача пирамиды

Вася с Петей используют интересную структуру для хранения данных, пирамиду.

Пирамида состоит из n рядов, в i-том из них содержится i ячеек. Каждый ряд сдвинут относительно предыдущего на половину длины ячейки влево. Ячейки пирамиды пронумерованы от 1 до так, как показано на рисунке ниже.

Пример пирамиды при n = 5:

Эта структура данных умеет выполнять операции двух видов:

1. Изменить значение конкретной ячейки. Описывается тремя числами: "t i v", где t = 1 (тип операции), i — номер ячейки, которую нужно изменять и v — значение, которое нужно в нее записать.
2. Изменить значение в некоторой подпирамиде, на изображении выделена подпирамида с вершиной в 5 ячейке. Описывается s + 2 числами: "t i v₁ v₂ ... v_s", где t = 2, i — номер ячейки, которая является вершиной подпирамиды, s — размер подпирамиды (количество ячеек в ней), v_j — значение, которое необходимо присвоить j-той ячейке подпирамиды.

Формально: подпирамида с вершиной в i-той ячейке k-того ряда (5 ячейка = вторая ячейка третьего ряда) будет содержать ячейки из рядов от k до n, в (k + p)-том из них — ячейки ряда от i-той до (i + p)-той (0 ≤ p ≤ n - k).

У Васи и Пети было две одинаковые пирамиды. Вася в своей пирамиде изменил некоторые ячейки и теперь хочет передать изменения Пете. Для этого он хочет найти последовательность операций, при помощи которой можно повторить все сделанные им изменения, однако, среди всех возможных последовательностей необходимо выбрать самую короткую (содержащую минимальное количество чисел).

Вам дана пирамида из n рядов, в которой k ячеек были изменены. Найдите последовательность операций, после которой каждая из k измененных ячеек будет также изменена как минимум одной из операций. Среди всех возможных последовательностей выберите содержащую минимальное количество чисел.