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

Закодированное сообщение: HPC PJVYMIY

Декодированное сообщение: ACM CONTEST

В этом примере выполнены следующие замены:

H=A, P=C, C=M, J=O, V=N, Y=T, M=E и I=S.

Чтобы не заниматься кодированием и декодированием вручную, подруги просят Вас написать программу. Помогите девочкам!

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

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

Саша увлекается программированием компьютерных игр. Вот уже три для он пишет новую игру для сотового телефона под названием "Битва титанов". Героями игрушки являются оловянные солдатики. В качестве прототипа для описания действий оловянного солдатика Саша взял шахматную ладью.

Шахматная ладья - это фигура, которая может перемещаться на любое количество клеток по вертикали или горизонтали. Ладьи не могут перемещаться за препятствия. Задача - вычислить максимальное количество ладей, которые можно поставить на доске так, чтобы никакие две не били друг друга. Это означает, что конфигурация правильна при условии, что никакие две ладьи не находятся на одной горизонтали или вертикали в пределах видимости друг друга.

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

Помогите Саше поскорее закончить программу и вычислите максимальное количество ладей на заданной конфигурации доски.

Ира начала изучать в школе квадратные, кубические и прочие корни из целых чисел. Корни Иринке даются с трудом, поэтому старшая сестра Вера решила показать младшей сестренке разные примеры. А чтобы самой не тратить время на вычисление корней, Вере нужна программа, которая вычислит нужные числа. Работать эта программа должна очень просто: даны положительные целые числа \(B\) и \(N\). Нужно найти такое целое число \(A\), что \(A^N\) есть наиболее близкое число к \(B\). Заметим, что \(A^N\) может быть меньше, равно или больше \(B\).

У Васиной бабушки в саду растет много разных плодовых деревьев. Одно грушевое дерево она посадила в день рождения Васи и сказала, что как только оно начнет плодоносить, Вася должен съедать все созревшие на нем груши. В этом году на Васиной груше впервые появились плоды. Вася пересчитал все плоды - их оказалось \(N\) штук. Как только поспели первые груши, Вася пересчитал их и съел. Их было \(K\) штук - замечательных, огромных и сочных. Оказалось, что каждый день поспевает на \(M\) штук больше, чем в предыдущий день. Бабушка сказала, что груши очень полезны для Васиного здоровья, и, следовательно, каждый день Вася должен есть их как можно больше. К счастью, груши оказались такими вкусными, что каждый день Вася съедает все поспевшие в этот день и радует этим свою бабушку.

Сколько груш Вася съест в последний день, когда созреет \(N\)-я груша?