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

Задача A. Разбиение на пары

Четыре целых числа A, B, C и D необходимо разбить на пары таким образом, чтобы сумма произведений в этих парах была максимальна.

В качестве примера рассмотрим числа 2, 3, 4 и 5. Здесь максимальное значение получается в парах (2,3) и (4,5), так как в данном случае искомая сумма будет равна 2×3 + 4×5 = 26.

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

Входной файл INPUT.TXT содержит четыре целых числа A, B, C и D, не превышающих 1000 по абсолютной величине. Каждое число записано в отдельной строке.

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

В выходной файл OUTPUT.TXT выведите искомое значение максимальной суммы.

Пример

Задача B. Цифра

Каждой цифре от 0 до 9 сопоставим изображение размером 5×3, составленное из пробелов и символов «#»:

        ###   # ### ### # # ### ### ### ### ###
        # #  ##   #   # # # #   #     # # # # #
        # # # # ### ### ### ### ###   # ### ###
        # #   # #     #   #   # # #   # # #   #
        ###   # ### ###   # ### ###   # ### ###

Требуется написать программу, которая считывает цифру и выводит изображение, соответствующее этой цифре.

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

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

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

В выходной файл OUTPUT.TXT выведите изображение, соответствующее цифре N. В каждой строке допускается вывод произвольного числа пробелов после последнего символа «#».

Примеры

Задача C. Преобразование

Требуется из числа 0 получить целое число N, используя минимальное количество действий. В качестве действия над числом разрешается использовать одно из следующих преобразований:

1. умножить число на некоторое целое K;
2. прибавить к числу единицу.

Например, при N=30 и K=3 достаточно сначала прибавить 1, затем дважды умножить на 3, потом прибавить 1 и еще раз умножить на 3. Всего получилось 5 действий, которые можно записать следующим образом: ((0+1)×3×3+1)×3 = 30.

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

Первая строка входного файла INPUT.TXT содержит целое число N (0 ≤ N ≤ 10⁹), во второй строке записано целое число K (2 ≤ K ≤ 10⁹).

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

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

Примеры

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

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

Решения, работающие только для K ≤ 10⁶, будут оцениваться в 50 баллов.

Задача D. Лазерная пушка

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

Вам необходимо расставить минимальное количество зеркал так, чтобы лазерный луч поразил цель в координате (X, Y).

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

Входной файл INPUT.TXT содержит два целых числа X и Y, не превосходящих по модулю 10 000, записанные в разных строках – координаты цели. Точка (X, Y) не совпадает с началом координат.

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

В первой строке выходного файла OUTPUT.TXT выведите число N – необходимое количество зеркал. Следующие N строк должны содержать информацию о каждом зеркале. В i-й строке должны быть записаны через пробелы два целых числа x_i и y_i и один символ t_i, обозначающие координаты (x_i, y_i) точки, в которых установлено i-е зеркало, и тип этого зеркала t_i. Если t_i является символом «V», то i-е зеркало размещено вертикально, если же t_i является символом «H», то зеркало размещено горизонтально. Например, строка «-2 5 H» обозначает горизонтальное зеркало в точке (-2, 5). Зеркала можно выводить в любом порядке. Зеркало нельзя размещать в точке (0, 0), также нельзя размещать два зеркала в одной точке. Значения x_i и y_i не должны по модулю превосходить 100 000. Также, разумеется, нельзя допустить, чтобы отражённый луч попал в пушку.

Если вариантов ответа несколько, выведите любой из них. Если поразить цель в соответствии с условиями задачи невозможно, программа должна вывести одно число «-1». Если для поражения цели зеркала не нужны, программа должна вывести одно число «0».

Пример

№	INPUT.TXT	OUTPUT.TXT	Пояснение
1	5 1	1 3 3 H

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

Решения, правильно работающие только для X ≥ 0 и Y ≥ 0, будут оцениваться в 40 баллов.

Задача E. Каталоги

Задан список путей к каталогам в виде имен, разделенных символом «/» (слэш). Например: «a/b/c», «b/d» и «test».

Требуется вывести данный список в виде дерева. Каталоги должны быть упорядочены лексикографически (в алфавитном порядке). При выводе элементов списка следует выводить только имена каталогов, а глубину вложенности нужно обозначать символами «+» (см. примеры).

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

Первая строка входного файла INPUT.TXT содержит целое число N (1 ≤ N ≤ 100) – количество заданных путей к каталогам. Далее в N строках содержатся сами пути по одному в строке. Все пути различны, состоят из строчных букв английского алфавита и слэшей, имеют длины от 1 до 100. Никакой путь не начинается со слэша, не заканчивается слэшем, не содержит два или более слэша подряд. Гарантируется, что в списке нет одинаковых каталогов.

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

В выходной файл OUTPUT.TXT выведите искомое дерево, однозначно определяющее структуру данных каталогов.

Примеры