Задачи олимпиады "II (районный) этап Всероссийской олимпиады школьников Красноярского края по информатике"
Задача A. Алгоритм Евклида
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Дима недавно начал изучать информатику. Одним из первых алгоритмов, который он изучил, был алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел. Напомним, что наибольшим общим делителем двух чисел a и b называется наибольшее натуральное число x, такое, что и число a, и число b делится на него без остатка.
Алгоритм Евклида заключается в следующем:
Пусть a, b – числа, НОД которых надо найти.
Если b = 0, то число a – искомый НОД.
Если b > a, то необходимо поменять местами числа a и b.
Присвоить числу a значение a – b.
Вернуться к шагу 2.
Дима достаточно быстро освоил алгоритм Евклида и вычислил с его помощью много наибольших общих делителей. Поняв, что надо дальше совершенствоваться, ему пришла идея решить новую задачу. Пусть заданы числа a, b, c и d. Требуется узнать, наступит ли в процессе реализации алгоритма Евклида для заданной пары чисел (a, b) такой момент, когда число a будет равно c, а число b будет равно d.
Требуется написать программу, которая решает эту задачу.
Входные данные
Первая строка входного файла INPUT.TXT содержит количество наборов входных данных k (1 ≤ k ≤ 100). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: a, b (1 ≤ a, b ≤ 1018). Вторая строка – два целых числа: c, d (1 ≤ c, d ≤ 1018).
Выходные данные
Для каждого набора входных данных выведите в отдельной строке выходного файла OUTPUT.TXT слово «YES», если в процессе применения алгоритма Евклида к паре чисел (a, b) в какой-то момент получается пара (c, d), или слово «NO» – в противном случае.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
2 20 10 10 10 10 7 2 4
YES NO
Задача B. Подпись
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Марсиане Миша и Маша решили вместе подобрать подарок на день рождения Кати. Когда они наконец нашли то, что хотели, и упаковали предмет в красивую коробку, надо было решить, как подписать подарок. Друзья подумали, что лучшим решением будет составить общую подпись так, чтобы в ней как подстроки содержались их имена.
Учтите, что на Марсе принято подписываться полными именами, а они у марсиан могут быть достаточно длинными.
Входные данные
Входной файл INPUT.TXT содержит две строки, в которых записаны полные имена друзей. Имена, как ни странно, состоят из букв английского алфавита, из которых только первая – прописная. Длина имен от 1 до 1000 символов.
Выходные данные
В выходной файл OUTPUT.TXT выведите кратчайшую строку, в которой встречаются имена Миши и Маши одновременно. Буквы, с которых имена начинаются в этой строке нужно сделать большими. Если существует несколько решений, выведите то, которое меньше в алфавитном порядке (следует считать, что любая буква в верхнем регистре меньше, чем любая буква в нижнем регистре).
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
Misha Masha
MashaMisha
2
Julya Lyalya
JuLyalya
Задача C. Замок
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Замок состоит из K уровней. Каждый уровень - это правильный N-угольник, угол которого совпадает с углом предыдущего. На сторонах первого уровня находится по две комнаты (в углах), на сторонах каждого следующего - на одну больше. Сколько в замке комнат?
Входные данные
В первой строке входного файла INPUT.TXT указаны два целых числа N и K
(3 ≤ N ≤ 106; 1 ≤ K ≤ 106).
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число - количество комнат в замке.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
6 3
28
Задача D. Длина отрезка
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Отрезок задан координатами своих концевых точек. Требуется вычислить длину этого отрезка.
Входные данные
Первая строка входного файла INPUT.TXT содержит координаты концов отрезка в формате X1 Y1 X2 Y2 . Все координаты – целые числа, не превышающие 1000 по абсолютной величине.
Выходные данные
В выходной файл OUTPUT.TXT выведите длину отрезка с точностью 10-5.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
3 4 8 4
5
Задача E. Сумма двух чисел
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Заданы три числа: a, b, c. Необходимо выяснить, можно ли так переставить цифры в числах a и b, чтобы в сумме получилось c.
Входные данные
Входной файл INPUT.TXT содержит три целых числа: a, b, c (0 ≤ a, b, c < 109). Числа разделены пробелом.
Выходные данные
В выходной файл OUTPUT.TXT следует вывести YES, если искомая перестановка цифр возможна, в противном случае необходимо вывести NO. При положительном ответе во второй строке следует вывести число x, получаемое перестановкой цифр числа a, и число y, получаемое перестановкой цифр числа b, сумма которых равна c. Числа x и y при выводе не должны содержать ведущих нулей. Числа в строке разделены пробелом. Если решений несколько, то следует вывести ту пару, в которой число x минимально.
