Квадратным фракталом $$$0$$$-го уровня назовем квадрат со стороной $$$a$$$.

Чтобы получить квадратный фрактал первого уровня, нужно каждую сторону квадрата разделить на $$$3$$$ равные части, и на центральном фрагменте построить маленький квадрат со стороной, равной длине этого центрального фрагмента, расположив его на внешней стороне исходного квадрата.

Внутренние линии после построения удаляются. Каждый новый фрактал — это замкнутая непересекающаяся ломаная.

Квадратный фрактал любого следующего уровня образуется аналогичным образом из фрактала предыдущего уровня, при этом новые маленькие квадраты появляются на каждой внешней стороне тех квадратов, которые были добавлены на предыдущем уровне.

По заданному $$$N$$$ и длине стороны $$$а$$$, вычислите периметр и площадь квадратного фрактала $$$N$$$-го уровня.

Для каждой подгруппы баллы начисляются только в случае прохождения всех тестов в ней самой и во всех необходимых подгруппах.

Магистр-джедай Йода способен передвигать предметы силой мысли. Его сила мысли измеряется в интеллах. Чтобы сдвинуть, например, камень массой $$$3$$$ кг на $$$5$$$ метров, ему нужно потратить $$$3 \times 5=15$$$ интеллов силы.

В начальный момент времени все камни находятся по одну сторону от воображаемой прямой линии $$$L$$$, причём каждый камень располагается на заданном целом расстоянии от этой линии (некоторые камни могут даже лежать на $$$L$$$, т.е. находиться на расстоянии $$$0$$$ от неё). Йода хочет добиться максимального результата, используя имеющуюся у него силу. Он хочет так отодвинуть камни на целое число метров от прямой $$$L$$$, чтобы после сдвига ближайший к $$$L$$$ камень оказался как можно дальше от неё.

Требуется выяснить, на каком максимальном расстоянии от линии $$$L$$$ может оказаться ближайший к ней камень после сдвига, если Йода обладает силой заданной величины?

Для каждой подгруппы баллы начисляются только в случае прохождения всех тестов в ней самой и во всех необходимых подгруппах.

Когда Незнайка ходит в гости к своим друзьям, он либо идет пешком, либо едет на такси. Всё зависит от расстояния.

Если предстоит пройти без отдыха не более $$$D$$$ километров, Незнайка идет пешком, а иначе — берёт такси.

В свой день рождения Незнайка решил навестить всех своих друзей. Но самое главное — он хочет минимизировать число своих поездок на такси!

Чтобы добиться этого, ему, возможно, придётся неоднократно заходить к кому-то из друзей, чтобы отдохнуть, и, возможно, также для отдыха неоднократно возвращаться к себе домой. После захода в любой дом Незнайка отдыхает, поэтому когда после этого он выходит на улицу, у него достаточно сил, чтобы пройти ещё $$$D$$$ километров.

Известно, что некоторые пары домов связаны двухсторонними дорогами, для каждой из которых известна её протяженность. Ходить пешком и ездить на такси можно только по этим дорогам. От любого дома можно добраться по дорогам до любого другого.

Любая поездка Незнайки на такси начинается и заканчивается возле одного из домов. Посещение друга возможно только после окончания поездки.

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

Требуется выяснить, какое минимальное количество поездок на такси может сделать Незнайка и при этом навестить всех своих друзей, если начать свой путь и закончить его Незнайка должен у себя дома?

Для каждой подгруппы баллы начисляются только в случае прохождения всех тестов в ней самой и во всех необходимых подгруппах.

Васе и Пете на новогоднем утреннике подарили много одинаковых круглых конфет. После окончания праздника братья принесли сладости домой и решили их поделить. Пока Вася мыл руки, Петя решил посчитать конфеты, а для этого выложил их все без остатка на стол в виде, как ему показалось, идеального прямоугольника $$$w \times h_1$$$.

После того, как Вася вернулся, настала Петина очередь идти мыть руки. В это время Вася решил подшутить над братом и переложил сладости: он убрал из каждого горизонтального ряда последние $$$K$$$ конфет и образовал из них новые ряды так, что получился прямоугольник $$$(w - K) \times h_2$$$.

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

Петя зашёл в комнату и увидел неидеальный прямоугольник. Переполненный эмоциями, Петя подошёл к столу и разбросал лежащие на нём конфеты по всей комнате, а затем ушёл к себе.

Васю замучила совесть за неудачную шутку, поэтому он решил извиниться перед братом, восстановив исходный прямоугольник. Собирая разбросанные по полу конфеты, он насчитал $$$N$$$ штук. Однако за время сбора конфет он забыл число $$$w$$$.

Помогите Пете по общему количеству конфет $$$N$$$ и количеству перекладываемых из каждого ряда конфет $$$K$$$ найти все возможные значения длины ряда до перекладывания $$$w$$$.

Для каждой подгруппы баллы начисляются только в случае прохождения всех тестов в ней самой и во всех необходимых подгруппах.

На далёком континенте в бескрайней степи жило племя Морьтонов. Они пасли лошадей, овец, а также совершали набеги на соседние племена. После очередного набега хан Удирдагч рассматривал награбленное, когда на его глаза неожиданно попался необычный свиток. Он рассказывал о далекой стране Леку-Десирагаррия, лежащей на другом конце континента и обладающей несметными богатствами. Вдохновившись этими историями, военачальник решил отправиться в завоевательный поход.

Континент можно представить в виде прямоугольника, разбитого на равные квадратные ячейки. Ставка хана располагается в клетке $$$(0, M)$$$, а Леку-Десирагаррия — в клетке $$$(N, 0)$$$. Координаты задаются в виде (<номер строки>, <номер столбца>). Строки нумеруются сверху вниз, а столбцы слева направо.

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

Каждый отряд за время дневного перехода может переместиться двумя способами: на $$$A$$$ клеток влево и на $$$B$$$ клеток вниз, либо на $$$A$$$ клеток вниз и $$$B$$$ клеток влево. Клетка считается посещённой, только если в ней отряд останавливается на ночёвку.

Естественно, вождю потребовалось узнать, какое наибольшее количество отрядов могут добраться до Леку-Десирагаррии.

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

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

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

Баллы за каждую подгруппу начисляются только в случае прохождения всех тестов этой подгруппы и всех тестов всех необходимых подгрупп.