Условие
Есть упорядоченный массив из N различных элементов с известными вероятностями запроса каждого w_i. Нужно построить алгоритм бинарного поиска: на каждой итерации алгоритм выбирает индекс i. Если совпало — успех (1 итерация). Иначе сравниваем с arr[i] и спускаемся в одну из двух половин (как в дереве). Алгоритм описывается деревом сравнений с количеством итераций для каждого исхода.
Считаем матожидание числа итераций. Нужно найти все алгоритмы с минимальным матожиданием (с точностью до изоморфизма), не более K штук, где K ≤ 1000.
Формат ввода
N # 1 ≤ N ≤ 800
w_1 w_2 … w_N # 1 ≤ w_i ≤ 1000, целые веса (вероятности после нормализации)
Формат вывода
В первой строке — K — число оптимальных алгоритмов (≤ 1000).
Далее K блоков: каждый описывает дерево.
Описание дерева: для каждого индекса от 1 до N выводится индекс родителя (или -1 для корня) и пометка L/R (левый/правый ребёнок).
Пример
Ввод:
3
2 1 2
Вывод:
3
1 3 2
2 1 3
3 1 2