Муниципальное общеобразовательное учреждение

средняя общеобразовательная школа №4

Территориальный ресурсный центр

Тверская область, г. Нелидово, ул. Карбышева 14А

Областная олимпиада по информатике

2007 года

Задачи I тура

Задача 1. «Алгоритм Евклида» (100 баллов)

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

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

1. Пусть a, b — числа, НОД которых надо найти.

2. Если b = 0,то число а — искомый НОД.

3. Если Ь > а, то необходимо поменять местами числа а и Ь.

4. Присвоить числу а значение а-Ь.

5. Вернуться к шагу 2. .

Дима достаточно быстро освоил алгоритм Евклида и вычислил с его помощью много наибольших общих делителей. Поняв, что надо дальше совершенствоваться, ему пришла идея решить новую задачу. Пусть заданы числа а, Ь, с и d. Требуется узнать, наступит ли в процессе реализации алгоритма Евклида для заданной пары чисел (а, Ь) такой момент, когда перед исполнением шага 2 число а будет равно с, а число b будет равно d.

Требуется написать программу, которая решает эту задачу.

Формат входных данных

Первая строка входного файла содержит количество наборов входных данных к (1 < к < 100). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: a, b (1 < a, b < 1018). Вторая строка - два целых числа: с, d (1 < с, d < 1018)..

Все числа в строках разделены пробелом.

Формат выходных данных

Для каждого набора входных данных выведите в отдельной строке выходного файла слово «YES», если в процессе применения алгоритма Евклида к паре чисел (а, Ь).в какой-то момент получается пара (с, d), или слово «NO» - в противном случае.

Примеры входных и выходных файлов

euclid.in

euclid.out

20 10

10 10

10 7

2 4

YES

Задача 2. «Преобразование последовательности» (100 баллов)

Задана последовательность, содержащая n целых чисел. Необходимо найти число, которое встречается в этой последовательности наибольшее количество раз, а если таких чисел несколько, то найти минимальное из них, и после этого переместить все такие числа в конец заданной последовательности. Порядок расположения остальных чисел должен остаться без изменения.

Например, последовательность 1, 2, 3, 2, 3, 1,2 после преобразования должна превратиться в последовательность 1, 3, 3, 1, 2, 2, 2.

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

Формат входных данных

Первая строка входного файла содержит число n — количество чисел во входной последовательности (3 < n < 200000). Следующая строка содержит входную последовательность, состоящую из n целых чисел, не превышающих по модулю 10⁹. Все числа в строке разделены пробелом.

Формат выходных данных

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

Пример входного и выходного файлов

trans.in

trans.out

1 2 3 2 3 1 2

1 3 3 1 2 2 2

Задачи II тура

Задача 1. Двойной листок (30 баллов)

Ученик подготовил N* листов одного размера (рис.1) сложил их пополам (рис. 2) и в получившейся тетрадке пронумеровал страницы по порядку: 1, 2, 3, 4...(рис.3)

Листки рассыпались. На одном из них ученик увидел подписанный номер страницы К. По заданным N и К определите все остальные номера страниц, которые тоже находятся на этом же листке.

Пример входных данных	Пример выходных данных
1 4	1 2 3 4

Задание 2. О костях домино (100 баллов)

У игрока имеется набор костей домино (не обязательно полный). На каждой косточке написаны два числа от 0 до 6 (например, 4-0 или 6-6), которые могут быть переставлены при прочтении (4-6 и 6-4 -одна и та же кость). Игра начинается с выкладывания одной косточки. Следующие косточки могут быть вплотную «пристыкованы» к ней справа или слева так, чтобы соседние числа разных косточек совпали, например, к 5-5 можно «пристыковать» 4-5 и 5-6, получится 4-5 5-5 5-6. Найдите последовательность выкладывания костей данного набора таким образом, чтобы получившаяся в результате цепочка была максимально возможной длины.

	Пример входных данных	Пример выходных данных
4		4
4-5		5-4 4-3 3-2 2-1
4-3
3-2
1-2

Задание 3. Самопорожденные числа (100 баллов)

В 1949 году Индийский математик Д. Р. Капрекар открыл класс чисел, называемых самопорожденными. Для любого положительного целого N можно определить функцию d(N) значением которой будет N плюс сумма цифр N.

Например, d(75) = 75 + 7 + 5 = 87. Взяв любое положительное целое N как начальное значение, можно построить бесконечно возрастающую последовательность чисел: N, d(N), d(d(N)), d(d(d(N))), .... Например, если вы начинаете с 33, то следующим числом будет 33 + 3 + 3 = 39, следующее - 39 + 3 + 9 = 51, следующее - 51 + 5 + 1 = 57, таким образом, получается последовательность 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, ...

Число N называется генератором d(N). В приведенной выше последовательности, 33 является генератором 39 39 - генератор 51, 51 - гэнсратср 57, и так далее. Некоторые числа могут иметь более одного генератора. Например, 101 имеет два генератора: 91 и 100. Число, не имеющее генераторов, называется самопорожденным.

Пусть a_i является самопорожденным числом с номером i. Существует 13 самопорожденных чисел (а1..а13), меньших 100: 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, и 97. (первое самопорожденное число a1=2, второе - а2 = 3, ..., тринадцатое - а13=97).

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

Ввод содержит целые числа X, К, s1...Sk. (1<=X<=10⁷, 1<=К<=5000), разделенные пробелами и символами перевода строки. Выходные данные

В первой строке должно содержаться одно число - количество самопорожденных чисел в интервале [1..Х]. Вторая строка

должна содержать К чисел - a_s1...a_sk , разделенных пробелами. Гарантируется, что все самопорожденные числа a_s1...a_sk входят в интервал [1..Х] (например, если X = 100, Sk может быть от 1 до 13 и не может быть 14, т.к. 14-е самопорожденное число a14= 108, 108 > 100).

Пример входных данных

Пример выходных данных

100 10

1 2 3 4 5 6 7 11 12 13

1 3 5 7 9 20 31 75 86 97

Задание 4. Язык BHTML (100 баллов)

Язык разметки гипертекста BHTML содержит всего два парных тега: <UP></UP> и <DOWN></DOWN>. Тег <UP></UP> преобразует все буквы внутри его тела, (между открывающим и закрывающим тегом) к верхнему регистру. Тег <DOWN></DOWN> преобразует все буквы внутри его тела нижнему регистру.

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

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

Входной файл содержит строку текста на языке BHTML. Длина строки не превышает 1000 символов. Теги всегда записаны в верхнем регистре. Выходные данные Выходной файл должен содержать текст после обработки, т.е. в том виде, в каком он будет представлен пользователю.

Пример входных данных

Пример выходных данных

Thi<UP>sls<DOWN>EaSY</DOWN>Pr

<UP>O</UP>ble</UP>m

ThiSISeasyPROBLEm