Сегодня мальчик Саша на уроке математики узнал про фракталы. Учитель показывал так называемую «кривую дракона». Она представляет собой геометрическую фигуру, которая строится следующим образом: на первом шаге проводится отрезок из начала координатной плоскости в точку (0; 1). Далее на каждом шаге из конца фрактала повторяется уже нарисованная часть фигуры, повернутая на 90 градусов против часовой стрелки (см. рисунок).

После уроков Саша попробовал сам изобразить «кривую дракона», и теперь он хочет знать, в какой точке координатной плоскости он закончил рисовать фрактал, проделав описанные выше N шагов. Требуется написать программу, которая по заданному числу N определяет координаты конца фрактала после выполнения N шагов.

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

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

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

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

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

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

В начале выполнения программы процессор находится в первом режиме, завершиться выполнение программы может при любом режиме процессора.

Всем известно, что в 2012 году прошла Летняя Олимпиада в Лондоне, однако не каждый знаком с историей крупнейших спортивных соревнований. Традиция игр зародилась в Древней Греции, но была забыта по завершении античной эпохи и вновь появилась лишь в конце XIX века благодаря французскому общественному деятелю Пьеру де Кубертену.

С 1896 года вновь проводятся летние Олимпийские игры, а с 1924 — зимние, причём оба вида соревнований проходят раз в четыре года. Первое время зимняя и летняя Олимпиады проводились в один и тот же год, но в конце XX века Международный олимпийский комитет принял решение установить между разными видами Игр двухгодичный перерыв. Таким образом, 1992 год был в последний раз отмечен проведением одновременно летних и зимних Олимпийских игр, в 1994 проводились только зимние, в 1996 — летние, и с тех пор они продолжают чередоваться.

Известно также, что в 1916, 1940 и 1944 годах Олимпийские игры были отменены по причине Первой и Второй мировых войн, а в 1906 году проводилась внеочередная Олимпиада.

Требуется написать программу, которая по заданному году определит, проводились ли в этом году Олимпийские игры и были ли они летними или зимними.

Мальчик Вася очень любит строить башни из кубиков. К сожалению, во время последней игры он увлёкся и потерял все кубики, кроме двух. Однако Вася не стал унывать и придумал новое развлечение. Заметив, что на каждой грани кубиков написано по одной цифре, он научился выкладывать двузначные числа из оставшихся игрушек. Вскоре мальчику стало интересно, сколько идущих подряд чисел, начиная с единицы, он сможет выложить с помощью двух кубиков. Помогите Васе найти ответ — такое максимальное число K, что все числа от 1 до K включительно можно получить, используя два оставшихся кубика.

Поскольку в игре используются оба кубика, числа, меньшие 10, Вася выкладывает с ведущими нулями (так, единицу можно получить, выбрав грань первого кубика с цифрой 0 и второго — с цифрой 1). Помните, что Вася умный мальчик: он знает, что перевернутый кубик с цифрой 6 позволяет получить цифру 9, и наоборот.