1. Задания личной олимпиады

G2048

В свободное от занятий время Гарри Поттер с друзьями очень любят играть в интеллектуальные игры и Гермиона принесла им новую игру. Ее игровое поле имеет форму квадрата размером 4х4. Перед первым ходом игры в некоторых двух разных произвольно выбранных клеточках находится по плитке номинала «2». Далее на каждом ходу в произвольно выбранной свободной клеточке появляется новая плитка номинала «2». Нажатием стрелки игрок может сдвинуть все плитки игрового поля в одну из четырех сторон (вверх/влево/вниз/вправо). Если при движении две плитки одного номинала «налетают» одна на другую, они сливаются в одну, номинал которой равняется сумме слитых. Например, если две плитки с номиналом «2» налетели друг на друга, они заменяются на одну плитку с номиналом «4» (2+2). При этом игровые очки увеличиваются на номинал вновь созданной плитки (в данном случае на 4). За один ход может выполниться несколько слияний и в этом случае все очки добавляются. Например, рассмотрим такое состояние игры:

Сдвиг влево в этом случае суммирует две «2» и две «8» и приносит 4+16=20 очков. После этого в случайной свободной клеточке появляется 2.

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

Формат ввода-вывода:

Программа G2048 читает с клавиатуры (стандартного устройства ввода) четыре строки по четыре числа в каждом. Пустые клеточки обозначены нулями, непустые могут содержать только степени двойки, т.е. числа 2, 4, 8, 16, 32, …, 65536 таким образом, что поле в целом может быть правильной конечной или промежуточной позицией рассмотренной игры.

Программа G2048 выводит на экран (стандартное устройства вывода) единственное число – искомое количество очков.

Пример входных и выходных данных:

Лестница (stairs)

Как известно, Школа чародейства и волшебства в Хогвардсе имеет 142 лестницы, одна из которых имеет ровно N ступенек. Именно по этой лестнице можно передвигаться, переходя с одной ступеньки на следующую, перепрыгивая через ступеньку или перепрыгивая через две ступеньки, однако перепрыгивать через ступеньки два раза подряд нельзя. Часть ступенек была разрушена в одной из схваток с Волан де Мортом, однако лестницей все еще можно пользоваться, обязательно начиная движение с первой ступеньки и заканчивая на последней.

Альбус Дамблдор не на шутку обеспокоен состоянием этой лестницы и его интересует ответ на такой вопрос: при разрушении какого максимального количества ступенек по лестнице все еще можно будет подняться с первой ступеньки на последнюю.

Формат ввода-вывода:

Программа stairs читает с клавиатуры (стандартного устройства ввода) два целых числа N и K, общее количество ступенек в лестнице и количество разрушенных ступенек (2 <= N <= 10⁶, 0 <= K <= N-2). Далее считывается K целых чисел, номера разрушенных ступенек (в диапазоне от 2 до N-2).

Программа stairs выводит на экран (стандартное устройства вывода) единственное число – максимальное количество ступенек, которые можно разрушить, не выводя лестницу из строя.

Пример входных и выходных данных:

Великая шахматная партия (emperor)

Главный противник Гарри Поттера лорд Волан-де-Морт, которого многие считали погибшим, тайно возвращается в Хогвардс. Для этого он использует тело профессора защиты от темных искусств Квиреуса Квиррелла. С его помощью он принимается искать философский камень, думая восстановить тело Темного лорда. Гарри Поттер активно ему противодействует и его друзья – Рон Уизли и Гермиона Грейнджер – помогают ему в борьбе. В один из самых критических моментов Рону предлагается сыграть в волшебные шахматы по новым правилам. На шахматном поле кроме обычных фигур находится новая фигура – так называемый Император.

1. На своем первом ходу Император сбивает любую шахматную фигуру, которая стоит на одной с ним горизонтали или вертикали и переходит на ее место.
2. На любом следующем ходу Император сбивает любую шахматную фигуру на той же вертикали (если предыдущий ход этого Императора был по горизонтали) или горизонтали (если предыдущий ход был по вертикали) и переходит на ее место.
3. Император не может сделать ход если он не может сбить вражескую фигуру.

Известно положение шахматных фигур на доске. Рону необходимо срочно рассчитать, какое наименьшее количество Императоров нужно поставить на доску так, чтобы они могли сбить все шахматные фигуры. При этом Императоры могут делать любое количество ходов, а шахматные фигуры не движутся. Размер доски: 10⁸ ×10⁸.

Формат ввода-вывода:

Программа emperor читает с клавиатуры (стандартного устройства ввода) целое число N (1 <= N <= 10⁵) – количество шахматных фигур. Затем считывается N пар целых чисел (в диапазоне от 1 до 10⁸), позиции шахматных фигур.

Программа emperor выводит на экран (стандартное устройства вывода) единственное число – наименьшее количество Императоров для полной победы.

Пример входных и выходных данных:

Левитация (levitation)

Как известно, левитация– это умение силой мысли преодолевать земное тяготение, проще говоря — летать, не имея крыльев или иных приспособлений. Заставить летать можно как неодушевлённый предмет, так и человека. Левитация изучается на уроках заклинаний в Школе чародейства и волшебства в Хогвардсе. На первых из этих уроков ученики заставляют летать только предметы и летают они в очень непредсказуемых направлениях.

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

Для начала он предложил рассмотреть материальную точку на плоскости с массой 0.1кг, которая в момент времени t = 0 сек находится в начале координат и имеет нулевую скорость. Предположим, что на точку действуют N постоянных сил от разных учеников. Для каждой силы известна прямая ее действия, однако направление силы точно не известно, т. е. сила может действовать вдоль прямой ее действия либо в одну, либо в другую сторону.

Необходимо найти наименьший круг с центром в начале координат, такой, что точка в момент времени t = 1 сек гарантированно находится внутри круга либо на его границе.

Формат ввода-вывода:

Программа levitation читает с клавиатуры (стандартного устройства ввода) целое число N – количество прямых действия сил (1 <= N <= 10⁵). Затем считывается N пар целых чисел (в диапазоне от −10³ до 10³), которые определяют соответствующую прямую, проходящую через центр координат и заданную точку. Модуль силы, действующей вдоль этой прямой, определяется длиной отрезка от начала координат до заданной точки и измеряется в кг∙м/сек².

Программа levitation выводит на экран (стандартное устройства вывода) единственное целое(!) число – квадрат радиуса круга (в м²).

Пример входных и выходных данных: