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

Задача A. Спираль

Петя очень любит рисовать, используя свои цветные карандаши. Однажды он взял листок бумаги в клеточку размером N×M и решил на нём нарисовать по линиям сетки спираль, которая закручивается вправо.

Формально, он придерживается следующего алгоритма:

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

Вам требуется вычислить суммарную длину получившейся линии в данной спирали по завершении этого увлекательного процесса.

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

Две строки входного файла INPUT.TXT содержат два натуральных числа N и M – количество клеток в листке бумаги по вертикали и горизонтали соответственно (2 ≤ N, M ≤ 10⁹).

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

В выходной файл OUTPUT.TXT выведите целое число – суммарную длину спирали.

Примеры

№	INPUT.TXT	OUTPUT.TXT	Пояснение
1	3 4	6
2	5 7	24

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

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

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

Задача B. Треугольник в прямоугольнике

Дан прямоугольник ABCD со сторонами a и b (a = AD = BC, b = AB = DC). Строну AB разбили на три равные части точками E и F. Строну DC разбили на две равные части точкой K.

Затем провели диагональ AC и отрезки EK и FK, которые образовали пересечение с диагональю AC в точках L и M.

По длинам сторон прямоугольника ABCD требуется определить значение площади треугольника LMK.

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

В первых двух строках входного файла INPUT.TXT записаны два целых числа a и b – длины сторон прямоугольника ABCD (1 ≤ a, b ≤ 1000).

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

В выходной файл OUTPUT.TXT выведите искомую площадь треугольника LMK с точностью не хуже, чем 10^-3.

Пример

Задача C. Весёлые качели

Однажды во дворе многоэтажки родители для своих n детей построили большие и прочные качели типа «качалка-балансир» в виде длинной балки, подвешенной в центре тяжести на шарнире так, что она может качаться в вертикальной плоскости.

Оказалось, что качаться на этих качелях интересно, когда качели уравновешены, то есть если модуль суммы моментов детей слева от центра качелей совпадает с модулем суммы моментов детей справа от центра. Напомним, что момент ребёнка равен произведению его массы на расстояние от него до центра качелей.

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

Более формально: для каждого ребёнка номер i с массой m_i необходимо определить целое число d_i (d_i ≠ 0) – его позицию на качелях так, чтобы все d_i были различны и выполнялось равенство:

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

Первая строка входного файла INPUT.TXT содержит целое число n (1 ≤ n ≤ 1000) – количество детей.

Во второй строке заданы n целых чисел m₁, m₂, …, m_n (1 ≤ m_i ≤ 100), где m_i обозначает массу i-го ребёнка в килограммах.

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

В выходной файл OUTPUT.TXT выведите «No», если решения не существует. В противном случае в первой строке выведите «Yes», а во второй строке – последовательность различных целых чисел d_i (1 ≤ |d_i| ≤ 10⁹). Если существует несколько решений, выведите любое.

Гарантируется, что если решение существует, то найдётся и решение для |d_i| ≤ 10⁹ при всех i.

Примеры

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

Решения, работающие только для случаев, когда присутствует хотя бы один ребёнок с массой в 1 килограмм, будут оцениваться в 50 баллов.

Задача D. Башенки из кубиков

Маленький Рома любит играть в кубики и строить из них башенки. Всего у него N кубиков, каждый из которых определяется целочисленным размером A_i, который определяет длину ребра i-го кубика. Если поставить несколько кубиков последовательно друг на друга, то получается башенка.

Рома считает башенку красивой, если каждый последующий сверху вниз кубик имеет размер на единицу больше, чем предыдущий. Высота башенки – это количество кубиков в ней. То есть для красивой башенки высоты M, состоящей из кубиков с размерами S₁, S₂, …, S_M, должно выполняться условие: S_i-1 = S_i – 1 для i от 2 до M.

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

Помогите Роме с этой задачей!

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

Первая строка входного файла INPUT.TXT содержит число N – количество кубиков у Ромы (1 ≤ N ≤ 2×10⁵). Во второй строке содержатся N целых чисел A₁, A₂, …, A_N , где A_i – размер i-го кубика (1 ≤ A_i ≤ 2×10⁵).

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

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

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

Если существует несколько решений задачи, выведите любое из них.

Примеры

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

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

Решения, работающие только в тех случаях, когда размеры всех кубиков различны, будут оцениваться в 40 баллов.

Задача E. Площадь многоугольника

По длинам сторон многоугольника требуется определить его максимально возможную площадь.

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

Первая строка входного файла INPUT.TXT содержит целое число N – количество сторон многоугольника (3 ≤ N ≤ 100). Вторая строка входных данных содержит N целых чисел L_i – длины сторон многоугольника (1 ≤ L_i ≤ 100).

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

В выходной файл OUTPUT.TXT выведите значение максимально возможной площади многоугольника с точностью не хуже, чем 10^-2. Если составить многоугольник невозможно, выведите «0».

Примеры

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

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

Решения, работающие только для равносторонних многоугольников, будут оцениваться в 20 баллов.

Задача F. Поход за грибами

Однажды грибник Макар попал в трёхмерный лес, в котором растут деревья и грибы. Лес состоит из H уровней, расположенных друг над другом. Каждый уровень – это прямоугольная площадка, разбитая на N×M участков. Макар может свободно перемещаться по свободным участкам в шести направлениях: вверх, вниз, влево, вправо, вперед и назад. Оказавшись на одном участке с грибом, Макар может его сорвать. Однако сквозь деревья и за пределы леса Макар ходить не может. При любом перемещении из одного участка в смежный Макар делает один шаг.

У Макара есть карта леса, включающая расположение деревьев и грибов в нём, а также текущее положение Макара. Некоторые грибы (возможно, все) могут быть недостижимы.

Требуется определить: какое максимальное число грибов сможет собрать Макар и какое минимальное количество шагов ему на это потребуется.

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

Первая строка входного файла INPUT.TXT содержит целые числа H, N, M – размеры леса (2 ≤ H, N, M ≤ 50). Далее идет описание H уровней снизу вверх. Каждый уровень описывается N строками по M символов в каждой: «.» обозначает свободный участок, «#» – дерево, заглавная буква английского алфавита «M» – гриб и заглавная буква английского алфавита «P» – положение Макара. Описание каждого уровня завершается пустой строкой. Гарантируется, что количество грибов на карте не превосходит 20.

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

В выходной файл OUTPUT.TXT выведите два целых числа: максимальное число грибов, которые может собрать Макар, и минимальное количество шагов, которые Макар должен сделать, чтобы собрать эти грибы.

Пример

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

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

Решения, работающие только для решений с не более чем 10 грибами, будут оцениваться в 80 баллов.