Задачи олимпиады "Полуфинал XIV Всероссийской командной олимпиады школьников по программированию (Восточно-Сибирский регион)"

Задача A. Семья

Известно, что отец старше сына на N лет, а сын моложе отца в M раз. Определите, сколько лет отцу и сколько лет сыну.

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

Входной файл INPUT.TXT содержит два натуральных числа N и M, разделенных пробелом (1 ≤ N, M ≤ 10⁴). Входные данные таковы, что возраст отца и возраст сына являются целыми числами.

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

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

Примеры

Задача B. Паркет - 2

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

Напоминание: правильный многоугольник – это выпуклый многоугольник, у которого все стороны равны между собой и все углы равны между собой.

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

Входной файл INPUT.TXT содержит целое число N – количество вершин в правильном многоугольнике (3 ≤ N ≤ 1000).

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

В выходной файл OUTPUT.TXT выведите «YES», если плоскость можно замостить и «NO» в противном случае.

Примеры

Задача C. Обмен

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

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

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

Входной файл INPUT.TXT содержит целое число N – количество смешариков, задействованных в обмене (2 ≤ N ≤ 10⁵).

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

В выходной файл OUTPUT.TXT выведите количество вариантов обмена фантиками по модулю 10⁹+9.

Примеры

Задача D. Апельсины - 2

На склад привезли коробку свежих апельсинов. Известно, что при поступлении апельсины весили ровно N грамм, а их влажность была F%. При хранении на складе апельсины могут либо вбирать в себя влагу из окружающего воздуха, либо терять влагу, если в помещении жарко и сухо. На складе решили апельсины ежедневно взвешивать и записывать изменения их массы в журнал: на сколько уменьшилась или увеличилась их масса по сравнению с предыдущим днем из-за поглощения влаги из воздуха или, наоборот, усыхания. Через M дней выяснилось, что апельсины необходимо перевезти на другой склад. Для этого нужно указать их текущий вес и влажность (в процентах).

Напомним, что влажность – это количество воды в веществе (в процентах) от первоначальной массы вещества.

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

Первая строка входного файла INPUT.TXT содержит три целых числа, разделенных пробелом: N – вес апельсинов (1 ≤ N ≤ 10⁹), F – влажность апельсинов в процентах (1 ≤ F ≤ 99), M – количество дней (0 ≤ M ≤ 100). Далее идет M строк, в каждой из которых указано целое число K (|K| ≤ 10⁷) – на сколько грамм изменился вес апельсинов по сравнению с предыдущим днем (со знаком «+», если он увеличился и со знаком «-», если уменьшился).

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

В выходной файл OUTPUT.TXT выведите два целых числа через пробел: вес в граммах и влажность апельсинов в процентах через M дней. Влажность следует округлить до целого числа.

Примеры

Задача E. Ученики

Однажды, неловкая секретарша перепутала личные дела учащихся. Теперь их снова необходимо упорядочить сначала по классам, а внутри класса по фамилиям.

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

Первая строка входного файла INPUT.TXT содержит натуральное число N – количество учеников (N ≤ 100). Далее, для каждого ученика определены 4 строки, содержащие фамилию, имя, класс и дату рождения соответственно. Фамилия и имя – строки, не превышающие 20 символов английского алфавита: первая буква заглавная, остальные – строчные. Класс – строка, состоящая из числа (от 1 до 11) и заглавной английской буквы (от «A» до «Z»). Дата рождения – строка в формате «ДД.ММ.ГГ». Гарантируется, что внутри одного класса нет однофамильцев.

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

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

Пример

Задача F. Функция - 3

Найдите все корни уравнения:

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

Входной файл INPUT.TXT содержит одно вещественное число C, не превышающее 10¹⁰ по абсолютной величине.

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

В выходной файл OUTPUT.TXT выведите все корни уравнения через пробел в порядке возрастания с ровно 6 знаками после запятой. В случае отсутствия корней следует вывести сообщение «No solution».

Примеры

Задача G. Игра - 4

А вы играли в игру «Кота в угол»? Правила игры очень просты. Есть прямоугольное игровое поле, заполненное клетками по принципу пчелиных сот – из каждой клетки можно перейти на 6 соседних. На одной из клеток сидит кот. За один ход кот может перейти на одну из соседних клеток, если она свободна (на рисунке свободные клетки светлые, а занятые – темные). Кот хочет как можно быстрее выйти за пределы игрового поля.

Определите минимальное число ходов, за которое он сможет это сделать.

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

Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M – количество строк и количество клеток в строке соответственно (N, M ≤ 1000). Вторая строка содержит два натуральных числа Y, X – номер строки и номер клетки в строке, где находится кот (Y ≤ N, X ≤ M). Далее идет N строк по M символов – описание игрового поля. Свободные клетки обозначены символом «1», занятые – символом «0».

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

В выходной файл OUTPUT.TXT выведите минимальное количество ходов, за которое кот может выйти за пределы игровой области. Или «No solution» (без кавычек), если это невозможно.

Примеры

Задача H. Последовательность - 6

Дано натуральное число A. К нему применили следующую операцию – все цифры возвели в квадрат и просуммировали.

Например, для числа 123 получим 1² + 2² + 3² = 14.

К полученному результату указанную операцию применили еще несколько раз.

Определите, какое число получится, если указанную операцию повторить ровно N раз для заданного числа A.

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

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

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

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

Примеры

Задача I. Биты

Дано натуральное число N. Необходимо найти младший и старший биты двоичной записи числа N, установленные в единицу, и вывести их в десятичной системе счисления.

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

Входной файл INPUT.TXT содержит натуральное число N (N ≤ 10¹⁸).

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

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

Примеры

Пояснение

В первом примере N = 26₁₀ = 11010₂. Младший бит (11010) равен 10₂ = 2₁₀, старший бит (11010) равен 10000₂ = 16₁₀.