Задачи олимпиады "Муниципальный этап Всероссийской олимпиады школьников Красноярского края по информатике, 9-11 классы"
Задача A. Дорожная политика
(Время: 1 сек. Память: 16 Мб Баллы: 100)
В некотором государстве приближается транспортная реформа, в результате которой предстоит соединить все N городов дорогами. Требуется определить общее количество дорог в государстве по завершении их строительства.
Входные данные
Входной файл INPUT.TXT содержит натуральное число N – количество городов (N ≤ 4∙109).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
2
1
2
4
6
Система оценки
Решения для N ≤ 104 оцениваются в 40 баллов. Решения для N ≤ 106 оцениваются в 60 баллов.
Задача B. Спичрайтер Йоды
(Время: 1 сек. Память: 16 Мб Баллы: 100)
У каждого общественного деятеля есть собственный спичрайтер – некто, помогающий в подготовке публичной речи, тот, кто делает ее более выразительной и интересной.
Это относится и к главе Ордена джедаев магистру Йоде, известному нам своими подвигами в «Звездных войнах». На первый взгляд может показаться, что спичрайтеру Йоды приходится тяжелее других: все-таки речь магистра своеобразна и ее изучение требует серьезных усилий. На самом деле все несколько проще. Спичрайтеру Йоды достаточно сначала придумать речь для обычного человека, после чего поменять порядок слов в каждом предложении на обратный. В силу того, что алгоритм преобразования обычной речи в речь магистра Йоды достаточно однообразен, спичрайтер решил автоматизировать этот процесс и попросил Вас написать программу, которая будет преобразовывать речь, составленную им для обычного человека в речь для Йоды.
Входные данные
В единственной строке входного файла INPUT.TXT задана речь, составленная спичрайтером. Речь состоит из предложений, отделенных друг от друга точками (точка ставится сразу после последнего слова в предложении). Каждое предложение состоит из слов. Предложение содержит, по крайней мере, одно слово. Соседние слова разделены ровно одним пробелом. Слово – непустая последовательность строчных английских букв. Строка не содержит лишних пробелов. Гарантируется, что строка не пуста и ее длина не превосходит 20000 символов.
Выходные данные
В выходной файл OUTPUT.TXT выведите преобразованную для Йоды речь в соответствии с форматом входных данных. Следует строго соблюдать формат вывода речи, описанный во входных данных.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
you should solve this problem. its easy.
problem this solve should you. easy its.
Система оценки
Решения для предложений, состоящих из одного слова, оцениваются в 10 баллов. Решения для одного предложения оцениваются в 40 баллов.
Задача C. Прыжки в длину
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Прыжки в длину – одна из популярных дисциплин легкой атлетики. Участники соревнований выполняют 6 попыток, каждая из которых измеряется с точностью до сантиметра. Попытки с заступом не идут в зачет и помечаются как «x». Побеждает спортсмен, показавший самый дальний прыжок в одной из попыток. В случае равенства лучшего результата преимущество отдается спортсмену, показавшему лучший второй прыжок, при равенстве двух лучших рассматривается лучший третий результат и т.д.
По имеющемуся протоколу соревнований требуется определить тройку победителей.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое N – количество участников соревнований (1 ≤ N ≤ 100). Далее следует N строк, каждая из которых представляет результаты выступления отдельного спортсмена в следующем формате:
CNT Name Surname N1 N2 N3 N4 N5 N6
Первые параметры определяют страну, имя и фамилию участника – строки из английских символов, каждая из которых не превышает 80 символов. Ni – значения прыжков в метрах, записанные с двумя знаками после точки (0 ≤ Ni ≤ 8.95, 1 ≤ i ≤ 6) в случае успешной попытки, либо обозначенные символом «x» (ASCII 120) в противном случае. Все параметры строки разделены пробелами (до 80 пробелов между двумя параметрами). Гарантируется, что в протоколе нет спортсменов с зачетными попытками и равными результатами.
Выходные данные
В выходной файл OUTPUT.TXT выведите тройку победителей согласно приведенному в примерах формату (лишние пробелы допускаются). Если победителей 1 или 2, следует вывести только их. Спортсменов без зачетных попыток следует проигнорировать. Если невозможно выявить ни одного победителя, то следует вывести «No results.».
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
8
GER Christian Reif 8.18 x 8.22 8.12 8.12 7.96
RSA Godfrey Mokoena 8.00 7.91 7.87 7.93 8.01 8.10
BRA Mauro Silva x x 8.09 8.05 8.23 8.24
MEX Luis Rivera 7.92 8.16 8.17 8.03 8.27 x
ESP Eusebio Caceres 8.09 8.25 8.17 x 8.26 8.20
RUS Aleksandr Menkov 8.14 7.96 8.52 8.43 8.56 x
JAM Damar Forbes 8.02 7.89 x x 8.00 x
NED Ignisious Gaisah 8.09 8.15 8.17 8.29 x 8.16
1) RUS Aleksandr Menkov 8.56
2) NED Ignisious Gaisah 8.29
3) MEX Luis Rivera 8.27
2
3
USA John Smith 8.25 8.14 8.01 7.99 7.23 6.92
RUS Evgeny Kuznetsov 8.25 8.14 8.02 7.15 x 6.93
FRA Lucas Martin x x x x x x
1) RUS Evgeny Kuznetsov 8.25
2) USA John Smith 8.25
3
2
USA Freddy Krueger x x x x x x
RUS Fedya Krukov x x x x x x
No results.
Задача D. Офисы
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Однажды N фирм арендовали довольно необычное N-этажное N-подъездное здание, где в каждом подъезде на каждом этаже линейно располагается N одинаковых комнат. В доме нет коридоров и дополнительных помещений. Так, дом похож на куб, состоящий из N3 комнат. Более того, в каждой комнате имеются двери, ведущие в смежные комнаты, включая те, что расположены сверху или снизу. Подобная архитектура дома позволяет легко перемещаться в смежные помещения. Однако если комнаты расположены далеко друг от друга, то в оптимальном маршруте может быть достаточно много комнат.
Вам поручили спроектировать распределение офисов фирм по комнатам в данном доме. Сотрудники каждой фирмы очень часто контактируют друг с другом, а также каждая фирма работает со всеми другими фирмами. Для наиболее эффективной работы должны выполняться следующие условия:
у каждой фирмы должен быть офис, т.е. хотя бы одна комната;
каждая комната должна принадлежать какой-либо фирме;
между любыми комнатами, принадлежащими одной фирме должен быть маршрут без выхода за пределы офиса данной фирмы;
для любых двух фирм должна быть хотя бы одна дверь, их связывающая.
Входные данные
Входной файл INPUT.TXT содержит натуральное число N – количество фирм (N ≤ 26).
Выходные данные
В выходной файл OUTPUT.TXT выведите любой проект распределения комнат по фирмам, удовлетворяющий условиям задачи. Если решения нет, то выведете «No solution.», в противном случае следует вывести N строк, где в каждой строке через пробел описан проект текущего подъезда: N элементов, каждый из которых состоит из N символов, описывающих план размещения для конкретного этажа. Для обозначения принадлежности комнат различным фирмам следует использовать различные заглавные английские буквы.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
2
AA BB AA BB
2
3
AAA AAA CCC AAA ABC CCC
AAA CCC CCC
Система оценки
Решения для N ≤ 6 будут оцениваться в 20 баллов.
Задача E. Треугольник и окружности
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Известно, что для любого треугольника существуют как вписанная в него, так и описанная около него окружности, которые определяются однозначно.
Центром вписанной окружности служит точка пересечения биссектрис треугольника, а точка пересечения серединных перпендикуляров к сторонам треугольника представляет собой центр описанной около него окружности. Радиус вписанной окружности равен расстоянию от ее центра до любой из сторон треугольника, в то время, как радиус описанной окружности соответствует расстоянию от ее центра до любой из вершин треугольника.
По заданным координатам вершин треугольника (x1,y1), (x2,y2) и (x3,y3) требуется найти центр и радиус либо вписанной, либо описанной около него окружности.
Входные данные
Первая строка входного файла INPUT.TXT содержит 6 вещественных чисел x1, y1, x2, y2, x3, y3 – координаты вершин треугольника ненулевой площади. Все числа не превышают 100 по абсолютной величине. Во второй строке записана команда «In» (вписанная) или «Out» (описанная), определяющая тип окружности, которую следует найти.
Выходные данные
В выходной файл OUTPUT.TXT выведите через пробел координаты центра (x,y) и радиус r искомой окружности. Все значения следует выводить с точностью не меньшей, чем 10-3.
Примеры
№
INPUT.TXT
OUTPUT.TXT
Рисунок к примерам
1
2 3 6 1 7 5 In
5.14 2.87 1.288
2
2 3 6 1 7 5 Out
4.72222 3.44444 2.758
Система оценки
Решения для равносторонних треугольников оцениваются в 20 баллов. Решения для прямоугольных треугольников с поиском описанной окружности оцениваются в 30 баллов.
