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

Задача A. Остаток от деления

Напомним, как в математике определяется остаток от деления целых чисел.

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

Здесь a – делимое, b – делитель, q – неполное частное, r – остаток. Следует заметить, что остаток r – это всегда неотрицательное число.

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

Ваша задача – по заданным числам a и b определить значение остатка от деления a на b.

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

Входной файл INPUT.TXT содержит два целых числа a и b (-10¹⁸ ≤ a, b ≤ 10¹⁸, b ≠ 0).

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

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

Примеры

Задача B. Газонокосильщик

Газонокосильщику Ивану в очередной раз предстоит подстричь свой газон, который можно представить в виде таблицы высотой N и шириной M. Ширина газонокосилки совпадает с шириной клеток таблицы, поэтому за один проход по прямой можно постричь сразу целую строку или целый столбец. Но постричь газон без поворотов газонокосилки зачастую не представляется возможным.

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

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

Помогите ему в этом!

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

Входной файл INPUT.TXT содержит в единственной строке два целых числа N и M – размеры газона (1 ≤ М, N ≤ 2∙10⁹).

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

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

Примеры

Система оценивания

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

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

Задача C. Предложение

В предложении необходимо найти самое короткое и самое длинное слово.

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

В первой строке входного файла INPUT.TXT содержится предложение, состоящее из слов, разделенных пробелами. Каждое слово – это последовательность букв английского алфавита. Слова могут отделяться друг от друга одним или несколькими пробелами. Также один или несколько пробелов могут быть как в начале, так и в конце предложения. Гарантируется, что в предложении присутствует хотя бы одно слово. Длина предложения может быть от 1 до 10⁶ символов.

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

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

Примеры

Пояснение

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

Система оценивания

Решения, работающие только для предложений, состоящих из слов одинаковой длины и не содержащих «лишних» пробелов, будут оцениваться в 60 баллов.

Задача D. Бесконечный поезд

Это интерактивная задача.

Представьте себе замкнутую по окружности железную дорогу и поезд, последний вагон которого скреплен с первым так, что внутри можно перемещаться между вагонами. Вы оказались в случайном вагоне и желаете определить количество вагонов N (1 ≤ N ≤ 10 000). В каждом вагоне можно менять положение переключателя света, но начальное состояние переключателей случайное и заранее неизвестно.

Протокол взаимодействия

Вы можете делать следующие запросы программе жюри:

switch – изменение состояние переключателя света в текущем вагоне;

front – перемещение в следующий вагон;

back – перемещение в предыдущий вагон;

N – вывод ответа, где N – целое число (количество вагонов в поезде).

После каждого запроса (кроме последнего) вашей программе будет сообщено состояние переключателя света в том вагоне, в котором вы оказались: «on» - если свет горит и «off» – иначе. Последним запросом должен быть вывод целого числа N, после чего ваша программа должна немедленно завершиться. На момент подачи любой команды модуль разности между количеством поданных команд front и количеством поданных команд back не должен превышать 3×N.

Пример

Пояснение к примеру

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

Примечание

Для корректной работы программы после каждой операции вывода данных выводите перевод строки, а также очищайте буфер вывода. Очистка буфера вывода производится следующим образом:

• В языке Pascal: flush(output)
• В С/С++: fflush(stdout) или cout.flush()
• В Java: System.out.flush()
• В Python: sys.stdout.flush() из библиотеки sys
• В C# и Basic: Console.Out.Flush()

Система оценивания

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

Задача E. Ремонт забора

Илья работает плотником и перед ним стоит задача отремонтировать забор. Забор состоит из N сегментов, i-й из которых имеет высоту A_i. Илья располагает тележкой, на которой лежит стопка из M досок, j-я из которых имеет длину B_j.

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

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

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

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

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

В третьей строке находится целое число M – количество досок на тележке (1 ≤ M ≤ 10⁵). В четвертой строке содержатся M целых чисел B₁, B₂, … B_M – длины досок на тележке, начиная с верхней (1 ≤ B_j ≤ 10⁸).

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

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

Примеры

Система оценивания

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