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

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

HotLog


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

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

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

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

Четыре целых числа 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 выведите искомое значение максимальной суммы.

Пример

INPUT.TXTOUTPUT.TXT
12
3
4
5
26

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

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

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

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

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

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
15 ###
#
###
  #
###
23 ###
  #
###
  #
###

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

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

Требуется из числа 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 ≤ 109), во второй строке записано целое число K (2 ≤ K ≤ 109).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
130
3
5
24
2
3

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

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

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


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

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

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

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

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

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

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

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

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

Пример

INPUT.TXTOUTPUT.TXTПояснение
15
1
1
3 3 H

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

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


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

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

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

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

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
14
opt
usr
bin
opt/tomcat
bin
opt
+tomcat
usr
23
usr/kate
usr/helen
usr/guest
usr
+guest
+helen
+kate
35
a/b/c
a/b/c/d
a/b/c/d/e
a
a/d
a
+b
++c
+++d
++++e
+d


Красноярский краевой Дворец пионеров, (c)2006 - 2022, E-mail: admin@acmp.ru



Подготовительные работы и горизонтальный транспорт производство земляных работ.