ВОШ Региональный этап ответы и задания для 9, 10, 11 классов олимпиады по Информатике региональный этап 2020-2021 всероссийской олимпиады школьников (ВсОШ). Олимпиада проходит во всех школах регионах России с 16-18 января 2021 г.
• Ссылка для скачивания 1 тур: Скачать
• Ссылка для скачивания 2 тур: Скачать
• Ссылка для скачивания заданий и ответов: strong>Скачать
Интересные задания 1 тура:
Задача 1. Два станка
На производстве имеется два станка. Необходимо изотовить как можно больше деталей за сего-дняшнюю смену, продложительность которой k минут.
Станки находятся в законсервированном состоянии. Для того, чтобы ввести в строй первый станок, требуется a минут, после чего он будет производить x деталей в минуту. Для того, чтобы ввести в строй второй станок, требуется b минут, после чего он будет производить y деталей в минуту.
Для введения в строй станка требуется присутствие инженера, поэтому нельзя вводить в строй два станка одновременно. При этом введение станка в строй и изготовление деталей на другом станке, а также одновременное изготовление деталей на двух станках разрешается.
Требуется выяснить, какое максимальное количество деталей удастся изготовить за k минут.
Формат входных данных
В первой строке ввода дано единственное целое неотрицательное число k количество минут в смене (0 6 k 6 109).
Во второй строке ввода даны целые неотрицательные числа a и x время введения первого станка в строй и количество деталей, которое он изготавливает за одну минуту (0 6 a, x 6 109).
В третьей строке ввода даны целые неотрицательные числа b и y время введения второго станка в строй и количество деталей, которое он изготавливает за одну минуту (0 6 b, y 6 109).
Формат выходных данных
Выведите единственное число максимальное количество деталей, которое удастся изготовить за смену.
Обратите внимание, что ответ в этой задаче может быть довольно большим и не помещаться в 32-битные типы данных. Рекомендуется использовать 64-битный тип данных, например ¾long long¿ в C++ или ¾int64¿ в Паскале.
Задача 2. Разбиение таблицы
Рассмотрим таблицу из n строк и m столбцов, в клетки которой по строкам записаны числа от 1 до n · m. Сначала заполняется первая строка слева направо, затем вторая, и так далее. Другими словами в клетку (r, c) записано число (r − 1) · m + c.
На рисунке приведен пример такой таблицы для n = 3, m = 5.
Требуется разделить таблицу одним вертикальным или горизонтальным разрезом, проходящим по сторонам клеток, так чтобы сумма чисел в получившихся частях таблицы отличалась как можно меньше. В этой задаче в одном тесте вам придётся ответить на несколько запросов об оптимальном разрезании таблицы.
Формат входных данных
В первой строке ввода задано целое число t количеcтво запросов (1 6 t 6 105).
В следующих t строках заданы по два числа n, m (1 6 n, m 6 109, 2 6 n × m 6 109).
Формат выходных данных
В t строках выведите ответы на запросы, по одному на строке.
Ответ на каждый запрос должен быть выведен в формате ¾D x¿, где D это ¾V¿, если нужно
резать по вертикали, ¾H¿ если по горизонтали, а x номер столбца или строки, перед которым надо сделать разрез. Строки пронумерованы от 1 до n, столбцы пронумерованы от 1 до m.
Если правильных ответов несколько, то надо вывести вариант с вертикальным разрезом, если он есть, а если и после этого вариантов несколько, то из вариантов с различными x следует выбрать тот, в котором x меньше.
Задача 3. Изменённая ДНК
Биологи обнаружили новый живой организм и решили изучить его ДНК. ДНК кодируется по-следовательностью символов ¾A¿, ¾G¿, ¾C¿ и ¾T¿.
Так как строка, кодирующая ДНК, часто очень длинная, для её хранения применяют RLE-кодирование. А именно, каждый блок, состоящий из двух или более идущих подряд одинаковых символов, заменяется на число, равное длине этого блока, после которого записывается соответ-ствующий символ. Например, последовательность ¾AAAGGTCCA¿ в закодированной форме имеет вид ¾3A2GT2CA¿.
В результате экспериментов, проводимых в лаборатории, ДНК может мутировать. Каждая му-тация это либо удаление одного символа из последовательности, либо добавление одного символа, либо замена одного символа на другой.
Уходя вечером из лаборатории, учёный записал ДНК в закодированной форме. Когда он вер-нулся на работу утром, он обнаружил, что в ДНК произошла ровно одна мутация. Теперь ученых интересует, какая минимальная и максимальная длина может получиться у новой ДНК в закоди-рованной форме.
Требуется по заданной ДНК в закодированной форме определить, какая мутация может при-вести к тому, что у новой ДНК будет закодированная форма минимальной возможной длины, а какая к тому, что у новой ДНК будет закодированная форма максимальной возможной длины.
Формат входных данных
В единственной строке входа находится строка s, состоящая из цифр и букв ¾A¿, ¾G¿, ¾C¿ и ¾T¿ закодированная ДНК.
Гарантируется, что это строка является корректной закодированной записью некоторой строки из символов ¾A¿, ¾G¿, ¾C¿ и ¾T¿.
Формат выходных данных
В первой строке выведите мутацию, после которой закодированная строка имеет минимальную длину. Выведите:
•1 x Z, если надо вставить символ Z так, чтобы слева от него было ровно x старых сим-волов. Символ Z должен быть из множества {A, C, G, T}.
•2 x, если надо удалить символ с номером x из последовательности.
•3 x Z, если надо заменить символ с номером x заменить на символ Z. Символ Z должен быть из множества {A, C, G, T}. При этом на этом месте до мутации обязательно должен был находиться символ, не равный Z.
В следующей строке выведите мутацию, после которой закодированная строка имеет максималь-ную длину, в таком же формате.
Если подходящих ответов несколько, можно вывести любой из них.
Интересные задания 2 тура:
Задача 5. Календарь на Альфе Центавра
На планете в системе Альфы Центавра год состоит из m месяцев, пронумерованных от 1 до m, а каждый месяц из d дней, пронумерованных от 1 до d. В свою очередь неделя у поселенцев на этой планете состоит из w дней, проиндексированных строчными английскими буквами, от ¾a¿ до w-й буквы английского алфавита.
Первый день первого месяца первого года соответствует букве ¾a¿.
Требуется определить, какой букве будет соответствовать i-й день j-го месяца k-го года.
Формат входных данных
Первая строка ввода содержит три целых числа d, m и w (1 6 d, m 6 100, 1 6 w 6 26). Вторая строка ввода содержит три целых числа i, j и k (1 6 i 6 d, 1 6 j 6 m, 1 6 k 6 109).
Формат выходных данных
Выведите одну строчную букву английского алфавита какой букве соответствует i-й день j-го месяца k-го года.
Задача 6. Числа
Аня любит, когда числа состоят из одинаковых цифр. Поэтому ей нравятся числа 777 или 5555, а вот число 1234 ей совсем не нравится.
Иногда у Ани бывает хорошее настроение, тогда ей по прежнему нравятся все числа, состоящие из одинаковых цифр, но также нравятся числа, в которых все цифры кроме одной одинаковые, как, например, в числе 77727.
У Ани есть число x. Аня хочет найти минимальное целое число y > x, которое ей понравится. Требуется написать программу, которая по заданному целому числу x и информации, хорошее
ли настроение у Ани, находит минимальное целое число y > x, которое нравится Ане.
Формат входных данных
Первая строка ввода содержит целое число x (1 6 x 6 1017, обратите внимание, что число x не может быть сохранено в стандартном 32-битном типе данных, необходимо использовать 64-битный тип данных, например ¾long long¿ в C++, ¾int64¿ в Паскале).
Вторая строка ввода содержит число k, равное 0 или 1. Значение k = 1 означает, что у Ани хорошее настроение, а значение k = 0 что это не так.
Формат выходных данных
Следует вывести одно целое число y. Должны выполняться следующие свойства:
•y > x;
•если k = 0, то все цифры в десятичной записи числа y должны совпадать;
•если k = 1, то все цифры в десятичной записи числа y, кроме, может быть, одной, должны совпадать.
Вам будет интересно:
Результаты региональных этапов Всероссийской олимпиады ВОШ 2020/21 учебного года