ЗАДАНИЯ ОЛИМПИАДЫ

Решения задач загружаются в Виртуальном кабинете.

Задачи теоретической части

В предложенных задачах требуется дать словесное описание алгоритма решения предложенной задачи (если не оговаривается что-то другое). При проверке решений (алгоритмов) будут учитываться следующие параметры:

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

Решения задач теоретической части оформляются в виде документа Microsoft Word в соответствии с техническими требованиями и загружаются для проверки в Виртуальном кабинете.

1. Слова

Даны два слова, состоящих из букв A и B произвольной длины. Разрешается выделить в любом из них несколько идущих подряд букв, среди которых есть ровно k букв A, и одну из них перенести в начало слова. Также разрешается выделить в нём несколько идущих подряд букв, среди которых есть ровно k букв B, и одну из них перенести в конец слова. Опишите алгоритм, определяющий, можно ли несколькими такими действиями получить из заданных слов два одинаковых слова (состоящих из A и B).

2. Греко-латинский квадрат

Имеется 16 карт. По четыре туза, короля, дамы и валета, всех четырёх мастей. Говорят, что карты образуют греко-латинский квадрат, если они лежат в таблице 4×4 так, что в каждом горизонтальном и вертикальном ряду есть карты каждой масти и каждого достоинства. Две карты наугад положили в какие-то клетки таблицы 4×4. Опишите алгоритм, по которому можно достроить таблицу до греко-латинского квадрата (если это возможно) или сделать вывод о том, что этого сделать нельзя.

3. Автомат

Имеется автомат, в который можно вставить две карточки с написанными на них числами a и b. Автомат возвращает исходные карточки, а также ещё две – на одной из которых написано число 1–(a/b), а на другой 1–(b/a). Если для получения какой-то из карточек требуется делить на ноль, то эта карточка не возвращается. Как с помощью такого автомата получить сумму двух исходных чисел?

4. Треугольники

Заданы декартовы координаты трех точек на плоскости. Все координаты – целые. Придумайте наиболее оптимальные алгоритмы (требующие наименьшего количества вычислений), которые позволяют ответить на следующие вопросы:

А) Лежат ли эти точки в вершинах прямоугольного треугольника?

Б) Лежат ли эти точки в вершинах равнобедренного треугольника?

В) Лежат ли эти точки в вершинах правильного треугольника?

5. Волейбольный турнир

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

Задачи практической части

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

Для проверки принимаются только исходные тексты программ (файлы *.pas, *.c, *.cpp) в соответствии с техническими требованиями. Программы (исходные тексты) загружаются для проверки в Виртуальном кабинете, сразу компилируются и проверяются на наборе тестов, после чего участнику выдается результат. Допускается вносить изменения в программы произвольное количество раз и загружать программы для повторной проверки.

Внимание: загрузка работ будет возможна с 25 ноября. Загружается только исходный текст программы (файл *.pas, *.c, *.cpp) без архивирования.

С учетом того, что проверка работ практической части ведется а автоматическом режиме, следует внимательно следить за форматами выходных файлов: несоответствие формата выходного файла может привести к тому, что результат прохождения теста не будет засчитан.

Входные данные берутся из текстового файла input.txt, результат выполнения программы выводится в файл output.txt в установленном формате. Программа ничего не должна запрашивать для ввода с клавиатуры и не должна ничего выводить на экран.

Ограничения на время выполнения программы по каждому из тестов: 10 секунд. Программы, не укладывающиеся во время прохождения теста в установленные ограничения или выдающие ошибку, считаются не прошедшими данный тест.

1. Простые числа

Даны натуральные n и k. Укажите n идущих подряд натуральных чисел, среди которых ровно k простых.

Вход: файл input.txt, в котором записаны два натуральных числа, разделенных пробелом: первое число – n, второе число – k.

Ограничения: 1 ≤ n ≤ 100, 1 ≤ k ≤ 25.

Выход: файл output.txt, содержащий одно натуральное число – первое число в любой удовлетворяющей условию последовательности из n натуральных чисел. Ответ не превосходит 1000000000.

Пример:

2. Картонные круги

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

Вход: файл input.txt, в котором записаны три вещественных числа, разделенных пробелом,  – длины сторон треугольника.

Ограничения: длины сторон не превосходят 100, входные данные корректны (т.е. предполагается, что из отрезков с данными длинами действительно можно составить треугольника).

Выход: файл output.txt, содержащий одно вещественное число – сумму площадей кругов, ответ выводится с точностью до 0.0001.

Пример:

3. Расписание

В  однокруговом  турнире участвуют 2n команд. В каждом туре все команды разбиваются на n пар (в одну пару не попадают команды, ранее игравшие друг с другом) и проводят между собой, соответственно, n игр (по одной игре в паре). Прошло n-1 туров. Составьте расписание ещё двух туров.

Вход: файл input.txt, в котором записаны натуральные числа;

первая строка:  число n,

вторая строка: через пробел перечислены номера соперников команды №1 в 1, 2, …, (n-1) туре (соответственно, всего n-1 число);

третья строка: аналогично перечислены соперники команды №2 в 1, 2, …, (n-1) туре;

…

(2n+1)-я строка: перечислены соперники команды №(2n) в 1, 2, …, (n-1) туре.

Ограничения: 2 ≤ n ≤ 50.

Выход: файл output.txt, содержащий 2n строк с числами – в k-й строке (1 ≤ k ≤ 2n) через пробел указаны номера двух команд, с которыми k-я команда сыграет в турах с номерами n и (n+1) соответственно.

Пример:

Пример соответствует такой ситуации

1 тур: играют команды 1-2, 3-4 и 5-6,

2 тур: играют команды 1-6, 2-3 и 4-5,

вариант расписания для третьего и четвертого тура:

3 тур: играют команды 1-3, 2-5 и 4-6,

4 тур: играют команды 1-4, 2-6 и 3-5.