Problem A: Игра

Time limit = 2 секунды

Memory limit = 64 мегабайта

Рассмотрим следующую игру. Изначально на доске записано целое положительное число X. Пусть перед очередным ходом одного из играющих записано число X1. Игрок, делающий ход, выбирает целое число Y от 1 до 20 и заменяет X1 на X1-Y. Ходы делаются по очереди. Выигрывает тот, кто после своего хода получит 0. Человек играет партию в эту игру с компьютером. При этом первый ход всегда делает человек, а компьютер действует по следующей схеме: если человек предыдущим ходом вычитает число I, программа или выигрывает в один ход (если записанное на доске число не превосходит 20), или делает ход Yi, однозначно определённый значением I. По заданным X и Yi выясните, имеет ли человек шансы выиграть у робота.

Формат входных данных. В первой строке входных данных задано 1 ≤ X ≤ 109 --- исходное число. Во второй заданы 20 чисел 1 ≤ Yi ≤ 20. Число Yi обозначает ответный ход компьютера на ход человека, заключавшийся в вычитании числа i.

Формат выходных данных. Выведите 1, если человек может выиграть у робота, и 0 в противном случае.

Пример

Ввод

Вывод

83

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 
 
1

Problem B: Numbers

Time limit = 2 секунды

Memory limit = 64 мегабайта

Заданы восемь целых чисел xmin,xmax,ymin,ymax,smin,smax,dmin,dmax. Надо найти количество пар целых чисел (x,y) таких, что xmin ≤ x ≤ xmax, ymin ≤ y ≤ ymax, smin ≤ x+y ≤ smax, dmin ≤ x-y ≤ dmax.

Формат входных данных. 8 целых чисел xmin,xmax,ymin,ymax,smin,smax,dmin,dmax, по модулю не превосходящие 106.

Формат выходных данных. Одно целое число --- искомое количество пар целых чисел.

Пример

Ввод

Вывод

-1 1 

-1 1 

-2 1 

-10 10 
8



Problem C: Almost prime.

Time limit = 2 секунды

Memory limit = 64 мегабайта

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

Формат входных данных. Oдно целое число N (1 ≤ N ≤ 109)

Формат выходных данных. Выведите ближайшее к N полупростое число в соответствии с условиями задачи.

Пример

Ввод

Вывод

5
4
10
10

Problem D: Game:Time limit = 2 секунды

Memory limit = 64 мегабайта

Постройте граф из n вершин с наибольшем количеством ребер, в котором нет треугольников, то есть циклов из трёх рёбер.

Формат входных данных. 2 ≤ n ≤ 103 --- исходное число.

Формат выходных данных. 1 число - количество рёбер.

Пример

Ввод

Вывод

2 
1
20
100



Problem D: Triangles

Time limit = 2 секунды

Memory limit = 64 мегабайта

Постройте граф из n вершин с наибольшем количеством ребер, в котором нет треугольников, то есть циклов из трёх рёбер.

Формат входных данных. 2 ≤ n ≤ 103 --- исходное число.

Формат выходных данных. 1 число - количество рёбер.

Пример

Ввод

Вывод

2 
1
20
100



Problem E: Magnitude.

Time limit = 2 секунды

Memory limit = 64 мегабайта

В 1856 году Н. Погсон предложил формализацию шкалы звёздных величин. Видимая звёздная величина определяется по формуле: m = -2,5 lg I + C, где I — световой поток от объекта, C — постоянная. Звёздная величина Солнца, наблюдаемая с Земли (орбита радиусом 1 астрономическая единица), равна -26,7. Шкала звёздных величин является логарифмической, поскольку изменение яркости в одинаковое число раз воспринимается как одинаковое (закон Вебера — Фехнера). Кроме того, поскольку Гиппарх решил, что величина тем меньше, чем звезда ярче, то в формуле присутствует знак минус, а увеличению светового потока в 100 раз соответствует уменьшение видимой звёздной величины на 5 единиц. Световой поток от звезды обратно пропорционален квадрату расстояния до неё Какую звёздную величину будет иметь Солнце с орбиты планеты, радиус которой X астрономических единиц?

Формат входных данных. 1.0 ≤ X ≤ 103 --- радиус орбиты планеты.

Формат выходных данных. Одно действительное число с точностью до 1 знака после запятой - звёздная величина.

Пример

Ввод

Вывод

1.0
 -26.700000  
10.0
-21.700000



Problem F: Search:

Time limit = 2 секунды

Memory limit = 64 мегабайта

Дан текст, состоящий из не более чем 5*106 символов. В тексте могут встречаться символы  с кодами от 32 до 127, а также переводы строк (символов с кодом 10) и табуляции (символов с кодом 9). Словом называется последовательность строчных и прописных латинских букв, ограниченная или началом/концом строки, или символом, не являющимся строчной или прописной латинской буквой. 

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

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

