Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Положение] [Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

Задачи олимпиады "Муниципальный этап ВОШ Красноярского края по информатике, 9-11 классы"

Задача A. Словесная запись числа

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Дано целое число N. Требуется определить количество букв в его словесной записи на русском языке. Например, число 145 записывается как «сто сорок пять» с использованием 12 букв.

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

Входной файл INPUT.TXT содержит целое число N (0 ≤ N ≤ 106).

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

В выходной файл OUTPUT.TXT выведите целое число – количество букв в словесной записи числа N.

Примеры

INPUT.TXTOUTPUT.TXT
123
214512
3114518
46392641

Система оценки

Решения, работающие только для N < 10, будут оцениваться в 20 баллов.

Решения, работающие только для N < 100, будут оцениваться в 40 баллов.

Решения, работающие только для N < 1000, будут оцениваться в 60 баллов.


Задача B. Ёлочка

(Время: 1 сек. Память: 16 Мб Баллы: 100)

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

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

Входной файл INPUT.TXT содержит целые числа M и N – размер основания первого уровня и количество уровней соответственно (3 ≤ M < 50, 1 ≤ N ≤ 50, M - нечётно).

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

В выходной файл OUTPUT.TXT выведите прямоугольник, состоящий из символов «.» и «*», который отражает ёлочку. Ширина прямоугольника должна соответствовать ширине последней строки нижнего уровня ёлочки.

Примеры

INPUT.TXTOUTPUT.TXT
13 1.*.
***
25 2...*...
..***..
.*****.
...*...
..***..
.*****.
*******

Система оценки

Решения, работающие только для 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.TXTOUTPUT.TXT
11 1 10
22 3 49
33 6 533

Система оценки

Решения, работающие только для 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» (без кавычек).

Примеры

INPUT.TXTOUTPUT.TXT
15 3
Ivanov 09:00 13:30
Petrov 05:30 10:00
Sidorov 09:30 14:00
Orlov 13:30 16:15
Frolov 13:00 17:00
Ivanov 2
Petrov 1
Sidorov 3
Orlov 2
Frolov 1
22 1
Kuznetsov 09:00 12:00
Bobrov 11:59 13:20
No solution

Система оценки

Решения для N ≤ M будут оцениваться в 20 баллов.

Решения для 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.TXTOUTPUT.TXTПояснение
15 34
23 11

Система оценки

Решения, работающие только для N ≤ 5, будут оцениваться в 20 баллов.



Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483