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

Задача A. Три армии

Великие полководцы Конрад, Гарольд и Вильгельм решили помериться силами, а именно своими армиями. Известно, что армия Конрада состоит из N батальонов по A воинов в каждом. Армия Гарольда содержит M батальонов по B воинов. В армии Вильгельма находится K батальонов по C воинов.

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

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

В первой строке входного файла INPUT.TXT записаны 6 целых чисел N, M, K, A, B и C (1 ≤ N, M, K, A, B, C ≤ 1000) – число батальонов у Конрада, Гарольда, Вильгельма, и число воинов в них соответственно.

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

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

Примеры

Задача B. Шеренга

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

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

Первая строка входного файла INPUT.TXT содержит целое число N – количество учеников в классе (2 ≤ N ≤ 50). Следующие N строк содержат по два целых числа каждая: A_i и H_i – пол и рост в сантиметрах i-го ученика (0 ≤ A_i ≤ 1, 100 ≤ H_i ≤ 200). Значение A_i = 0 означает, что i-й ученик – мальчик, а значение A_i = 1 означает, что i-й ученик – девочка.

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

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

Пример

Задача C. Минипалиндромы

Минипалиндром – это слово из трёх букв, которое читается одинаково как слева направо, так и справа налево.

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

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

Входной файл INPUT.TXT содержит строку, длина которой не превышает 3×10⁵. Гарантируется, что строка содержит только строчные буквы английского алфавита и пробелы. Также гарантируется, что строка не пуста и не может начинаться с пробела или заканчиваться им.

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

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

Примеры

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

Решения, работающие в случаях, в которых длина строки не превосходит 200, будут оцениваться в 30 баллов.

Решения, работающие в случаях, в которых длина строки не превосходит 5000, будут оцениваться в 60 баллов.

Задача D. Полное произведение

Рассмотрим N наборов чисел:

Полным произведением этих наборов назовем число P:

Ваша задача – для заданных наборов чисел X₁, X₂, ... , X_N вычислить остаток от деления их полного произведения на K.

Напомним, как правильно находить остаток от деления целых чисел. Для любых целых чисел a и b (b ≠ 0) найдется единственная пара целых чисел q и r таких, что a = q×b + r, где 0 ≤ r < |b|. Здесь a – делимое, b – делитель, q – неполное частное, r – остаток.

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

В первой строке входного файла INPUT.TXT находятся целые числа N, M (1 ≤ N, M ≤ 1000) и K (2 ≤ K ≤ 10⁹). В каждой из следующих N строк записано по M чисел: в i-ой из них на j-ом месте записано целое число x_i^j. Гарантируется, что |x_i^j| ≤ 10⁹.

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

В выходной файл OUTPUT.TXT выведите P mod K – ответ на задачу.

Пример

Задача E. Максимальное разрезание

Юный математик Егор очень любит вкусно поесть и поэтому часто заглядывает в холодильник. Однажды он достал оттуда палку колбасы и с помощью трёх разрезов ножом получил из нее 4 куска, которые впоследствии благополучно съел.

Конечно, на этом он решил не останавливаться и в следующий раз при открытии холодильника взгляд Егора упал на аппетитную пиццу, которую он разогрел в микроволновой печи, после чего смог разрезать на 7 частей и съесть.

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

В отличие от предыдущих продуктов сыр представлял собой серьёзное испытание для Егора и потребовал массу времени для его употребления. В процессе поедания сыра Егор задумался над тем, почему же при равном числе разрезов каждый раз получалось разное количество частей, несмотря на то, что каждый раз Егор старался получить максимальное количество кусков от каждого продукта. В результате он понял, что все дело в размерности: колбасу он рассматривал как одномерный отрезок, пиццу – как двумерный круг, а сыр – как трехмерный куб.

Теперь Егор хочет решить более общую задачу: на какое максимальное количество частей можно разрезать K-мерный куб, используя N прямых разрезов размерности K-1?

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

Входной файл INPUT.TXT содержит целые числа K и N – размерность куба и количество разрезов размерности K-1 (1 ≤ K, N ≤ 63).

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

В выходной файл OUTPUT.TXT выведите одно целое число – ответ на задачу Егора.

Примеры

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

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

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

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

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

Задача F. Фермер 3D

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

Представим участок фермера в виде прямоугольного параллелепипеда и разобьем его на участки размером 1×1×1, являющимися частью трехмерной сетки размером H×N×M. При этом каждый такой участок может быть либо пригоден, либо нет для использования.

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

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

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

Далее идет описание H слоев земельного участка. Каждый слой представлен N строками по M цифр 0 или 1 (без пробелов), после чего идет пустая строка. При этом 1 соответствует пригодности участка, а 0 – говорит о том, что участок не пригоден для использования.

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

В выходной файл OUTPUT.TXT выведите максимально возможный объем погреба.

Пример

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

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

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

Решения, работающие для случаев, где погреб с максимальным объемом имеет форму куба, будут оцениваться в 30 баллов.