Задачи олимпиады "Муниципальный этап ВОШ Красноярского края по информатике, 9-11 классы"
Задача A. Словесная запись числа
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Дано целое число N. Требуется определить количество букв в его словесной записи на русском языке. Например, число 145 записывается как «сто сорок пять» с использованием 12 букв.
Входные данные
Входной файл INPUT.TXT содержит целое число N (0 ≤ N ≤ 106).
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – количество букв в словесной записи числа N.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
2
3
2
145
12
3
1145
18
4
63926
41
Задача B. Ёлочка
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Необходимо нарисовать ёлочку, состоящую из N уровней. Каждый из уровней представляет собой равнобедренный треугольник, состоящий из звёздочек. Первая строка каждого уровня содержит одну звездочку. Каждая последующая строка имеет на две звездочки больше предыдущей. Первый уровень имеет M звёздочек в основании, каждый последующий повторяет предыдущий с добавлением одной строки. Все линии из звёздочек должны быть выровнены по центру.
Входные данные
Входной файл INPUT.TXT содержит целые числа M и N – размер основания первого уровня и количество уровней соответственно (3 ≤ M < 50, 1 ≤ N ≤ 50, M - нечётно).
Выходные данные
В выходной файл OUTPUT.TXT выведите прямоугольник, состоящий из символов «.» и «*», который отражает ёлочку. Ширина прямоугольника должна соответствовать ширине последней строки нижнего уровня ёлочки.
Решения, работающие только для M=3 и N ≤ 10, будут оцениваться в 20 баллов.
Решения, работающие только для N=1, будут оцениваться в 20 баллов.
Решения, работающие только для M=3, будут оцениваться в 40 баллов.
Задача C. Робот Гильберта
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Кривая Гильберта порядка N – самоподобная непрерывная ломаная, заполняющая квадрат 2N x 2N и проходящая через все клетки данного квадрата. Каждая кривая N-го порядка строится рекурсивно: квадрат делится на 4 части и в каждой из частей рисуется кривая (N-1)-го порядка. При этом верхние части остаются без изменений, а нижние поворачиваются на 90 градусов в разные стороны. Далее, все части соединяются тремя отрезками, образуя непрерывную ломаную.
На следующем рисунке показаны первые три кривые:
Робот начал свое движение по кривой Гильберта из клетки с координатами (1,1) и в некоторый момент остановился в клетке с координатами (X,Y). Ваша задача – определить количество шагов, которые он сделал, чтобы попасть в данную клетку. За шаг следует считать перемещение в соседнюю клетку.
Входные данные
Входной файл INPUT.TXT содержит натуральные числа N, X и Y (N ≤ 30, X,Y ≤ 2N). Здесь N – порядок кривой Гильберта, (X,Y) – координата робота.
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
1 1 1
0
2
2 3 4
9
3
3 6 5
33
Система оценки
Решения, работающие только для N ≤ 3, будут оцениваться в 20 баллов.
Решения, работающие только для N ≤ 10, будут оцениваться в 70 баллов.
Задача D. Шкафчики
(Время: 5 сек. Память: 16 Мб Баллы: 100)
Тренажерный зал в течение суток планирует принять N клиентов, время прихода и ухода каждого из них определено с точностью до минуты. Находясь в тренажерном зале, клиент занимает один из M шкафчиков для раздевалок. Шкафчики в учреждении нумеруются целыми числами от 1 до M.
По заданному расписанию визитов клиентов требуется распределить шкафчики таким образом, чтобы каждый человек в свое время посещения использовал отдельный шкафчик.
Входные данные
Первая строка входного файла INPUT.TXT содержит целые числа N и M – количество клиентов и шкафчиков соответственно. Каждая из последующих N строк содержит информацию о клиенте: фамилию, время прихода и время ухода, разделенные пробелом. Фамилия содержит от 1 до 10 символов английского алфавита. Время прихода строго меньше времени ухода. Каждое из времен имеет формат ЧЧ:ММ (1 ≤ N, M ≤ 105, 00:00 ≤ ЧЧ:ММ ≤ 23:59).
Выходные данные
В выходной файл OUTPUT.TXT выведите фамилии клиентов и номера занимаемых ими шкафчиков в той же последовательности, в которой они заданы во входных данных. Если существует несколько решений, выведите любое. Если решения не существует, выведите «No solution» (без кавычек).
Решения для N ≤ 1000 будут оцениваться в 60 баллов.
Задача E. Изоморфизм
(Время: 2 сек. Память: 16 Мб Баллы: 100)
Граф – математический объект, состоящий из вершин и ребер, где каждое ребро соединяет пару вершин. Обычно в графическом представлении вершины обозначают точками, а ребра – отрезками. Будем рассматривать неориентированные невзвешенные графы (нет кратных ребер, ребра не имеют длины и направления).
Матрица смежности – это квадратная матрица (таблица) N x N, однозначно описывающая структуру графа. Если все вершины графа пронумерованы от 1 до N, то в i-й строке и j-м столбце матрицы смежности стоит 1, если существует ребро между i-й и j-й вершинами, в противном случае – стоит 0.
Изоморфные графы – идентичные графы с точностью до изменения нумерации вершин. При определенной нумерации вершин изоморфных графов их матрицы смежности совпадают. Графы с различным числом вершин или ребер не являются изоморфными.
Требуется вычислить количество попарно неизоморфных графов с N вершинами и M ребрами.
Входные данные
Входной файл INPUT.TXT содержит целые числа N и M (1 ≤ N ≤ 6, 0 ≤ M ≤ N*(N-1)/2).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
№
INPUT.TXT
OUTPUT.TXT
Пояснение
1
5 3
4
2
3 1
1
Система оценки
Решения, работающие только для N ≤ 5, будут оцениваться в 20 баллов.
