Дни рождения Пети и Васи совпадают. Вероятно, поэтому им подарили по коробке одинаковых конфет. Но друзьям слишком скучно просто съесть эти конфеты, поэтому они решили сделать их призом для игры.
За один ход игроку разрешается извлечь из любой коробки такое число конфет, чтобы в ней осталось конфет меньше, чем в другой коробке. Пусть после хода в коробках осталось N и M конфет (N > M). Тогда число N - M должно быть неотрицательной степенью i числа P, другими словами N - M = Pi, i ≥ 0. При этом целая часть от деления N на разность N - M не должна быть кратна P, или [N / (N - M)] mod P ≠ 0.
Поскольку родители очень любят своих детей, количество конфет в каждой из коробок может оказаться довольно большим и игра таким образом затянется. В связи с этим ребята хотели бы знать, является ли изначальная конфигурация конфет (X конфет в коробке Пети и Y в коробке Васи) выигрышной для игрока, который будет делать первый ход. Напомним, что ситуация является выигрышной, если из нее возможно перевести игру в хотя бы одну проигрышную позицию, и ситуация является проигрышной, если из нее невозможно перевести игру в другую проигрышную позицию.
Игрок считается проигравшим, если он не может сделать следующий ход.
Определите выигрышность начальной ситуации в игре.
Единственная строка содержит три положительных целых числа P, X, Y — число, степенью которого должна быть разность, количество конфет в коробках Пети и Васи, соответственно (2 ≤ P, X, Y ≤ 1018).
В первой строке требуется вывести сообщение «NO», если позиция является проигрышной и «YES», если выигрышной.
В случае выигрышной позиции требуется вывести любую следующую за этой игровую позицию, которая является проигрышной.
2 3 5
NO
3 3 3
YES
3 0
Национальный заповедник государства Q недавно обзавелся прекрасной березовой аллеей, которая состоит из N деревьев. Каждое из деревьев имеет высоту Hi.
Международный классификатор национальных парков составляет список самых красивых заповедников мира. Для ранжирования парков используется такое понятие как «отличительность» под которой понимается количество таких пар (i, j), для которых соблюдается соотношение Hi mod Hj = K, где K — это специальное число, которое выбирается экспертным советом международной организации национальных парков.
Какой же «отличительностью» обладает национальный парк государства Q?
В первой строке располагается два целых положительных числа N и K — количество деревьев в национальном парке и специальное число экспертного совета соответственно (1 ≤ N ≤ 105, 0 ≤ K ≤ 106).
Во второй строке располагается N чисел Hi — высоты каждого из деревьев в парке (1 ≤ Hi ≤ 105).
В единственной строке выведите «привлекательность» национального парка страны Q.
5 1
1 2 3 4 5
8
Во время раскопок в одной из пещер были обнаружены старинные надписи. Каждая из найденных записей представляла собой некоторое число N и правильную скобочную последовательность (ПСП).
Напомним, что ПСП может быть определена так:
По некоторым из записей археологи поняли, что первое число обозначает количество подстрок в ПСП, которые также являются ПСП. Это навело археологов на мысль, что если они восстановят оставшиеся надписи, то им будет доступно какое-то тайное знание. Поскольку на стенах пещеры в основном обнаружены числа, то они считают, что восстановление отсутствующих ПСП возможно. Также ученые узнали, что длина каждой из ПСП не должна превышать 105 символов, поскольку может не поместиться на стену в пещере.
Соответственно, теперь им необходимо построить такую ПСП, которая содержит в себе ровно N подстрок, которые также являются ПСП.
В единственной строке расположено целое положительное число N — количество подстрок в ПСП, которые также являются ПСП (1 ≤ N ≤ 109).
ПСП, которая содержит в себе ровно N подстрок, являющихся ПСП. Длина выводимой строки не должна превышать 105 символов.
2
(())
В настоящее время приобрели популярность интерактивные кодовые замки. Для того, чтобы протестировать сообразительность своих сотрудников, такой замок установили на дверь в офисе. Теперь работники в панике пытаются открыть его, но ничего не выходит.
Кодовый замок состоит из T секций, содержащих целые числа Xi (102 ≤ Xi ≤ 104), для каждого из которых необходимо отгадать делитель (кроме единицы) следующим образом:
После вычитания отгадываемое число должно оставаться положительным, а также нельзя называть один и тот же делитель для текущего отгадываемого числа более одного раза. В случае соблюдения всех ограничений и удачного отгадывания хотя бы одного делителя для каждого из чисел дверь будет открыта.
Сотрудники бились над этой задачей в течение всего дня. Теперь им нужен тот, кто мог бы помочь им открыть дверь. Способны ли Вы на это?
В первой строке задается чисел T — количество чисел в кодовом замке (1 ≤ T ≤ 500).
Далее в качестве ответов на попытки угадать делитель необходимо считывать сообщения «YES» или «NO». Такое сообщение будет приходить после каждой попытки угадывания.
После каждой попытки угадать не забывайте выводить символ новой строки и делать flush-операцию (сброс буфера, например, fflush(stdout) в С++, System.out.flush() в Java, и flush(output) в Pascal).
В случае если Вы нарушите какие-либо ограничения протокола общения с интерактором, Ваша программа будет завершена автоматически.
Необходимо выводить предполагаемые делители для каждого из чисел кодового замка. Таких попыток может быть несколько для каждого числа в зависимости от успешности отгадывания делителя.
3
YES
NO
YES
YES
2
2
3
2
В тесте приведен пример корректной работы для кодового замка, состоящий из трех секций с числами 100, 101 и 102.
Петя с детства обожает головоломки. В связи с этим он посещает в школе кружок любителей интересных математических задач.
Одно из последних занятий кружка было посвящено делителям натуральных чисел. Пете оказалось мало того, что было рассмотрено на занятии, поэтому он решил придумать что-нибудь поинтереснее.
Назовем «делительностью» целого положительного числа N количество его делителей и обозначим эту функцию как D(N). Например, для числа 12 «делительность» равна 6.
Теперь для промежутка целых положительных чисел от L до R Петя пытается научиться вычислять такую сумму 
, которую Петя назвал «интервальной делительностью».
Теперь Пете хотелось бы разработать программу, которая позволяет считать «интервальную делительность» для произвольного интервала. Помогите ему в этом.
В первой строке входных данных располагается два целых положительных числа L и R — границы интервала, для которого необходимо найти «интервальную делительность» (1 ≤ L ≤ R ≤ 1012).
В единственной строке выведите единственное число — искомую «интервальную делительность» для заданного интервала по модулю 109 + 7.
7 16
429
В новом сезоне цирка «Печальный клоун» публику решили развлечь математическим фокусом. Самым опытным работником цирка является фокусник Георгий. Ему и доверили честь показывать этот фокус.
Суть фокуса состоит в том, что Георгий выбирает из зала случайного зрителя и просит его назвать случайное число N. Далее фокусник думает в течение ровно 5,674 секунды и говорит некоторое число M отличное от N. Особенностью этих двух чисел является то, что они имеют одинаковую сумму цифр.
Как только Георгию это удается?
Единственная строка содержит целое неотрицательное число N — число, названное зрителем (0 ≤ N ≤ 109). Гарантируется, что в записи числа N нет лидирующих нулей.
В единственной строке необходимо вывести целое неотрицательное число M — число, названное фокусником. Если существует несколько подходящих чисел, то выведите любое из них.
Число M не должно содержать лидирующих нулей и при этом не должно превышать 109.
Если фокусник не может назвать число, то необходимо вывести -1.
24
42
Градоначальник города Q недавно получил от руководства письмо о важности повышения рейтинга городов страны в связи с предстоящим годом «высоких рейтингов». На первом этапе необходимо выслать рейтинг города, вычисленный по новой методике, в столицу государства.
Мэр поручил аналитическому отделу рассчитать этот рейтинг.
В городе Q расположено N памятников архитектуры, которые пронумерованы от 1 до N и между собой связаны автобусными маршрутами. Известно, что таких маршрутов ровно N - 1 и они позволяют туристу проложить путь между любой парой памятников (возможно, с пересадками). Назовем «привлекательностью» пути от памятника A до памятника B функцию F(A, B) = D, где D – количество оплаченных автобусных маршрутов, необходимых для того, чтобы добраться от A до B.
Для привлечения большего числа туристов и, соответственно, повышения рейтинга мэр издал указ о том, что каждый второй маршрут на пути от некоторого памятника A до некоторого памятника B является бесплатным.
Вам необходимо вычислить рейтинг города, который определяется как сумма «привлекательностей» путей между всеми парами памятников архитектуры.
В первой строке располагается целое положительное число N — количество памятников архитектуры в городе Q (1 ≤ N ≤ 105). Далее в N - 1 строках раполагается по два числа Ai и Bi — номера памятников, между которыми проложен автобусный маршрут (1 ≤ Ai, Bi ≤ N, Ai ≠ Bi).
В единственной строке выведите единственное число — привлекательность города Q.
3
1 2
1 3
3
8
1 3
8 1
4 3
5 2
3 6
7 6
5 6
42
Волшебнику Ринсвинду известно всего лишь одно заклинание. И как бы он не старался изучить ещё, у него никак не получалось: новые заклинания не хотели оседать у него в голове и забывались спустя 3+5 секунд после запоминания. Поэтому он должен попробовать научиться получать новые заклинания из того, которое ему известно. Поскольку известное ему заклинание является достаточно могущественным, эта затея может оказаться удачной.
Заклинание можно представить как строку S, состоящую из строчных латинских символов. Для конструирования новых заклинаний Ринсвинд может поменять местами два соседних символа. Для того, чтобы заклинание не утратило свою силу есть одно ограничения: нельзя менять местами символы в позициях i и i + 1, если до этого уже меняли местами символы в позициях j и j + 1 и позиция j находится правее i, т.е. j > i. Например, он может из abc cконструировать abc, acb, bac и bca, но не может cab и cba.
Заклинание может быть достаточно длинным, поэтому оно описывается несколькими блоками. Каждый блок представляет из себя строку и число, обозначающего количество повторений этой строки.
Ринсвинд сейчас занят тренировкой произношения, но ему очень интересно, каким потенциальным количеством заклинаний он может владеть отточив технику конструирования до совершенства. Помогите ему посчитать это количество. Напомним, что Ринсвинд не может запоминать новые заклинания, поэтому конструировать заклинания он может только из исходного.
В первой строке задается число N — количество блоков, из которых состоит заклинание известное Ринсвинду (1 ≤ N ≤ 100).
В следующих N строках задаются блоки заклинания в порядке их следования в нём Si Ki — строка и количество раз, которое её требуется повторить соответственно (1 ≤ |Si| ≤ 104, 1 ≤ Ki ≤ 106).
В единственной строке выведите количество потенциальных заклинаний, которое может произнести Ринсвинд, по модулю 109 + 7.
3
a 1
ng 2
an 1
42
Довольно немногие знают, что в старые времена для борьбы с нечистой силой (ведьмами, вампирами, оборотнями и др.) помимо широко известных серебряных пуль использовались также и серебряные таблицы. Принцип использования таких таблиц прост: если Вы ходите защититься от N существ, то Вам необходимо высечь у себя на двери таблицу размера 2N × 2N, заполненную целыми числами из множества S = {1, 2, ..., 2N + 1 - 1}.
Но, естественно, не любая таблица считается серебряной. Для того, чтобы наверняка защитить Вас от N единиц нечисти таблица должна обладать специальным свойством: для каждого числа i от 1 до 2N множество, образуемое строкой номер i, и множество, образуемое столбцом номер i, в объединении должны давать множество S.
В последнее время все меньше уверенности в том, что вампиров и ведьм не существует. Поэтому уметь составить серебряную таблицу для произвольного N в Ваших же интересах :)
В единственной строке раполагается целое положительное число N (1 ≤ N ≤ 10) — количество существ, от которых Вас защитит серебряная таблица размером 2N × 2N.
Выведите 2N строк по 2N чисел, каждое из которых должно принадлежать множеству S и полученная в результате таблица должна быть серебряной.
1
1 3
2 1
В одной из воинских частей республики Y солдаты ежедневно тренируют построение в одну шеренгу. После нескольких месяцев упорных тренировок солдаты могут выполнять это упражнение достаточно хорошо. А нужно идеально.
Представим каждого из N солдат части в виде материальной точки с координатами (Xi, Yi). Задача состоит в том, чтобы солдаты смогли построиться в шеренгу (прямую линию) таким образом, чтобы максимальное Евклидово расстояние, на которое перемешается один из солдат, было минимально возможным.
Как известно, в армии нет ничего невозможного. Однако солдатам так и не удалось для любого своего расположения находить наименьшее расстояние и строиться вдоль прямой линии. Поэтому требуется решить поставленную начальником части задачу.
В первой строке располагается целое положительное число N — количество солдат в воинской части (2 ≤ N ≤ 1000).
Далее в N строках располагается по два числа целых числа Xi и Yi — координаты каждого из солдат ( - 1000 ≤ Xi, Yi ≤ 1000). Изначально все солдаты стоят в разных точках. Приказ есть приказ и поэтому после перепостроения несколько солдат могут стоять в одной точке.
В первой строке необходимо вывести минимальное искомое расстояние, которое достаточно пройти солдату, чтобы стать на свою позицию в шеренге. Ответ считается правильным, если его абсолютная или относительная погрешность не превышает 10 - 6.
Далее в N строках необходимо вывести по два числа — координаты точек, в которые переместятся солдаты после перемещения.
Расстояние от каждой из точек до построенной шеренги (прямой линии) не должно превышать 10 - 6. Прямая линия будет строиться по двум крайним солдатам в шеренге.
5
1 1
0 2
-1 -1
1 -2
-1 1
1.00000000
0.00000000 1.00000000
0.00000000 2.00000000
0.00000000 -1.00000000
0.00000000 -2.00000000
0.00000000 1.00000000
В одном из всемирно известных казино разработали новую карточную игру. Вам, конечно, хотелось бы побывать на премьере этой игры, которая состоится в ближайшее время. Однако, поскольку Вы основательный человек, Вы решили детально ознакомиться с правилами игры и разработать стратегию с наибольшим возможным выигрышем.
Для игры необходима колода, состоящая из N красных и M черных карт, которая изначально перемешивается случайным образом. Каждый раунд игрок случайно выбирает в закрытую одну карту. Если игрок вытянул красную карту, то к его выигрышу прибавляется 1 млн. бел. руб., в противном случае, из его выигрыша вычитается 1 млн. бел. руб. Вытянутая карта в колоду обратно не возвращается. Игрок может в любой момент остановиться и забрать свой выигрыш (в том числе и заплатить, если он отрицательный).
Чтобы оценить целесообразность участия в этой игре Вам необходимо вычислить математическое ожидание выигрыша при условии, что игрок стремится максимизировать сумму своего выигрыша.
В единственной строке располагается два целых положительных числа N и M — количество красных и черных карт в колоде, соответственно (0 ≤ N, M ≤ 100).
В единственной строке необходимо вывести математическое ожидание выигрыша. Ответ необходимо вывести в миллионах белорусских рублей. Ответ считается правильным если его абсолютная или относительная погрешность не превышает 10 - 6.
1 1
0.500000000
1 2
0.000000000