В кабинете информатики есть старый стековый калькулятор. Он содержит K ячеек памяти, организованных в виде стека. Первая ячейка называется вершиной стека. На индикаторе калькулятора отображается содержимое вершины стека, если стек непуст.

Над стеком может выполняться операция проталкивания. Применение этой операции приводит к записи числа на вершину стека. Перед этим, если в стеке уже были числа, то каждое из них перемещается в ячейку с номером на единицу больше. Если в стеке уже находится K чисел, то выполнение операции проталкивания невозможно.

Калькулятор позволяет выполнять арифметические операции. Они применяются к числам, хранящимся во второй и первой ячейках стека. Результат операции записывается в первую ячейку стека, а число из второй ячейки удаляется. После этого, если третья ячейка непуста, то число из неё переписывается во вторую, если есть число в четвертой ячейке — оно переписывается в третью и так далее до последней занятой ячейки, которая становится пустой. Для выполнения арифметической операции в стеке должно быть хотя бы два числа. Например, при выполнении операций сложения или умножения, значения соответственно суммы или произведения чисел из первой и второй ячеек помещаются на вершину стека. Операция вычитания выполняется так: из содержимого второй ячейки стека вычитается содержимое первой ячейки.

Известно, что калькулятор неисправен. Из цифровых клавиш работает только клавиша «1». Нажатие этой клавиши приводит к проталкиванию в стек числа 1. Например, попытка набрать число 11, два раза нажав клавишу «1», приводит к тому, что в стек два раза проталкивается число 1. Из операций работают только сложение (клавиша «+»), умножение (клавиша «*») и вычитание (клавиша «-»). Если в результате вычитания получено отрицательное число, то калькулятор зависает.

Легко заметить, что на индикаторе возможно получить произвольное натуральное число. Например, чтобы получить число 3, необходимо дважды нажать клавишу «1», затем клавишу «+» (на индикаторе после этого появится число 2), затем один раз нажать клавишу «1» и один раз — клавишу «+». При K > 2 того же результата можно достичь иначе, трижды нажав клавишу «1», а затем два раза клавишу «+». Дополнительно используя операции умножения и вычитания, в некоторых случаях число N можно получить быстрее, чем сложив N единиц.

Требуется написать программу, которая определяет, каким образом можно получить на индикаторе калькулятора заданное число N, выполнив минимальное количество нажатий клавиш. Стек изначально пуст.

На плоскости задано такое множество из N многоугольников, что выполняются следующие условия:

• никакие два многоугольника не имеют общих точек;
• для каждого i –го многоугольника существует P_i многоугольников, внутри которых он находится, и N-1-P_i многоугольников, которые находятся внутри его, 0 ≤P_i≤N-1.

Напишите программу, которая для каждого многоугольника выдает количество многоугольников, внутри которых он находится.

Территория Великой Треугольной Области (ВТО) представляет собой прямоугольный треугольник. Длины его катетов равны M и N государственных единиц длины (ГЕД). Правительство ВТО решило покрыть как можно большую часть территории области квадратными плитами размером 11 ГЕД. Плиты должны плотно прилегать друг к другу и к катетам ВТО. Разрезать плиты нельзя.

Согласно межгосударственным соглашениям, правительство ВТО не имеет права покрыть частью своей плиты чужую территорию. Производитель поставляет плиты только контейнерными партиями — по P плит. Правительство заказывает столько контейнеров, сколько необходимо для реализации проекта.

Заведующий центральным складом, узнав про проект, решил, что его интересует коли­чество плит, которые останутся на складе из последнего контейнера после покрытия территории ВТО.

Напишите программу, которая по длинам катетов ВТО и вместимости контейнера находит количество плит, которые останутся на складе после осуществления проекта.

Заданы коэффициенты уравнения прямой ax + by + c = 0 и координаты точки A (xa, ya). Найдите точку B, которая является отражением точки A относительно заданной прямой.