XIX Всеукраинская олимпиада по информатике

Первый тур

Делители

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

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

Задание

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

Входные данные

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

Выходные данные

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

Пример входных и выходных данных

DIVISOR.DAT	DIVISOR.SOL
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, т.к. в секторе снизу нет ни одного ярлыка.

Задание

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

Входные данные

Первая строка входного файла DESKTOP.DAT содержит три целых числа: 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-координата.

Выходные данные

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

Пример входных и выходных данных

DESKTOP.DAT	DESKTOP.SOL
8 1 4 5 4 a 2 3 b 3 2 h 0 3 c 4 6 d 7 6 e 7 2 f 9 6 g	1

Экзамен

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

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

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

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

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

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

Задание

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

Входные данные

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

Выходные данные

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

Пример входных и выходных данных

EXAM.DAT	EXAM.SOL
5 5 1 2 1 4 1 5 3 2 3 5	1 2 3 4

 

XIX Всеукраинская олимпиада по информатике

Второй тур

Поиск строки

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

Задание

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

Входные данные

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

Выходные данные

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

Пример входных и выходных данных

SUBSTR.DAT	SUBSTR.SOL
abcabcdabc bacdbca	abcd

Счастливый билет

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

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

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

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

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

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

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

Задание

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

Входные данные

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

Выходные данные

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

Примеры входных и выходных данных

LUCKY.DAT	LUCKY.SOL
840 182836	1 8 2 836
120 000001	0

Расстояние

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

Задание

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

Входные данные

Первая строка входного файла DIST.DAT содержит единственное целое число – количество точек N
(3≤N≤700) заданных на плоскости. Далее следует N строк, каждая из которых задает точку плоскости в формате “x y” (-5000≤x, y≤5000), x и y – целые числа. Никакие две точки не имеют одинаковых координат.

Выходные данные

Единственная строка выходного файла DIST.SOL должна содержать наибольшее расстояние от одной из заданных точек, до прямой, построенной на двух других точках, с точностью до 10^-6. Ответ должен быть записан в формате с точкой (<целая часть>.<дробная часть>)

Пример входных и выходных данных

DIST.DAT	DIST.SOL
5 1 4 2 0 2 4 3 5 4 4	4.242641