Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Положение] [Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

Задачи олимпиады "II (районный) этап Всероссийской олимпиады школьников Красноярского края по информатике"

Задача A. Алгоритм Евклида

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Дима недавно начал изучать информатику. Одним из первых алгоритмов, который он изучил, был алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел. Напомним, что наибольшим общим делителем двух чисел a и b называется наибольшее натуральное число x, такое, что и число a, и число b делится на него без остатка.

Алгоритм Евклида заключается в следующем:

  1. Пусть a, b – числа, НОД которых надо найти.
  2. Если b = 0, то число a – искомый НОД.
  3. Если b > a, то необходимо поменять местами числа a и b.
  4. Присвоить числу a значение a – b.
  5. Вернуться к шагу 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.TXTOUTPUT.TXT
12
20 10
10 10
10 7
2 4
YES
NO

Задача B. Подпись

(Время: 1 сек. Память: 16 Мб Баллы: 100)

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

Учтите, что на Марсе принято подписываться полными именами, а они у марсиан могут быть достаточно длинными.

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

Входной файл INPUT.TXT содержит две строки, в которых записаны полные имена друзей. Имена, как ни странно, состоят из букв английского алфавита, из которых только первая – прописная. Длина имен от 1 до 1000 символов.

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

В выходной файл OUTPUT.TXT выведите кратчайшую строку, в которой встречаются имена Миши и Маши одновременно. Буквы, с которых имена начинаются в этой строке нужно сделать большими. Если существует несколько решений, выведите то, которое меньше в алфавитном порядке (следует считать, что любая буква в верхнем регистре меньше, чем любая буква в нижнем регистре).

Примеры

INPUT.TXTOUTPUT.TXT
1Misha
Masha
MashaMisha
2Julya
Lyalya
JuLyalya

Задача C. Замок

(Время: 1 сек. Память: 16 Мб Баллы: 100)
Замок

Замок состоит из K уровней. Каждый уровень - это правильный N-угольник, угол которого совпадает с углом предыдущего. На сторонах первого уровня находится по две комнаты (в углах), на сторонах каждого следующего - на одну больше. Сколько в замке комнат?

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

В первой строке входного файла INPUT.TXT указаны два целых числа N и K (3 ≤ N ≤ 106; 1 ≤ K ≤ 106).

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

В выходной файл OUTPUT.TXT выведите целое число - количество комнат в замке.

Пример

INPUT.TXTOUTPUT.TXT
16 328

Задача D. Длина отрезка

(Время: 1 сек. Память: 16 Мб Баллы: 100)
Отрезок, заданный координатами своих концевых точек

Отрезок задан координатами своих концевых точек. Требуется вычислить длину этого отрезка.

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

Входной файл INPUT.TXT содержит координаты концов отрезка в формате X1 Y1 X2 Y2 . Все координаты – целые числа, не превышающие 1000 по абсолютной величине.

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

В выходной файл OUTPUT.TXT выведите длину отрезка с точностью 10-5.

Пример

INPUT.TXTOUTPUT.TXT
13 4 8 45

Задача 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 минимально.

Примеры

INPUT.TXTOUTPUT.TXT
112 31 25YES
12 13
212 31 26NO
3101 2 13YES
11 2


Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483



Виниловые слэп браслеты браслеты. У нас: слэп браслеты: Лучшие браслеты c доставкой!   Все мне давно советуют смотреть сериал кухня http://kuhnyamero.ru, и я нашел для этого хороший сайт!