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

Задача A. Принцип Дирихле

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

Нас же будет интересовать более общий случай, когда у нас N клеток и M кроликов. Вам требуется вычислить максимальное количество кроликов, которое гарантированно окажется в одной из клеток.

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

Входной файл INPUT.TXT содержит целые числа N и M (1 ≤ N, M ≤ 10¹⁹).

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

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

Пример

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

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

Задача B. Красивая дата

Вася считает, что дата, записанная в формате ДДММГГГГ, красивая, если в ней день, месяц и год – нечётные числа, то есть числа, которые не делятся на 2.

Например, дата «первое сентября 2019 года» (01092019) является красивой, так как числа 1, 9 и 2019 – нечётные. А вот дата «13 июня 1997 года» (13061997) не является красивой, так как в ней номер месяца 6 – чётное число.

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

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

В первой строке входного файла INPUT.TXT содержится корректная дата в виде последовательности десятичных цифр формата ДДММГГГГ. Такое представление даты можно рассматривать как восьмизначное целое число с одним возможным лидирующим нулём. Дата может быть любой в промежутке от 1 января 1 года (01010001) до 31 декабря 9999 года (31129999).

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

В выходной файл OUTPUT.TXT выведите «Yes» (без кавычек), если дата является красивой, и «No» (без кавычек) – в противном случае.

Примеры

Задача C. Максимальный прямоугольник

На клетчатом поле размером M×N разместили две фишки.

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

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

Первая строка входного файла INPUT.TXT содержит два целых числа M и N – количество столбцов и количество строк клетчатого поля (2 ≤ M, N ≤ 1000).

В следующих двух строках заданы координаты фишек: в (i+1)-й строке файла записана целочисленная координата i-й фишки (x_i,y_i). Гарантируется, что фишки находятся в разных клетках поля (1 ≤ x_i ≤ M, 1 ≤ y_i ≤ N, i=1..2).

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

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

Примеры

№	INPUT.TXT	OUTPUT.TXT	Пояснение
1	4 3 2 1 4 3	9
2	2 2 1 1 2 2	2

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

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

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

Задача D. Лексикографически минимальное число

Найдите число, десятичная запись которого является лексикографически минимальной среди десятичных записей всех целых чисел от A до B.

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

Входной файл INPUT.TXT содержит два целых числа: A и B (1 ≤ A ≤ B ≤ 10¹⁸).

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

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

Примеры

Пояснение

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

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

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

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

Задача E. Полка с книгами

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

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

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

Вернувшись домой, Вася заметил, что порядок книг нарушен. Допросив маму, он узнал то, каким образом случилось такое перемешивание, и его заинтересовал вопрос: сколько книг мог брать папа, и сколько книг могла брать мама?

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

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

Первая строка входного файла INPUT.TXT содержит единственное число N – количество книг на полке у Васи. Во второй строке записаны N целых чисел A_i – информация о количестве страниц в каждой книге слева направо на тот момент, когда Вася вернулся домой. Гарантируется, что все значения A_i различны.

Ограничения: 2 ≤ N ≤ 3×10⁵, 1 ≤ A_i ≤ 10⁹.

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

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

Примеры

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

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

Задача F. Миссия невыполнима

Вы играете в новую компьютерную игру «Миссия невыполнима 0xFF» и почти завершили ее прохождение. На последнем уровне вам осталось взломать сейф с электронным кодовым замком, представляющим собой сенсорную прямоугольную панель из N строк и M столбцов, пронумерованных по порядку числами от 1 до N и от 1 до M соответственно. Первоначально каждая из N×M ячеек замка имеет определенный цвет. Известно, что различных цветов на панели не может быть более, чем min(N, M)-1, цвета нумеруются целыми числами от 1 до min(N, M)-1. Вам доступна функция перекрашивания ячеек панели: если выбрать две клетки одного цвета, принадлежащие одной строке или одному столбцу, то вся эта строка (весь этот столбец) перекрасится в цвет выбранных клеток. При этом разрешается перекрашивать строку (столбец), если эта строка (столбец) ранее уже была окрашена в цвет перекраски. Для открытия сейфа необходимо не более чем за 2×(N+M) операций перекрасить всю панель в какой-нибудь один цвет.

Напишите программу, которая по заданной раскраске панели будет выводить последовательность команд, приводящую к открытию замка сейфа. Команд не должно быть более 2×(N+M).

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

В первой строке входного файла INPUT.TXT записаны целые числа N и M (3 ≤ N, M ≤ 100). Затем в последующих N строках задается начальное состояние панели замка. В (i+1)-й строке файла записаны M целых чисел от 1 до min(N, M)-1 – номера цветов ячеек панели замка в i-й строке панели.

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

В первой строке выходного файла OUTPUT.TXT выведите целое число K – количество операций перекрашивания. В следующих K строках опишите предлагаемые операции перекрашивания. Каждая строка описания должна содержать в начале символ «V», если соответствующая операция перекрашивает столбец, и «H», если строку. Затем в строке через пробел идут четыре целых числа x₁, y₁, x₂, y₂ – координаты двух выбранных клеток (здесь x₁ и x₂ – номера столбцов, а y₁ и y₂ – номера строк). Цвета в этих клетках на начало операции перекрашивания должны быть одинаковыми.

Примеры