Задачи олимпиады "Муниципальный этап ВОШ Красноярского края по информатике, 7-8 классы"
Задача A. Ключ
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Петя – начинающий компьютерный взломщик. После перехвата очередного сигнала между своими соседями, ему удалось извлечь из него два числа N и P. Петя долго не мог понять смысл этих чисел, однако, в разговоре соседей на лестничной площадке он нечаянно услышал алгоритм получения ключа, которого достаточно для полной расшифровки сигнала.
Из всех наборов натуральных чисел рассматриваются те, которые состоят из N элементов, а их произведение равно P. Ключ равен наибольшей из возможных сумм элементов такого набора.
Например, существует два набора из трех натуральных чисел, произведение которых равно четырем: 1, 2, 2 и 1, 1, 4. Сумма элементов первого набора равна пяти, а второго – шести, следовательно, ключ равен шести.
Помогите Пете найти ключ для расшифровки сигнала.
Входные данные
Входной файл INPUT.TXT содержит два целых числа N и P (1 ≤ N, P ≤ 1018).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – искомый ключ.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
2 2
3
2
3 4
6
Система оценки
Решения, работающие только для N, P ≤ 1000, будут оцениваться в 80 баллов.
Задача B. Прыжки в воду
(Время: 1 сек. Память: 16 Мб Баллы: 100)
В рамках олимпийских игр во Флатландии проводятся соревнования по прыжкам в воду. Для повышения объективности судейства на этих соревнованиях применяется следующая система оценки.
Каждому из спортсменов оценки выставляют N судей. Обозначим эти оценки как A1, A2, ..., AN. Для получения итоговой оценки из этих оценок вычеркивается наибольшая и наименьшая, после чего вычисляется среднее арифметическое оставшихся оценок.
Ваша задача состоит в том, чтобы реализовать описанный алгоритм вычисления итоговой оценки.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число N (3 ≤ N ≤ 100). Во второй строке записано N целых чисел: A1, A2, ..., AN (1 ≤ Ai ≤ 10).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу с точностью не хуже 10-6.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
3 3 3 3
3
2
4 1 2 3 4
2.5
Задача C. Грибные места
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Василий Петрович – грибник со стажем. У него есть грибная карта прямоугольной формы размером N×M, разбитая на квадратные сектора 1×1. В каждом секторе записано число, соответствующее количеству грибов, которые Василий Петрович собрал в прошлом году в данном секторе.
В этом году Василий Петрович не хочет тратить время попусту, он хочет посетить только грибные места, под которыми он понимает те сектора его карты, в которых он в прошлом году собрал грибов строго больше, чем в каждом из секторов, граничащих с данным сектором по стороне.
Требуется вычислить общее количество грибных мест, которые собирается посетить Василий Петрович.
Входные данные
В первой строке входного файла INPUT.TXT заданы числа N и M (1 ≤ N, M ≤ 100) – размеры грибной карты. Далее идут N строк по M чисел Aij (1 ≤ Aij ≤ 100) в каждой – количество грибов в секторе, который находится в i-й строке и j-м столбце.
Выходные данные
В выходной файл OUTPUT.TXT выведите количество грибных мест на карте.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
1 4 3 7 4 2
1
2
4 4
1 2 1 2
2 1 2 1
1 2 1 2
2 1 2 1
8
Система оценки
Решения, работающие для N=1, будут оцениваться в 60 баллов.
Задача D. Прямоугольники
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Дима решил написать отечественную операционную систему «Окна 2020». Для начала он планирует написать подпрограмму, которая будет рисовать рамки окон. Поле для рисования представляет собой прямоугольник размером H×W пикселей, строки занумерованы сверху вниз от 1 до H, столбцы – слева направо от 1 до W. На поле последовательно рисуются N рамок, i-я рамка представляет собой границы прямоугольника с противоположными углами в точках (ri,1, ci,1) и
(ri,2, ci,2).
Требуется вывести получившееся изображение в виде H рядов по W символов. Пиксель, который не был использован при изображении рамок, следует вывести с использованием символа «.» (точка), а пиксели i-й рамки с использованием i-го символа английского алфавита (первая рамка изображается буквами «a», вторая – «b», третья – «c» и т.д.).
Входные данные
Первая строка входного файла INPUT.TXT содержит целые числа H, W и N – высота и ширина поля, а также число рамок (2 ≤ H, W ≤ 80, 1 ≤ N ≤ 26). Следующие N строк содержат по четыре целых числа каждая: ri,1, ci,1, ri,2 и ci,2 (1 ≤ ri,1 < ri,2 ≤ H,. 1 ≤ ci,1 < ci,2 ≤ W).
Выходные данные
В выходной файл OUTPUT.TXT выведите результат с изображением рамок, описанных во входных данных.
Решения, работающие только для N=1, будут оцениваться в 40 баллов.
Задача E. Карандаши
(Время: 2 сек. Память: 32 Мб Баллы: 100)
Есть коробка с N цветными карандашами. Требуется выбрать из данного набора K карандашей таким образом, чтобы количество карандашей разных цветов было максимально возможным.
Входные данные
Первая строка входного файла INPUT.TXT содержит целые числа N и K
(1 ≤ K ≤ N ≤ 105) – количество карандашей в коробке и количество карандашей, которые следует выбрать соответственно. Во второй строке записаны N целых чисел Ai (1 ≤ Ai ≤ 109) – цвета карандашей в коробке.
Выходные данные
В выходной файл OUTPUT.TXT выведите ровно K целых чисел через пробел – цвета карандашей, которые следует выбрать. Если существует несколько вариантов ответа, то выведите любой из них.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
5 3 1 1 1 2 2
1 1 2
2
10 4 8 8 8 8 8 8 8 8 2 1
1 2 8 8
Система оценки
Решения, работающие для тестов, где N ≤ 2000, будут оцениваться в 60 баллов.
