Задания

А.  Сокращенное слово

Ограничение по времени: 1 сек.

Ограничение по памяти: 16 МБ

Сложность: 30 баллов

Маша придумала очень простой способ сокращать длинные тексты. Для этого надо в словах вычеркивать одинаковые, рядом стоящие буквы, оставляя только одну из них. Например, непонятное Маше слово «РЕЕСТР» можно сократить до «РЕСТР». Маша даже написала компьютерную программу, которая умеет сокращать слова по придуманному ею правилу.

Формат входных данных

В первой строке входного файла input. txt записано натуральное число N, не превосходящее 100. Во второй строке файла – слово, составленное из N заглавных латинских букв A, B, C, …, Z.

Формат выходных данных

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

Пример

input. txt	output. txt
6 AAASBB	ASB

-------------------------------------------------------------------------------------------B.  Удачный день

Ограничение по времени: 1 сек.

Ограничение по памяти: 16 МБ

Сложность: 40 баллов

Миша вернулся из похода в горы со многими перевалами, подъемами и спусками. В конце каждого дня он записывал, какую высоту ему удалось в этот день покорить. Ещё до похода он решил, что будет считать день «удачным», если в этот день он сумеет подняться выше, чем в предыдущий день.

Требуется выяснить, сколько же «удачных» дней было у Миши за все время его похода?

Формат входных данных

В первой строке входного файла input. txt записано натуральное число N – длительность похода в днях (1 ≤ N ≤ 1000). Во второй строке записаны N натуральных чисел (не превосходящих 1000) – это высоты, которые последовательно, день за днем, покорял Миша.

Формат выходных данных

Выходной файл output. txt должен содержать единственную строку. В ней должно быть записано количество дней, которые, по мнению Миши, оказались «удачными» во время его похода.

Пример

input. txt	output. txt
7 2 5 1 3 4 6 5	3

-------------------------------------------------------------------------------------------C.  Симметричная точка

Ограничение по времени: 1 сек.

Ограничение по памяти: 16 МБ

Сложность: 50 баллов

Маша на уроке геометрии узнала об осевой симметрии и научилась строить точки, симметричные друг другу относительно заданной прямой. Однажды она решила выполнить построения на координатной плоскости. Она провела прямую через точки с координатами (a, 0) и (0, b), а потом построила точку С, которая симметрична точке О (началу координат) относительно этой прямой.

Требуется определить координаты точки С.

Формат входных данных

В единственной строке входного файла input. txt записаны два целых числа a и b – координаты точек, через которые проходит заданная прямая (0 < |a|,|b| ≤ 104).

Формат выходных данных

В первой и второй строках выходного файла output. txt должно быть записано по одному искомому числу – соответственно координаты x и y точки С, симметричной началу координат относительно заданной прямой. Искомые координаты надо вычислить с точностью не менее 6 знаков в дробной части.

Пример

input. txt	output. txt
5 10	8.000000 4.000000

-------------------------------------------------------------------------------------------

D.  Максимальное число

Ограничение по времени: 1 сек.

Ограничение по памяти: 16 МБ

Сложность: 60 баллов

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

Формат входных данных

В единственной строке входного файла input. txt записано натуральное число N, где N ≤ 231.

Формат выходных данных

Единственная строка выходного файла output. txt должна содержать искомое максимальное натуральное число, у которого сумма и произведение цифр – такие же, как у исходного числа N. Гарантируется, что для всякого заданного N искомое число обязательно существует.

Пример

input. txt	output. txt
23	32

-------------------------------------------------------------------------------------------

E.  Разноцветный забор

Ограничение по времени: 1 сек.

Ограничение по памяти: 16 МБ

Сложность:100 баллов

Мише предстоит покрасить на даче забор из вертикальных досок разными красками. Чтобы не было скучно, он решил красить каждую доску в определенный цвет, но так, чтобы любые две соседние доски были покрашены в разные цвета. А поскольку участок, огороженный забором, имеет круглую форму, то у каждой доски в заборе есть две соседних доски. Миша решил всё продумать заранее, пронумеровал доски и каждому номеру подобрал цвет.

Требуется выяснить, сколько существует разных способов покрасить забор, используя не более K красок, если забор состоит из N досок, а любые две соседние доски должны быть покрашены в разные цвета. Два способа покраски забора считаются разными, если по-разному покрашена хотя бы одна из досок. При покраске забора не обязательно использовать все имеющиеся краски.

Формат входных данных

В единственной строке входного файла input. txt записаны два натуральных числа K и N – соответственно количество имеющихся красок и досок в заборе, причем 2 ≤ K ≤ 10, 3 ≤ N ≤ 16.

Формат выходных данных

В единственной строке выходного файла output. txt должно быть записано количество различных способов покрасить забор, используя не более K красок так, чтобы любые две соседние доски были покрашены в разные цвета.

Примеры

input. txt	output. txt
2 4	2
3 3	6