В крайних клетках полоски шириной в одну клетку и длиной в $$$N$$$ клеток сидят лягушка и кузнечик: лягушка в клетке № 1, кузнечик в клетке № $$$N$$$. Каждую секунду лягушка прыгает в сторону кузнечика, и одновременно кузнечик прыгает в сторону лягушки. Лягушка может прыгать только на две или на три клетки, кузнечик — только на одну или на две клетки. За какое наименьшее время они смогут оказаться в одной клетке?

Решения, правильно работающие при $$$N \leq 30$$$, будут оцениваться в 30 баллов.

Решения, правильно работающие при $$$N \leq 10^5$$$, будут оцениваться в 50 баллов.

Дан прямоугольник из $$$N\times M$$$ квадратов. Назовём квадраты на границе прямоугольника крайними. Расстоянием от какого-либо квадрата до края назовём количество перемещений, которое нужно сделать из данного квадрата в соседний по стороне квадрат, чтобы добраться от данного квадрата до крайнего квадрата. Квадраты с максимальным расстоянием до края, будем называть центральными. При этом квадрат может быть одновременно и крайним, и центральным.

На рисунке изображён прямоугольник для $$$N=7$$$ и $$$M=8$$$, в каждом квадрате которого записано расстояние от этого квадрата до края. У этого прямоугольника два центральных квадрата.

По данным $$$N$$$ и $$$M$$$ определите количество центральных квадратов в прямоугольнике.

Решения, правильно работающие, когда входные числа не превосходят $$$100$$$, будут оцениваться в 30 баллов.

Решения, правильно работающие, когда входные числа не превосходят $$$10^5$$$, будут оцениваться в 60 баллов.

Решив запастись ручками на весь новый учебный год, Игорь подсчитал, что ему нужно $$$M$$$ ручек.

В его любимом интернет-магазине есть удобная функция — он может сразу добавить в заказ упаковку из любого числа ручек от $$$1$$$ до $$$N$$$. Правда, оказалось, что нельзя добавить в заказ две упаковки одного размера. Например, если Игорю нужно купить $$$M=12$$$ ручек, а максимальное число ручек в упаковке $$$N=10$$$, то Игорь может добавить в заказ упаковку из $$$7$$$ ручек и упаковку из $$$5$$$ ручек, но не сможет добавить две упаковки из $$$6$$$ ручек.

Сформируйте заказ на $$$M$$$ ручек, используя минимальное число различных упаковок.

Решения, правильно работающие при $$$N \le 10^5$$$, будут оцениваться в 40 баллов.

В левом верхнем углу прямоугольного поля размера $$$N \times M$$$ сидит Черепашка. Она хочет закрасить некоторые клетки по спирали, закручивающейся к центру, как на рисунке:

Определите, сколько клеток ей придётся закрасить.

Решения, правильно работающие, когда числа $$$N$$$ и $$$M$$$ не превосходят 100, будут оцениваться в 40 баллов.

Решения, правильно работающие, когда числа $$$N$$$ и $$$M$$$ не превосходят $$$10^5$$$, будут оцениваться в 60 баллов.

Вы получили доступ к одной из камер наблюдения в особо секретной огранизации. В зоне видимости камеры находится табло, с которого вы постоянно считываете информацию. Теперь вам нужно написать программу, которая по состоянию табло определяет, какая буква изображена на нём в данный момент. Табло представляет из себя квадратную таблицу, разбитую на $$$n\times n$$$ равных квадратных светодиодов. Каждый диод либо включён, либо выключен. Введём систему координат, направив ось $$$OX$$$ вправо, а ось $$$OY$$$ — вверх, приняв сторону диода равной 1.

На табло могут быть изображены только следующие буквы:

• I — прямоугольник из горящих диодов.
• O — прямоугольник из горящих диодов с углами $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$, внутри которого есть прямоугольник из выключенных диодов с координатами углов $$$(x_3, y_3)$$$ и $$$(x_4, y_4)$$$. При этом границы выключенного прямоугольника не должны касаться внешнего, то есть $$$x_1 \lt x_3 \lt x_4 \lt x_2$$$ и $$$y_1 \lt y_3 \lt y_4 \lt y_2$$$.
• C — прямоугольник из горящих диодов с углами $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$, внутри которого есть прямоугольник из выключенных диодов с координатами углов $$$(x_3, y_3)$$$ и $$$(x_4, y_4)$$$. При этом правая граница выключенного прямоугольника находится на правой границе внешнего прямоугольника, то есть $$$x_1 \lt x_3 \lt x_4 = x_2$$$ и $$$y_1 \lt y_3 \lt y_4 \lt y_2$$$.

  

• L — прямоугольник из горящих диодов с углами $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$, внутри которого есть прямоугольник из выключенных диодов с координатами углов $$$(x_3, y_3)$$$ и $$$(x_4, y_4)$$$. При этом правые верхние углы выключенного прямоугольника и внешнего прямоугольника совпадают, то есть $$$x_1 \lt x_3 \lt x_4 = x_2$$$ и $$$y_1 \lt y_3 \lt y_4 = y_2$$$.
• H — прямоугольник из горящих диодов с углами $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$, внутри которого находятся 2 прямоугольника из выключенных диодов с координатами углов $$$(x_3, y_3)$$$, $$$(x_4, y_4)$$$ у первого и $$$(x_5, y_5)$$$, $$$(x_6, y_6)$$$ у второго. При этом выключенные прямоугольники должны иметь одинаковую ширину, находиться строго один под другим, один прямоугольник должен касаться верхней стороны, а другой прямоугольник должен касаться нижней стороны внешнего прямоугольника, то есть $$$x_1 \lt x_3 = x_5 \lt x_4 = x_6 \lt x_2$$$ и $$$y_1 = y_3 \lt y_4 \lt y_5 \lt y_6 = y_2$$$.

  

• P — прямоугольник из горящих диодов с углами $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$, внутри которого находятся 2 прямоугольника из выключенных диодов с координатами углов $$$(x_3, y_3)$$$, $$$(x_4, y_4)$$$ у первого и $$$(x_5, y_5)$$$, $$$(x_6, y_6)$$$ у второго. При этом правый нижний угол первого выключенного прямоугольника должен совпадать с правым нижним углом внешнего прямоугольника, а другой выключенный прямоугольник должен находиться строго выше и не касаться границ других прямоугольников, также левые границы двух выключенных прямоугольников должны совпадать, то есть $$$x_1 \lt x_3 = x_5 \lt x_6 \lt x_4 = x_2$$$ и $$$y_1 = y_3 \lt y_4 \lt y_5 \lt y_6 \lt y_2$$$.

  

• Любое другое состояние табло считается буквой X.

По виду табло определите, какая буква на нём изображена.