Задачи олимпиады "Муниципальный этап ВОШ Красноярского края по информатике, 9-11 классы"
Задача A. Периметр треугольника
(Время: 1 сек. Память: 16 Мб Баллы: 100)
По длинам сторон треугольника требуется вычислить периметр вписанного в него треугольника, вершинами которого являются середины сторон исходного треугольника.
Входные данные
Входной файл INPUT.TXT содержит три натуральных числа – длины сторон треугольника, не превышающие 5•1018.
Выходные данные
В выходной файл OUTPUT.TXT выведите периметр вписанного треугольника с одной цифрой после запятой, округленный до десятых.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
3 3 3
4.5
2
3 4 5
6.0
Система оценки
Решения, работающие с длинами сторон до 108, будут оцениваться в 60 баллов.
Задача B. Клеточное поле
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Под клеточным полем будем понимать прямоугольник на плоскости, состоящий из квадратных черных и белых клеток, причем цвета смежных клеток должны отличаться. Примером такого поля служит черно-белая шахматная доска.
Требуется отобразить клеточное поле N×M с размером клеток K×K.
Входные данные
Входной файл INPUT.TXT содержит три целых числа: N, M и K – размеры поля и клеток (1 ≤ N, M, K ≤ 10).
Выходные данные
В выходной файл OUTPUT.TXT выведите клеточное поле N×M (N клеток по вертикали и M клеток по горизонтали), с размером клеток K×K. Следует использовать английскую букву «X» для заполнения черных клеток и «.» (точка) – для белых. Также следует учесть, что левая нижняя клетка должна быть окрашена в черный цвет.
Решения, работающие только для N=M и K=1, будут оцениваться в 30 баллов.
Решения, работающие только для K=1, будут оцениваться в 50 баллов.
Решения, работающие только для N=M, будут оцениваться в 70 баллов.
Задача C. Считалочка
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Дети решили поиграть в прятки. Для выбора ведущего они встали в круг и начали считаться, используя известную считалочку. Показывая пальцем по очереди на каждого стоящего в кругу, считающий произносит одно слово, и тот, на кого придется последнее слово, и будет водить.
Требуется по данной считалочке и именам детей определить того, кто будет водить.
Входные данные
Первая строка входного файла INPUT.TXT содержит считалочку, которая состоит из слов. Во второй строке перечислены имена детей в том порядке, в котором они стоят. Слова считалочки и имена ребят представляют собой от 1 до 10 букв английского алфавита (возможно, что в различном регистре). Слова и имена отделены друг от друга как минимум одним пробелом. Также допустимы пробелы, как в начале, так и в конце каждой строки. Гарантируется, что во входных данных есть хотя бы одно слово в считалочке и хотя бы одно имя в списке детей, общее количество слов и имен не превосходит 1000.
Выходные данные
В выходной файл OUTPUT.TXT выведите имя того, кто будет водить.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
eniki beniki eli varyeniki
Ilya Misha Nikita Sasha
Sasha
2
mi delili apelsin mnogo nas a on odin
Dasha Nastya Marina
Nastya
Система оценки
Решения, не анализирующие лишние пробелы, будут оцениваться в 40 баллов.
Решения для случаев, когда все слова в считалочке состоят из строчных букв, а имена детей таковы, что первая буква прописная, а остальные – строчные, будут оцениваться в 60 баллов.
Задача D. Танцуют все!
(Время: 1 сек. Память: 16 Мб Баллы: 100)
На вечеринку приглашены N мальчиков и M девочек. Каждый мальчик хочет станцевать с каждой девочкой, а каждая девочка – с каждым мальчиком. Можно организовать несколько раундов. В каждом раунде может танцевать несколько пар так, что каждая пара состоит из одного мальчика и одной девочки.
Требуется организовать минимально возможное число раундов, в результате которых каждый мальчик станцует с каждой девочкой и наоборот, каждая девочка – с каждым мальчиком. При этом никакая пара не должна танцевать дважды и, разумеется, никто не может танцевать дважды в одном раунде.
Входные данные
Входной файл INPUT.TXT содержит два натуральных числа N и M – количество мальчиков и девочек (N ≤ 100, M ≤ 100).
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите целое число K – минимальное количество раундов. В последующих K строках следует вывести информацию о танцах: в отдельной строке выводится информация о каждом раунде. Раунд описывается целым числом T – количество танцующих пар, после чего идет описание T пар, разделенных пробелом. Информация о паре имеет вид «A-B», где A – номер мальчика, а B – номер девочки. Все мальчики пронумерованы от 1 до N, а девочки – от 1 до M.
Если существует несколько оптимальных решений, то следует вывести любое из них.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
2 2
2
2 1-1 2-2
2 1-2 2-1
2
3 2
3
2 1-1 3-2
2 2-2 3-1
2 1-2 2-1
Система оценки
Решения, работающие только при N+M ≤ 6, будут оцениваться в 25 баллов.
Решения, работающие только при N=M, будут оцениваться в 30 баллов.
Решения, работающие только для взаимно простых N и M, будут оцениваться в 50 баллов.
Задача E. Шахматная расстановка
(Время: 2 сек. Память: 16 Мб Баллы: 100)
На шахматной доске размером N×N необходимо вычислить количество вариантов расстановки Q ферзей и R ладей таким образом, чтобы фигуры не били друг друга. Напомним, что ладья может перемещаться как по горизонтали, так и по вертикали; ферзь же может ходить как ладья, а так же как слон (по диагонали).
Входные данные
Входной файл INPUT.TXT содержит три целых числа: N, Q и R (1 ≤ N ≤ 10, 0 ≤ Q, R ≤ 10).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
3 1 2
4
2
8 8 0
92
3
4 0 2
72
4
10 2 3
26079424
Система оценки
Решения, оценивающие только случаи при N ≤ 3, будут оцениваться в 20 баллов.
Решения, работающие только при Q = 0, будут оцениваться в 30 баллов.
Решения, работающие только при R = 0, будут оцениваться в 30 баллов.
Решения, работающие только при N ≤ 9, будут оцениваться в 80 баллов.
