По заданному натуральному числу N необходимо вычислить количество натуральных чисел, которые есть делителями N! (факториала числа N).

Например, при N=4, N!=4·3·2·1=24. Это число имеет следующие делители: 1, 2, 3, 4, 6, 8, 12, 24. Таким образом, искомое количество составляет 8.

Напишите программу, которая по натуральному N, находит количество делителей его факториала.

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

Единственная строка входного файла содержит одно целое число N (1≤N≤45).

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

Единственная строка выходного файла должна содержать одно целое число –найденное количество делителей числа N!

4

8

На рабочем столе операционной системы расположено N ярлыков, каждый из которых задан целыми координатами x и y, а также названием. Название ярлыка состоит из маленьких символов латинского алфавита (a-z). Необходимо перейти (т.е. переместить выделение) с выделенного ярлыка S к ярлыку F, с помощью клавиатуры, использовав наименьшее возможное количество нажатий. Переход осуществляется с помощью нажатий на клавиши с буквами a-z, либо на стрелки “↑”,“↓”,“←” и “→”.

При нажатии на клавиши с буквами переход происходит по следующим правилам:

1. Если на рабочем столе находятся ярлыки, название которых начинается на нажатую букву, и выделен один из них, то переход происходит на ярлык, с названием, следующим в лексикографическом порядке среди тех, которые начинаются на эту букву (после последнего выделение переходит на первый). Т.е. если есть ярлыки a, ab, b, то при нажатии a выделение будет переходить только между a и ab.

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

3. Если на рабочем столе нет ярлыков, название которых начинается на нажатую букву, переход не осуществляется.

При нажатии на стрелку переход происходит на ближайший в обычном геометрическом смысле ярлык, который лежит в секторе стрелки. Определим сектор стрелки как прямой угол с вершиной в выделенном ярлыке, биссектрисой которого есть луч, соответствующий стрелке. Если ярлык лежит на границе сектора, то он относится к верхнему или нижнему сектору (а не к правому или левому). Если в определенном секторе нет ни одного ярлыка, то переход не осуществляется. Если ближайших ярлыков несколько, то выбирается ярлык с наименьшей x координатой, а если и таких несколько, то выбирается с наименьшей y-координатой.

Например, если выделен ярлык a (см. рисунок), то при нажатии стрелок могут произойти такие переходы:

1. Стрелка “←”. Выделение переходит на ярлык b, т.к. он есть ближайшим в секторе этой стрелки. При последующем нажатии “←” будет выделен ярлык c.

2. Стрелка “↑”. В секторе стрелки находятся ярлыки d и e. Выделение перейдет на d, который ближе.

3. Стрелка “→”. В секторе “→” находится только ярлык g, на который и перейдет выделение.

4. Стрелка “↓”. В этом секторе находятся ярлыки f и h, которые равноудалены от ярлыка a. Выделение переходит на ярлык h, т.к. x-координата этого ярлыка меньше. Если после этого нажать “↓”, то выделение остается на h, т.к. в секторе снизу нет ни одного ярлыка.

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

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

Первая строка входного файла содержит три целых числа: N (1≤N≤1000) – количество ярлыков на рабочем столе, S (1≤S≤N) – номер выбранного ярлыка, F (1≤F≤N) – номер ярлыка на который требуется перейти. Каждая из последующих N строк задает ярлык в формате «x y text», x, y – целые числа (0≤x, y≤10⁶), а текст содержит не более чем 50, и не менее чем один маленький символ латинского алфавита a-z.

Никакие два ярлыка не имеют одинаковых координат и одинаковых названий. Координатная сетка – стандартная, т.е. “↑” увеличивается y-координата, а “→” x-координата.

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

Единственная строка выходного файла должна содержать одно целое число – минимальное количество нажатий на клавиатуру, которые позволят перейти от ярлыка S к ярлыку F.

7 1 6
10 10 buka
12 15 mama
12 5 papa
18 12 sina
18 8 doch
20 15 vnuk
20 5 vnuchka

2

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

1. Каждый мальчик должен сидеть за одной партой с девочкой. Количество мальчиков должно равняться количеству девочек.

2. В результате наблюдений учитель знает, какие пары мальчиков и девочек не позволяют друг другу списывать. Только такие пары могут сидеть за одной партой.

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

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

Рассмотрим пример класса из пяти учеников. Пусть учитель знает, что мальчика 1 можно посадить вместе с девочками 2, 4, 5, а мальчика 3 с девочками 2 и 5. Тогда максимальное количество пар, которую можно сформировать для того, чтобы посадить в первую аудиторию равно 2. Возможные варианты выбора можно записать так: (1, 2, 3, 4), (1, 2, 3, 5), (1, 3, 4, 5). Среди этих вариантов первый есть лексикографически наименьшим.

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

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

Первая строка входного файла содержит два целых числа: N (1≤N≤50) – количество учеников в классе, M (M≥0) – количество пар мальчиков и девочек, которых учитель может посадить за одну парту. Далее следует M строк, каждая из которых содержит два номера в списке класса – номер мальчика и номер девочки (именно в таком порядке). Во входном файле пары не повторяются. Все номера от 1 до N.

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

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

5 3
1 3
1 4
2 3

1 2 3 4

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

Напишите программу, которая по заданной последовательности находит первую подпоследовательность, состоящую из разных символов.

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

Входной файл содержит последовательность, которая, для удобства, разбита на несколько срок. Каждая строка содержит не более 100 символов. Общая длина последовательности – не более 10 000 000 символов.

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

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

b
b

b

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

1. Сначала номер разбивают на цифры, и определенные соседние цифры объединяют в числа.

2. Между полученных чисел располагают скобки и знаки операций: плюс, минус, умножить, разделить по математическим правилам. Также разрешается использовать унарный минус.

3. Нельзя менять местами цифры.

4. Если удается составить такое выражение, которое после вычисления равняется искомому числу k, то билет считается счастливым.

Операцию «разделить» можно использовать только в случаях, когда вследствие деления будет получено целое число.

Рассмотрим билет номер: 182836. Положим k=840. Разобьем число на четыре: 1, 8, 2, 836. Число k можно получить, например, следующим образом: 1*(8/2+836)=840.

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

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

Единственная строка входного файла содержит два числа: целое k (1≤k≤1000) и номер билета. Номер билета состоит из шести цифр, и может начинаться с 0.

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

Единственная строка выходного файла должна содержать любой из возможных наборов чисел, на которые может быть разбит номер билета для получения числа k. Если число не может быть получено, то единственная строка выходного файла должна содержать цифру 0 (нуль).

58 830663

8 3 0 6 63
8 3 0 66 3
8 3 06 63
8 3 066 3
8 30 6 6 3
8 30 66 3