Магистр Йода известен тем, что использует необычный порядок слов. Эта особенность имеет еще одно следствие. Когда магистр называет какое-то расстояние, площадь или объем, он использует множество приставок системы Си. Каждая приставка системы Си умножает единицу измерения на некоторую степень десяти. Например, он может сказать «megananokilogigamicrometer», что будет соответствовать $$$10^3$$$ метрам. Если речь идет об объёме, то он может сказать «millimeter$$$^3$$$», что будет соответствовать $$$10^{-9}$$$ метрам кубическим.

Магистр использует только следующие приставки:

Например, если Йода сказал «megananokilogigamicrometer», то это равно $$$10^6 \cdot 10^{-9} \cdot 10^3 \cdot 10^9 \cdot 10^{-6}$$$ метрам или $$$10^3$$$ метрам. Правила применения приставок к квадратным и кубическим величинам также являются стандартными. Например, один кубический метр равен $$$10^6$$$ кубическим сантиметрам.

К сожалению, C-3PO рядом не оказалось, и вам нужно самостоятельно расшифровать, что именно сказал Йода. Переведите единицу измерения, которую назвал Йода, в метры, метры квадратные или метры кубические, в зависимости от разрядности исходной единицы измерения. Несложно показать, что у вас получится величина, равная $$$10^x$$$ (метров, метров квадратных или метров кубических), где $$$x$$$ — целое число. Выведите $$$x$$$.

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

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

Сегодня класс молодых джедаев получил задание посчитать значение выражения, состоящего из неотрицательных целых чисел и знаков «+» и «-». Однако, просто вычислять значение выражения было бы скучно. Поэтому, магистр Йода сказал своим ученикам использовать Силу и удалить из выражения ровно один символ, чтобы значение получившегося выражения было максимальным возможным. В получившемся выражении разрешены числа с ведущими нулями. Гарантируется, что после удаления любого символа, выражение останется корректным.

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

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

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

Пещера, в которой находится вход в храм, имеет размеры $$$n \times m$$$ метров, и поделена на квадраты размера $$$1 \times 1$$$ метр. Представим пещеру в виде таблицы $$$n \times m$$$, строки которой пронумерованы от $$$1$$$ до $$$n$$$ сверху вниз, а столбцы — от $$$1$$$ до $$$m$$$ слева направо. В некоторых квадратах находятся рунические камни, а остальные квадраты свободны. Кэл может перемещаться только по свободным квадратам. За единицу времени он может переместиться из квадрата в соседний по стороне.

Сейчас Кэл находится в некотором квадрате пещеры. Чтобы открыть вход в храм, нужно в правильном порядке коснуться нескольких рунических камней. После чего, Кэл должен дойти до квадрата, в котором откроется вход в храм. Чтобы коснуться рунического камня, расположенного в некотором квадрате, Кэл должен встать в квадрате, соседнем по стороне. На то, чтобы коснуться камня, Кэл не тратит дополнительного времени.

За Кэлом гонятся инквизиторы Империи, и он хочет узнать, за какое минимальное время можно открыть замок и войти в храм. Помогите ему узнать эту величину.

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

R2-D2 решает кроссворд, составленный специально для дроидов. В этом кроссворде в клеточки нужно писать не буквы, а цифры.

Кроссворд представляет из себя клетчатое поле $$$n \times m$$$. Некоторые клетки заблокированы, а все остальные — свободные. Словом в кроссворде назовем максимальный по включению вертикальный или горизонтальный отрезок свободных клеток. Иными словами, слово — это отрезок клеток одного столбца или строки, ограниченный с обоих сторон краем поля или заблокированными клетками.

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

Помогите R2-D2 решить кроссворд так, чтобы суммарное изменение цифр было минимально. Несложно заметить, что всегда есть способ заполнить кроссворд так, чтобы все слова были палиндромами. Например, заполнить все свободные клетки одинаковыми цифрами. Поэтому, решение всегда существует.

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

Граф Дуку хочет отправить отряд дроидов на важное задание. Перед ним стоит шеренга из $$$n$$$ дроидов, пронумерованных от $$$1$$$ до $$$n$$$ слева направо. Граф решил выбрать в качестве отряда подотрезок этой шеренги. То есть, всех дроидов с номерами от $$$l$$$ до $$$r$$$ для некоторых $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$). Каждый дроид характеризуется своим AIQ — коэффициентом искусственного интеллекта. AIQ дроида номер $$$i$$$ равен $$$a_i$$$.

Дроиды, находящиеся в одном отряде, могут объединяться в более продвинутых дроидов. Если в отряде есть два дроида с одинаковым AIQ, равным $$$x$$$, они могут объединиться в одного дроида с AIQ равным $$$x + 1$$$.

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

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