В первой строке входного файла записана  команда <text>. Далее, в последующих строках, задан исходный текст. О завершении ввода текста сигнализирует команда </text> в отдельной строке.

Далее идет количество запросов N100, после чего по одному на строку идут сами запросы. Количество слов в запросе не превосходит 100. Длина каждого слова в запросе не превосходит 10.
Слова в запросе разделены пробелами. Длина текста не более 5Mb.

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

Для каждого запроса  в отдельной строке выведите YES, если все слова из запроса встречаются в тексте (не являясь при этом частью какого-то другого слова) и NO в противном случае. 

Пример

Ввод

Вывод

<text>
This task is too hard for me
</text>
3
for me this task is too hard
me for this task
task is easy
YES
YES
NO

 

Problem G: Bridges

Time limit = 2 секунды

Memory limit = 64 мегабайта

Пара ребер называется 2-мостом, если эти ребра имеют общий конец и при удалении их из графа число компонент связности увеличивается. Вам нужно найти число 2-мостов.

Формат входных данных. В файле задан неориентированный невзвешенный граф без кратных ребер и петель. В первой строке числа N и M --- число вершин и ребер графа (0 ≤ N, M ≤ 105). Далее M строк, в каждой 2 числа от 1 до N --- концы очередного ребра.

Формат выходных данных. Одно число --- количество различных пар ребер, являющихся 2-мостами.

Пример

Ввод

Вывод

4 4
1 2
2 3
3 1
1 4
5



Problem H: Cells

Time limit = 2 секунды

Memory limit = 64 мегабайта

Задано поле клеток размером NxM. На нем некоторые клетки проколоты. Требуется установить, существует ли путь из клетки с координатами   (Ax, Ay)  в клетку (Bx, By). Путь не должен проходить через проколотые точки. Передвигаться можно только влево, вправо, вверх, вниз. Выход за пределы поля запрещен.

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

Размер поля 1≤N≤1018, 1≤M≤1018.

Координаты клетки (Ax, Ay),  1≤AxN,  1≤AyM

Координаты клетки (Bx, By),  1≤Bx≤N,  1≤By≤M

Количество проколотых точек 0 ≤ K ≤ 105

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

Ответ Yes , если путь существует, и No в противном случае.

Пример

Ввод

Вывод

3 3
1 1
3 3
3
2 1
2 2
2 3
No



Problem I: Virus

Time limit = 2 секунды

Memory limit = 16 мегабайт

Недалёкое будущее. У Вас оказалось n нанороботов, каждый из которых имеет свой номер (нумерация начинается с 0) и программу. Известно, что v из них заражены нановирусом для нанороботов (говоря, что автор пользовался для написания исходного кода этого вируса текстовым редактором nano). Нановирус размножается по такому алгоритму: если он работает на нанороботе номер X, то он заражает нанороботов с номерами X*2, X*3+1, X*4+3, X*5+6... (при каждом заражении разница номеров между подряд идущими заражёнными увеличивается на 1). С вновь заражённых нанороботов вирус уже никуда не распространяется (см. ответ к примеру). И теперь нужно подсчитать: сколько же у Вас заражённых нанороботов?

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

1 ≤ v ≤ 102 - количество изначально заражённых,

1 ≤ n ≤ 108 - общее количество нанороботов,

далее v чисел - номера заражённых нанороботов.

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

1 число - количество заражённых нанороботов.

Примеры

Вход

Выход

1 100 99

1

2 1000 3 4

85



Problem J: Plan.


    В рамках инновационного плана «Россия Вперед!™», разрабатывается Великий План™ по преобразованию всех технологических карт заводов для выпуска новой продукции.
Технологическая Карта Завода представляет собой конвеер-последовательность из стандартных станков и прочих машин. Каждый из станков и машин кодируются уникальным одно буквенным кодом из диапазона {0-9, A-z, a-z} в соответствии с ГОСТ-ом.
Например «04ABFGSDDD8F67GODMNDOT895J4C7DHT84H»,  но вообще, технологическая карта может быть очень длинной (до 1000 знаков).

    Соответственно, Аналитики™ Великого Плана™ исследуют возможности по оптимальной перестройке всех заводов, выполняя многофакторную оптимизацию.

    Вы, как программист Императорского Бюро Вычислительных Машин, решаете частную задачу:
для завода с технологической картой OLD, и предлагаемой новой картой NEW. Вам необходимо предложить оптимальный план перестройки завода, используя три возможных операции:


То есть для заданных технологических карт OLD и NEW ваша программа должна рассчитать план перестройки минимальной стоимостью.

Формат входных данных.
    В первой и второй строках входного файла заданы старый(OLD) и новый(NEW) планы соответственно. Каждый из которых представляющий собой не пустую последовательность символов {0-9, A-Z, a-z} длиной не более 1000 символов.

Формат выходных данных.
    В единственной строке выведите одно целое число минимальную стоимость операций, приводящих старый план в новый
 

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

Вход

Выход

bba

abbaaa


9

abbb

abba

4