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

Задача A. Температура

Известно, что существует несколько единиц измерения температуры. В России, как правило, температуру измеряют в градусах Цельсия (^◦С), в США чаще используют градусы Фаренгейта (^◦F), а в физике используют систему СИ и термодинамическую шкалу определяют через шкалу Кельвина (K).

Требуется по заданному значению температуры в градусах Цельсия получить значение этой температуры в градусах Фаренгейта по следующей формуле:

^◦F = ^◦С × 1,8 + 32

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

Входной файл INPUT.TXT содержит целое число T – температуру в градусах Цельсия (-273 ≤ T ≤ 10⁹).

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

В выходной файл OUTPUT.TXT выведите точное значение температуры T в градусах Фаренгейта.

Примеры

Задача B. Cashback

Известно, что в настоящее время многие банки предлагают систему возврата части потраченных средств, именуемую cashback (кешбек) в целях привлечения клиентов.

Предположим, что у Вас есть три карты различных банков: Darkoff Bank, Beta Bank и Vendel Bank. Карты разных банков имеют различные условия возврата потраченных средств. Так, на карту банка Darkoff Bank возвращается 5 рублей из каждых полных 100 рублей стоимости одной покупки. Например, за покупки стоимостью 100 и 199 рублей возвращается равная сумма в размере 5 рублей. Банк Beta Bank возвращает 2 рубля с каждых 50 рублей покупки, и за покупку стоимостью 199 рублей он вернет уже 6 рублей. А банк Vendel Bank возвращает 3% с полной стоимости любой покупки, поэтому за покупку в 199 рублей он вернет 5 рублей и 97 копеек.

Вам предстоит осуществить очередную покупку, стоимость которой известна. Требуется определить банк, карту которого следует использовать для получения максимального кешбека. Если некоторые лучшие карты дают одинаковый результат, то следует выбирать банк с наивысшим рейтингом. Максимальный рейтинг имеет банк Vendel Bank, далее идет Beta Bank, а банк Darkoff Bank имеет самый низкий рейтинг среди представленных банков.

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

Первая строка входного файла INPUT.TXT содержит целое число X – стоимость покупки в рублях (1 ≤ X ≤ 10 000).

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

В выходной файл OUTPUT.TXT выведите название банка, картой которого выгоднее оплатить покупку.

Примеры

Задача C. Путешествие вдоль реки

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

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

По заданной карте реки определите минимальное количество переправ, которое Вам придётся совершить.

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

Единственная строка входного файла INPUT.TXT содержит описание реки между начальной и конечной точкой путешествия. Длина строки не превышает 200 символов.

Каждый символ строки может быть одной из трех латинских букв L, R или B. Буква L означает, что очередной приток впадает в реку с левого берега, R – приток впадает в реку с правого берега и B – притоки впадают с обоих берегов реки в одном месте. Путешествие начинается на левом берегу перед описанной частью реки и заканчивается на правом берегу после описанной части.

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

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

Пример

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

Задача D. Автобус №13

На одну из остановок общественного транспорта пришло N пассажиров, при этом время прихода каждого из них известно. Всех пассажиров интересует автобус №13, маршрутом которого они желают воспользоваться. Также известно, что автобус проходит через остановку каждые K минут. Пассажир, находящийся на остановке в момент прихода автобуса, уезжает на нем.

Требуется определить время T (0 ≤ T < K) первого прихода автобуса на остановку, чтобы:

1. Суммарное время ожидания автобуса для всех пассажиров было минимально.
2. Максимальное из времен ожидания автобуса было минимально.

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

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

Вторая строка входных данных содержит N целых чисел T_i – времена прихода пассажиров на остановку (0 ≤ T_i ≤ 10⁵).

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

В выходной файл OUTPUT.TXT выведите два числа – ответы на первый и второй вопросы задачи соответственно. Если решений несколько, выведите любое из них.

Пример

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

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

Задача E. Замкнутая сортировка

Задан целочисленный массив A[1..N] из N различных чисел, в котором записана некоторая фиксированная перестановка чисел от 1 до N. Будем считать, что первый и последний элементы массива соединены таким образом, что за последним следует первый, а перед первым располагается последний. Мы получили замкнутую последовательность чисел без начала и конца.

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

1. Разрешается менять местами только два соседних элемента массива.
2. Не разрешается менять местами элементы, если они отличаются ровно на единицу.

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

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

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

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

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

Пример