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

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

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

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

Обратите внимание, что порядок сторон администратору сайта важен: если на оригинальной фотографии ширина была w, а высота h, а у найденного прямоугольника ширина (т. е. сторона, параллельная горизонту)w , а высота (т. е. вторая сторона) h, то должно быть , а не .

Написать рекурсивную программу перевода целых чисел, не превосходящих 10⁹, из десятичной системы счисления в P-ичную (1  ≤  P  ≤  36)

На вход программе подаются 3 целых неотрицательных числа x, N и P,  не превосходящих 2 * 10⁹. Кроме того P > 0. Требуется вычислить значение x в степени N по модулю P.

Петя с Андреем играют в интересную игру. Для этой игры им необходимо k шоколадок, каждая из которых имеет форму прямоугольника – i-ая из них имеет размер w_i на h_i долек.

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

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

Ваша задача — определить, кто из игроков выиграет при оптимальной игре обоих.

Рассмотрим последовательность n целых чисел от 1 до m. Подпоследовательность подряд идущих чисел называется рефреном, если произведение ее длины на количество вхождений в последовательность максимально.

По заданной последовательности требуется найти ее рефрен.