Смайлик с центром в точке (x0, y0) представляет из себя окружность радиуса 100 с центром в точке (x0, y0), из которой вырезаны две окружности радиуса 30 с центрами в точках (x0 - 40, y0 + 30) и (x0 + 40, y0 + 30) и нижняя половина окружности радиуса 60 с центром в точке (x0, y0 - 20) (смотри рисунок). В задаче требуется найти площадь объединения двух заданных смайликов.
В единственной строке через пробел даны четыре целых числа - 1000 ≤ x1, y1, x2, y2 ≤ 1000, где (x1, y1) – координаты центра первого смайлика, а (x2, y2) – координаты центра второго смайлика.
Выведите единственное число – ответ на задачу, c абсолютной погрешностью не более 10 - 4.
-1000 -1000 1000 1000
40212.3859659494
0 0 0 0
20106.1929829747
0 0 -10 0
23899.0852307386
Маленький Пафнутий недавно выучил буквы. Теперь он радостно пишет их в ряд в тетради. Написав достаточно большую строку, Пафнутий задумался о прекрасном – а достаточно ли красива его строка? Еще немного помедлив, он понял, что считает строку красивой, если она имеет вид a1a2a2a3a3a3... an... an. Например, строки a, abbccc, aaaaaa, xaabbbbbbb – красивые, а строки abbcc, aa, bbaaa – нет. Теперь Пафнутий просит Вас помочь найти в его строке красивую подстроку максимальной длины.
В единственной строке входного файла задана непустая строка s длиной не более 105 символов, состоящая из строчных букв латинского алфавита.
Выведите искомую подстроку.
abbccc
abbccc
misis
m
missiiis
issiii
aaaaaaa
aaaaaa
Суперкомпьютер по имени Lesli очень любит играть с программистами в различные интеллектуальные игры. Сегодня планируется играть в игру “Числа” и Lesli очень хочет победить. Но никто из программистов не соглашается запрограммировать Lesli для игры в “Числа”, чтобы избавиться от сильного конкурента. А ты сможешь помочь Lesli?
В игру “Числа” играют двое, ходят по очереди. Игра начинается с некоторого целого числа n, 1 ≤ n ≤ 109. Далее каждый игрок в свой ход должен выбрать число вида pk такое, что p – простое число, k – целое положительное число, n делится нацело на pk, после чего разделить n на pk. Более того, запрещено использовать простое число p, которое использовал соперник на предыдущем ходу. Проигрывает тот, кто не может сделать ход.
В единственной строке записано целое число 1 ≤ n ≤ 109.
В единственной строке выведите “YES” (без кавычек), если первый игрок побеждает в игре со стартовым числом n при оптимальной стратегии обоих игроков. В противном случае выведите “NO” (без кавычек).
1
NO
8
YES
Петя с двумя друзьями писал контест. Но тут его сокомандники отказались писать задачу, потому что она сложная. Расстроенный Петя раскатал первого из друзей в полоску, состоящую из 2 на n одинаковых квадратных клеточек, а второго разрезал на k уголков по три клеточки каждый. Теперь он интересуется вопросом: а сколько способов разместить эти уголки на полоске так, чтобы они не пересекались (то есть, чтобы ни одна клетка полосы не была покрыта более чем одним уголком). Петя не может отличить один уголок от другого, так что расстановки, отличающиеся только порядком уголков следует считать одинаковыми. Так как число способов может быть большим, а Петя добрый мальчик, ответ нужно вывести по модулю 109 + 7.
Два натуральных числа n и k через пробел, 1 ≤ n ≤ 5000, 1 ≤ k ≤ 109.
Выведите единственное число – ответ на задачу.
2 1
4
2 2
0
3 2
2
10 4
5820
Маша попала в уборную в торговом центре и решила поиграть с умывальниками. Умывальники расположены в ряд, в каждом из них либо течет вода, либо не течёт. За один раз Маша выбирает несколько подряд стоящих умывальников, открывает краны там, где вода не текла и закрывает там, где вода текла. Маше показалось скучным менять состояния всех подряд идущих умывальников, поэтому каждый раз она меняет состояния либо всех чётных, либо всех нечетных умывальников на подотрезке. Ваша задача – определить состояния всех умывальников после того, как Маша закончит играть.
В первой строке через пробел даны два целых числа n и m – количество умывальников и количество запросов, 1 ≤ n, m ≤ 2·105.
В следующих m строках даны описания запросов. В i-й строке даны три целых числа a, b и c, где [a, b] – подотрезок на котором Маша будет менять состояние умывальников (1 ≤ a, b ≤ n), а c – четность умывальников (c = 0 или 1). Если c = 0, значит Маша меняет состояние всех чётных умывальников, а если c = 1 – всех нечетных. Четность умывальника определяется от начала всего массива. Первый умывальник нечётный, второй – чётный и так далее. Изначально, во всех умывальниках вода не течет.
Выведите через пробел состояния всех умывальников после того, как Маша закончит играть.
3 3
1 3 1
1 1 0
1 1 1
0 0 1
Как то раз группа студентов МИСиС решила приехать в институт на велосипедах. Но у них возникла проблема. Цепь для крепления велосипеда была только у одного из студентов. Цепь была достаточно длинной и ею можно было пристегнуть все велосипеды, но при условии, что эти велосипеды будут стоять на подряд идущих местах парковки. Староста группы уже приехал в институт на автобусе и прислал ребятам расстановку уже занятых на парковке мест. Помогите ребятам понять какое максимальное количество велосипедов они смогут расположить на парковке так, чтобы их можно было пристегнуть одной цепью.
В первой строке дано целое число 1 ≤ n ≤ 100 – количество мест на парковке.
Во второй строке даны n целых чисел через пробел равных 0 или 1. Число 0 означает, что соответствующее место свободно, а 1 означает, что соответствующее место занято.
Выведите единственное число – ответ на задачу.
5
0 0 0 0 0
5
7
1 0 0 1 0 1 0
2
Шел 2567 год. Глобальное потепление привело к таянию полярного льда и практически вся поверхность Земли оказалась затоплена. Однако человечество не погибло. Ученые изобрели новые способы строительства городов.
Здания представляют собой высокие каменные столбы, частично погруженные в воду. Некоторые здания соединены друг с другом мостом, который расположен на определенной высоте. Мост соединяет здания в двух направлениях. Первый этаж каждого здания находится на уровне воды. Каждое здание включает в себя этажи с 1 по 109. Заметим, что два здания могут быть соединены двумя и более мостами, которые расположены на разных высотах. Два здания, например, могут быть соединены тремя мостами, которые расположены на высотах 7, 119 и 4432.
Однако жители города обеспокоены тем, что уровень воды продолжает подниматься. Они хотят знать, при каком максимальном уровне воды можно добраться от жилого дома A до центра эвакуации B.
Ваша задача – ответить на вопрос жителей. Заметим, что если вода находится на уровне некоторого моста, то по нему все еще можно перемещаться.
В первой строке через пробел даны два целых числа 2 ≤ n ≤ 5·105, 0 ≤ m ≤ 5·105 – количество зданий и мостов.
В следующих m строках через пробел даны по три целых числа a, b, c, которые задают описание мостов. Первые два числа это номера зданий, которые соединяет мост, 1 ≤ a, b ≤ n, a ≠ b. Третье число – высота, на которой расположен мост 1 ≤ c ≤ 109.
В последней строке через пробел даны два числа A и B – номер жилого дома и номер центра эвакуации, 1 ≤ A, B ≤ n, A ≠ B.
Выведите одно число – ответ на вопрос задачи. Если проехать от жилого дома до центра эвакуации нельзя вовсе, выведите - 1.
6 8
1 2 3
1 3 2
1 4 4
1 6 5
2 3 15
3 6 8
3 5 7
4 5 1
1 5
5
Вам даны два числа n и k. Назовем подмножество A множества {1, ..., n} хорошим, если любые два различные элемента A различаются не менее, чем на k. Найдите количество хороших множеств максимальной мощности. Так как ответ может быть достаточно большим, выведите его по модулю 109 + 7.
В первой строке дано целое число T – количество тестов, 1 ≤ T ≤ 105.
В следующих T строках через пробел даны по два целых числа 1 ≤ n ≤ 105 и 1 ≤ k ≤ 109.
Для каждого теста в отдельной строке выведите одно целое число – искомое количество множеств по модулю 109 + 7.
4
10 4
10 1
10 10
4 3
4
1
10
1
Маленький Леша очень любит рисовать домики. Он готов часами рисовать домики разных форм и размеров. Как-то раз Леша попал на одну Очень Серьезную Олимпиаду. Чтобы справиться с волнением, он решил прибегнуть к любимому занятию и нарисовать много-много домиков.
Леша считает, что множество из шести отрезков образует домик, если можно выбрать три из них так, что они образуют равнобедренный треугольник, а из оставшихся трех отрезков и основания треугольника можно составить прямоугольник (смотри рисунок).
У Леши в запасе есть множество отрезков, пронумерованных от 1 до n. Лешу очень интересует, сколькими способами можно выбрать шесть отрезков из множества таким образом, чтобы из них можно было составить домик. Две шестерки отрезков считаются различными, если в одной из шестерок найдется отрезок, которого нет в другой шестерке.
В первой строке дано целое число n (6 ≤ n ≤ 105) – количество отрезков.
Во второй строке даны n целых чисел ai через пробел – длины отрезков (1 ≤ ai ≤ 109).
Выведите единственное число – ответ на задачу. Так как Леша еще маленький и боится больших чисел, ответ нужно вывести по модулю 109 + 9.
6
1 1 1 1 1 1
1
7
1 1 1 1 1 2 2
5
Быстро летит время год за годом. И снова, как и каждый год, профессор МИСиСа задал группе студентов подготовить курсовую работу на тему: "Расчет воздухонагревателя доменной печи". В назначенный день и час все студенты принесли курсовые работы и дружно скопировали их на компьютер профессора.
Профессору стало интересно: а какова вероятность того, что студенты списали работы друг у друга? Для того чтобы это проверить, он решил просто сравнить названия папок и файлов в своей файловой системе. Файловая система профессора представляет из себя корневое дерево (то есть дерево с выделенным корнем), на каждой вершине которого написано некоторое целое число (название). Более того, как и в обычной файловой системе, внутри папки не может содержаться двух файлов (папок) с одинаковыми названиями.
Профессор считает, что каждая пара изоморфных корневых поддеревьев в его файловой системе является кандидатом на списанные курсовые. Для начала ему интересно посчитать, сколько таких пар существует. Помогите ему в этом.
Напомним, что корневое поддерево состоит из заданной вершины-корня и всех ее потомков.
Два корневых поддерева являются изоморфными, если каждой вершине первого поддерева можно однозначно поставить в соответствие ровно одну вершину второго поддерева таким образом, чтобы:
(a) каждая вершина второго поддерева соответствовала ровно одной вершине первого поддерева, причем с тем же самым значением;
(б) корень первого поддерева соответствовал корню второго поддерева;
(в) две вершины первого поддерева были соединены ребром тогда и только тогда, когда ребром соединены соответствующие вершины второго поддерева.
В первой строке дано целое число n – количество вершин в дереве, 2 ≤ n ≤ 105.
В следующих (n - 1) строках через пробел даны по два целых числа ui и vi – номера вершин, которые соединяет i-тое ребро дерева, 1 ≤ ui, vi ≤ n, ui ≠ vi, 1 ≤ i ≤ n.
В последней строке через пробел даны n целых чисел ci – значения вершин дерева, 1 ≤ ci ≤ 109, 1 ≤ i ≤ n.
Корень дерева находится в вершине номер 1.
Выведите единственное число – количество пар изоморфных корневых поддеревьев.
4
1 2
1 3
3 4
1 2 3 2
1
6
1 2
1 3
1 4
3 5
4 6
1 2 3 4 2 2
3