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

Задача A. Газировка

Предприятие по производству газировки ежедневно отгружает один и тот же объем этого чудесного напитка. Служба доставки сети ресторанов обычно использует для транспортировки емкости объемом или только 50 литров, или только 70 литров. Если доставка осуществляется с помощью емкостей в 50 литров, то для перевозки имеющегося объема газировки необходимо A емкостей. А если с помощью емкостей в 70 литров, то необходимо B емкостей. При этом в каждом из случаев одна из емкостей может быть заполнена не полностью.

Недавно сеть ресторанов решила утвердить новый объем емкостей для доставки – 60 литров. Сколько емкостей теперь может понадобиться для доставки того же самого объема газировки?

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

Первая строка входного файла INPUT.TXT содержит два целых числа A и B – необходимое число ёмкостей по 50 и 70 литров соответственно (1 ≤ A, B ≤ 10⁷).

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

В выходной файл OUTPUT.TXT выведите все возможные значения для количества емкостей по 60 литров, которые окажутся заполненными (в том числе одна возможно частично), в порядке возрастания или число  - 1, если значения A и B противоречат друг другу, то есть они были записаны неверно.

Примеры

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

В первом примере газировки могло быть, например, 115 литров, в этом случае понадобится две емкости в 60 литров, а могло быть – 135 литров, в этом случае понадобятся уже три емкости по 60 литров. Четыре емкости не могут понадобиться никогда.

Во втором примере легко видеть неточность в данных, так как количество ёмкостей по 70 литров не может превышать число ёмкостей по 50 литров (увеличение объёма используемых ёмкостей может только уменьшить их количество).

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

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

Задача B. Волшебная последовательность

Последовательность из K+1 целого числа A₀, A₁, …, A_K будем называть «волшебной», если она однозначно определяется первым своим элементом A₀ и значением K следующим образом. От последнего имеющегося числа последовательности отделяется последняя цифра его десятичной записи, возводится в пятую степень, умножается на 20 и прибавляется к числу, получившемуся после отделения этой цифры. При этом следует считать, что при отделении последней цифры от однозначного числа получается ноль. Именно таким образом формируется каждый последующий элемент A_i из A_i-1 для i от 1 до K.

Математически эту операцию преобразования числа d, состоящего из n цифр, можно описать следующим образом:

d_nd_n-1…d₁ → d_nd_n-1…d₂ + 20×d₁⁵

По заданному первому элементу последовательности A₀ и значению K требуется определить наименьший и наибольший элементы заданной последовательности.

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

Первая строка входного файла INPUT.TXT содержит два целых числа: A₀ и K – первый элемент последовательности и количество последующих её элементов соответственно (0 ≤ A₀ ≤ 10⁹, 0 ≤ K ≤ 10⁴).

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

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

Пример

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

Здесь мы получаем следующую последовательность из 11 чисел:

10 → 1 → 20 → 2 → 640 → 64 → 20486 → 157568 → 671116 → 222631 → 22283.

Задача C. Сортировка массива

Задан целочисленный массив A[1..N]. Элементы массива имеют различные значения от 1 до N. Требуется упорядочить элементы массива по возрастанию, используя последовательность обменов значений пары элементов. При этом разрешается проводить обмен только тех элементов, значения которых отличаются друг от друга на 1. Например, для элемента со значением 5 возможен обмен только с элементами со значением 4 или 6, а элемент со значением 1 можно менять только с элементом со значением 2.

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

Первая строка входного файла INPUT.TXT содержит целое число N (1 ≤ N ≤ 100) – количество элементов в массиве. Во второй строке заданы N разделенных пробелами различных чисел A_i (1 ≤ A_i ≤ N, 1 ≤ i ≤ N) – элементы массива.

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

В первой строке выходного файла OUTPUT.TXT выведите число k – количество ходов в возможной сортировке. На следующих k строках выведите последовательность ходов таким образом, чтобы на строчке с номером m было выведено два числа i и j, обозначающие позиции элементов массива, которые необходимо поменять на m-м шаге. Выведите любой вариант решения, количество операций в котором не превышает 50 000.

Если для заданного массива решения не существует, выведите «No solution» (без кавычек).

Пример

Задача D. Флаги

У Васи есть ткань прямоугольной формы, которая имеет клетчатую структуру и состоит из N×M цветных частей, разбитых на N строк и M столбцов.

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

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

Помогите Васе вычислить количество различных флагов, которые могут у него получиться.

Примеры прямоугольников, являющихся флагами:

Примеры прямоугольников, не являющихся флагами:

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

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

Каждая из последующих N строк входных данных описывает очередную строку материи и состоит из M строчных английских букв от «a» до «z», где одинаковым цветам соответствуют одинаковые буквы, а разным цветам – разные буквы.

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

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

Пример

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

Выделенные прямоугольники на следующем изображении обозначают все возможные флаги, которые можно получить:

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

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

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

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

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

Задача E. Арифметическая прогрессия

К элементам некоторой последовательности A, состоящей из n чисел, были добавлены n элементов другой последовательности B. После чего все элементы новой последовательности были перемешаны. В результате образовалась новая последовательность C, состоящая из 2n элементов.

Требуется восстановить исходную последовательность A из последовательности C. При этом известно, что последовательность A является арифметической прогрессией.

Напомним, что последовательность A₁, A₂, …, A_n называют арифметической прогрессией, если A_i = A_i-1 + d для всех i от 2 до n и некоторого d.

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

В первой строке входного файла INPUT.TXT содержится целое число n (1 ≤ n ≤ 10⁵). В следующей строке находится 2n целых чисел – элементы последовательности C (-10⁹ ≤ C_i ≤ 10⁹).

Гарантируется, что из чисел последовательности C можно выбрать n чисел так, чтобы они образовывали арифметическую прогрессию.

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

В выходной файл OUTPUT.TXT выведите два числа A₁ и d – первый элемент и разность найденной арифметической прогрессии. Если d = 0, то число A₁ должно встречаться среди заданных чисел не менее n раз. Если существует несколько решений, выведите любое.

Пример

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

Искомой последовательностью может служить последовательность чисел 2, 8, 14 (A₁ = 2, d = 6). Также в качестве верного ответа здесь может быть последовательность 2, 6, 10 (A₁ = 2, d = 4).

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

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

Задача F. Делители

Задан массив a[1..n], состоящий из n натуральных чисел. Требуется выполнить над массивом ряд операций двух типов:

• 0 i x – присвоить i-му элементу массива значение x;
• 1 l r – вывести количество делителей у произведения чисел на отрезке с l по r. Это число может быть довольно большим, поэтому ответ требуется вывести по модулю 10⁹+7.

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

В первой строке входного файла INPUT.TXT содержится число n (1 ≤ n ≤ 5×10⁴) – количество элементов массива.

Во второй строке записаны n чисел a_i (1 ≤ a_i ≤ 10⁴) – элементы массива.

В третьей строке дано число q (1 ≤ q ≤ 10⁴) – количество запросов.

В каждой из следующих q строк записано по три числа. Если первое из этих чисел равно 0, то это запрос обновления элемента массива, если же первое число равно 1, то это запрос на нахождение количества делителей у произведения чисел на отрезке [l, r] по модулю 10⁹+7.

Гарантируется, что во всех запросах 1 ≤ i, l, r ≤ n и 1 ≤ x ≤ 10⁴.

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

В выходной файл OUTPUT.TXT для каждого запроса на вывод количества делителей в отдельной строке выведите ответ по модулю 10⁹+7.

Пример

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

Решения, работающие только для n ≤ 10, a_i ≤ 30 и q ≤ 20, будут оцениваться в 30 баллов.