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

Задача A. Отгадай число

У Васи все хорошо с математикой и он решил удивить Петю своими арифметическими способностями. Он предложил загадать Пете любое целое число X. Далее, Вася попросил утроить загаданное число и прибавить к полученному результату 6. Далее, Петю попросили еще раз умножить результат на 3. А потом требовалось еще от полученного результата отнять 20 и прибавить 11. Всего получилось 6 действий.

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

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

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

Первая строка входного файла INPUT.TXT содержит целое число Y – полученное Петей в результате вычислений число (-10¹⁸ ≤ Y ≤ 10¹⁸).

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

В выходной файл OUTPUT.TXT выведите загаданное Петей число X, если результаты его вычислений могли быть верны, или «error» в противном случае.

Примеры

Задача B. Ёлки

Иван любит уроки математики и рисования. Поэтому он часто эти уроки совмещает, рисуя и вычисляя что-нибудь в тетрадке в клеточку. Сегодня он решил нарисовать N ёлочек по клеткам.

Каждая ёлочка имеет свою красоту K от 1 до N, равную количеству ветвей с одной стороны ствола и длине самой нижней ветви. Каждая следующая верхняя ветка на одну клетку короче предыдущей. Между ветвями, а также под самой нижней и над самой верхней ветвями находится ствол дерева шириной ровно в одну клетку. На приведенном ниже рисунке мы видим все ёлочки для N=5:

Ивана заинтересовал вопрос: сколько всего клеток в тетради ему придется закрасить, чтобы нарисовать N различных ёлок с красотой от 1 до N? Помогите ему решить эту задачу!

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

Входной файл INPUT.TXT содержит одно целое число N (N ≤ 10⁶) – количество ёлок.

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

В выходной файл OUTPUT.TXT выведите одно целое число – общую площадь (количество закрашенных клеток) всех ёлок, которые Иван планирует нарисовать.

Примеры

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

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

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

Задача C. Отпуск

Маша собирает вещи в отпуск. С собой в самолёт она может взять ручную кладь и багаж. Для ручной клади у Маши есть рюкзак, а для багажа – огромный чемодан. По правилам перевозки масса ручной клади не должна превосходить S кг, а багаж может быть любой массы (за сверхнормативный багаж Маша готова доплатить). Разумеется, наиболее ценные вещи – ноутбук, фотоаппарат, документы и так далее Маша хочет положить в ручную кладь. Маша разложила все свои вещи в порядке уменьшения их ценности и начинает складывать наиболее ценные вещи в рюкзак. Она действует следующим образом: берёт самый ценный предмет, и если его масса не превосходит S, то кладёт его в рюкзак, иначе кладёт его в чемодан. Затем она берёт следующий по ценности предмет, если его можно положить в рюкзак, то есть если его масса вместе с массой уже положенных в рюкзак вещей не превосходит S, то кладёт его в рюкзак, иначе в чемодан, и таким же образом процесс продолжается для всех предметов в порядке убывания их ценности.

Требуется определить массу рюкзака и массу чемодана после того, как Маша сложит все свои вещи.

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

Первая строка входного файла INPUT.TXT содержит число S – максимально разрешённую массу рюкзака. Во второй строке записано число N – количество предметов. В следующих N строках даны массы предметов, сами предметы перечислены в порядке убывания ценности (сначала указана масса самого ценного предмета, затем масса второго по ценности предмета и так далее). Все числа натуральные, число S не превосходит 2×10⁹ , общая масса всех предметов также не превосходит 2×10⁹. Значение N не превосходит 10⁵.

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

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

Пример

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

Максимально возможная масса рюкзака 20 кг. Дано 5 предметов весом 6, 10, 5, 2, 3. Сначала предмет весом 6 кладётся в рюкзак, затем предмет весом 10 тоже кладётся в рюкзак. Предмет весом 5 нельзя положить в рюкзак, так как тогда вес рюкзака станет 21 кг, поэтому предмет весом 5 кладётся в чемодан. Затем предмет весом 2 кладётся в рюкзак, а предмет весом 3 – в чемодан. Вес рюкзака 6 + 10 + 2 = 18, вес чемодана 5 + 3 = 8.

Задача D. Получи ноль

Задано натуральное число N. Требуется перед каждым из чисел от 1 до N поставить знак «+» или знак «–» таким образом, чтобы в результате получившаяся сумма чисел стала равна нулю. Например, для N = 3 сумма –1–2+3 (или сумма +1+2–3) будет равна 0, а для N = 2 нулевую сумму получить невозможно.

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

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

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

В выходной файл OUTPUT.TXT выведите последовательность из N символов «+» или «–», соответствующих знакам, которые нужно расставить перед числами от 1 до N так, чтобы сумма получившихся чисел была равна 0. Если задача имеет несколько решений нужно вывести любое из них. Если задача не имеет решения для заданного N выведите слово «IMPOSSIBLE» (без кавычек).

Примеры

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

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

Задача E. Необычная сортировка

Задан целочисленный массив A[1..N] из N различных чисел, в котором записана некоторая фиксированная перестановка чисел от 1 до N, и кроме того, ни одно число в нем изначально не находится на своем месте, то есть A[i] ≠ i для всех i=1..N.

Требуется отсортировать массив (упорядочить в нем элементы по возрастанию), при этом необходимо соблюдать следующие условия:

1. Разрешается менять местами только два соседних элемента массива.
2. Не разрешается изменять положение числа, которое уже находится на своем месте (A[i]=i).

Например, если массив из шести элементов в некоторый момент имеет вид [2, 1, 3, 6, 4, 5], то можно поменять местами 1 и 2, 6 и 4 или 4 и 5, а менять местами 1 и 3 или 3 и 6 нельзя, поскольку число 3 находится на своем месте (на позиции с номером 3).

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

Первая строка входного файла INPUT.TXT содержит целое число N – размер входного массива (2 ≤ N ≤ 100). Вторая строка содержит N целых чисел – исходную перестановку чисел от 1 до N в массиве. Изначально ни одно число не стоит на своем месте.

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

В выходной файл OUTPUT.TXT выведите K строк, где K – количество обменов в сортировке. На каждой строке выведите по два числа x_i и y_i, разделенных пробелом – позиции в массиве, числа на которых следует поменять местами на i-ом обмене. Помните, что должно выполняться условие |x_i–y_i|=1 и что нельзя перемещать число, которое уже стоит на своем месте. Если существует несколько решений, то разрешается вывести любое из них. При этом нет ограничений на число обменов K и решение не обязательно должно быть оптимальным. Если же такого решения не существует, то следует вывести «impossible» (без кавычек) в любом регистре.

Пример