Маша и Гриша очень любят изучать свойства множеств натуральных чисел.
В некоторый момент Гриша выписал на доске множество A, состоящее из n различных положительных целых чисел ai, и предложил Маше подумать над следующей задачкой: придумать множество B, состящее из n положительных целых чисел bj, такое, что все n2 чисел, которые получаются сложением ai и bj для всех возможных пар i и j — различны. При этом и Гриша и Маша не любят больших чисел, поэтому все числа в множестве A не превышают 106, то же свойство должно выполняться и для чисел из множества B.
Помогите Маше построить искомое множество B.
Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 100).
Каждый из тестов описывается следующим образом: в первой строке описания теста содержатся одно число n — размер множества A (1 ≤ n ≤ 100).
В следующей строке содержатся n чисел ai — числа, принадлежащие множеству A (1 ≤ ai ≤ 106).
Для каждого теста в отдельной строке сначала выведите ответ на него:
3
3
1 10 100
1
1
2
2 4
YES
1 2 3
YES
1
YES
1 2
Назовем словом непустую последовательность, состоящую из строчных букв латинского алфавита. Префиксом слова x называется слово y, которое можно получить из x удалением нуля или более последних букв x.
Назовем два слова похожими, если одно из них можно получить из другого, удалив в нем первую букву.
Дано множество слов S. Требуется найти размер максимального множества непустых слов X, удовлетворяющего следующим условиям:
Входные данные содержат несколько тестов. Первая строка входных данных содержит число t — количество тестов. Далее следуют описания тестов.
Первая строка каждого описания содержит целое число n — количество слов в множестве S (1 ≤ n ≤ 106). В каждой из следующих n строк содержится по одному непустому слову — элементы множества S. Все слова в S различны.
Гарантируется, что суммарная длина всех слов во входных данных не превосходит 106.
Для каждого теста выведите на отдельной строке число m — размер максимального искомого множества X.
2
3
aba
baba
aaab
2
aa
a
6
1
На одиннадцатый день рождения Боре подарили n карточек с числами. На i-й карточке написано число ai. Боря хочет выложить карточки в один ряд так, чтобы получилось одно большое число. Например, если у Бори есть карточки с числами 1, 31 и 12, и он выложит их в этом порядке, он получит число 13112.
В свои 11 он уже знает, что всего существует n! способов вызложить карточки, но сегодня его интересуют только те способы, в результате которых, он получит число, которое делится на одиннадцать. Так, приведенный выше способ подходит, поскольку 13112 = 1192 × 11, а вот если он выложит карточки в последовательности 31, 1, 12, то он получит число 31112, которое не делится на 11, этот способ Боре не подходит. Помогите Боре посчитать количество таких способов.
Даже если на двух карточках написаны одинаковые числа, Боря считает способы, которые отличаются обменом этих двух карточек, различными, например, если у Бори есть две карточки с числом 1, то он может выложить их на стол двумя способами.
Помогите Боре, найдите число подходящих способов выложить карточки. Поскольку это количество может быть слишком большим, требуется вывести остаток от его деления на 998244353.
Входные данные содержат несколько тестов. Первая строка входных данных содержит число t — количество тестов (1 ≤ t ≤ 100). Далее следуют описания тестов.
Каждый тест описывается двумя строками.
Первая из них содержит целое число n (1 ≤ n ≤ 2000) — количество карточек, которое подарили Боре.
Вторая строка содержит n чисел ai (1 ≤ ai ≤ 109) — числа, которые записаны на карточках.
Гарантируется, что суммарное количество карточек во всех тестах одних входных данных не превышает 2000.
Для каждого теста в отдельной строке выведите остаток от деления на 998244353 количества способов выложить карточки таким образом, чтобы получившееся число делилось на 11.
4
2
1 1
3
1 31 12
3
12345 67 84
9
1 2 3 4 5 6 7 8 9
2
2
2
31680
Маша очень любит кактусы. В детстве Маша посадила дерево, и сейчас оно стало достаточно большим. Маша хочет из своего дерева сделать самый красивый кактус.
Напомним, что дерево — это неориентированный связный граф, в котором нет циклов. А кактус — это неориентированный связный граф, через каждую вершину которого проходит не более одного простого цикла.
У Маши есть дополнительные ребра, которые она может добавить к дереву. Для каждого ребра Маша знает, какие вершины оно должно соединять, и красоту этого ребра. Маша может добавить некоторые из этих ребер к дереву, если после их добавления получившийся граф будет кактусом. Красота полученного графа равна сумме всех значений красоты добавленных ребер.
Помогите Маше выяснить, какую максимальную красоту итогового кактуса Маша может получить.
В первой строке записаны два целых числа n и m — число вершин в дереве и число имеющихся у Маши дополнительных ребер, соответственно (3 ≤ n ≤ 2·105; 0 ≤ m ≤ 2·105).
Пусть Машино дерево имеет корень в вершине 1. В следующей строке записано n - 1 целых чисел: p2, p3, ..., pn, где pi — номер родителя вершины i в дереве — первая вершина на пути от вершины i до корня (1 ≤ pi < i).
В следующих m строках задано по три целых числа ui, vi и ci — вершины, которые могут быть соединены дополнительным ребром, которые Маша может добавить к дереву, и красоту этого ребра (1 ≤ ui, vi ≤ n; ui ≠ vi; 1 ≤ ci ≤ 104).
Гарантируется, что ни одно из дополнительных ребер не совпадает с ребром дерева.
Выведите одно целое число — максимально возможную суммарную красоту кактуса, которую Маша может получить.
7 3
1 1 2 2 3 3
4 5 1
6 7 1
2 3 1
2
Real Cosmic Communications — самая крупная телекоммуникационная компания на далёкой планете на самом краю Вселенной. Основное направление деятельности RCC — запуск спутников связи.
Поскольку планета находится на краю Вселенной, она имеет форму полукруга. Его радиус равен r, концы диаметра — A и B. Прямая AB — это край Вселенной, поэтому в нижней полуплоскости нет ни планеты, ни спутников компании RCC, ни чего бы то ни было ещё. Введём систему координат следующим образом: начало отсчёта — в середине отрезка AB, ось OX совпадает с прямой AB, планета лежит в полуплоскости y > 0.
Спутник связи может находиться в любой точке Вселенной, кроме точек планеты. Спутник не находится за краем вселенной или на ее границе, то есть имеет координату y > 0. Антенны спутника направлены таким образом, что для связи ему доступен угол с вершиной в спутнике и сторонами, которые проходят через точки A и B. Будем называть эту область зоной покрытия спутника. Границы этой области тоже принадлежат зоне покрытия.
На рисунке показана система координат и зона покрытия одного спутника.
В момент основания RCC около планеты не было ни одного их спутника. С тех пор происходили события следующих типов:
Для каждой попытки установить связь требуется определить, возможно ли это сделать.
В примере входных данных расположение спутников следующее:
В первой строке входных данных заданы целые числа r и n — радиус планеты и количество событий (1 ≤ r ≤ 109, 1 ≤ n ≤ 5·105).
В следующих n строках заданы события в приведённом выше формате.
Координаты спутников целые и удовлетворяют ограничениям |x| ≤ 109, 0 < y ≤ 109. Два спутника не могут одновременно находиться в одной точке. Расстояние от спутника до центра планеты строго больше r.
Гарантируется, что в событиях типа 2 и 3 спутники, которые в них задействованы, на момент события существуют. В событиях типа 3 выполнено i ≠ j.
Для каждого события типа 3 выведите в отдельной строке «YES», если возможно установить связь, и «NO» в противном случае.
5 8
1 -5 8
1 -4 8
1 -3 8
1 2 7
3 1 3
2 2
3 1 3
3 3 4
NO
YES
YES
Вася и Петя играют в онлайн-игру. Как и во многих онлайн-играх, в этой есть своя схема прокачки, которая заключается в том, что чем больше опыта получил персонаж, тем он сильнее. Конечно, Вася хочет как можно быстрее получить максимальное количество опыта. Внимательно изучив правила игры, Вася понял, что если человек играет в игру один, то он получает одну единицу опыта каждую секунду, пока играет. Но если два игрока играют в одно время, и их текущий опыт отличается не больше, чем на число C, то они могут играть в команде, и тогда каждый из них будет получать по 2 единицы опыта в секунду.
Поскольку Вася и Петя еще учатся в школе, их родители не разрешают им играть круглые сутки, так что у каждого из друзей есть свое расписание: Вася может играть в какие-то промежутки времени [a1;b1], [a2;b2], ..., [an;bn], а Петя в [c1;d1], [c2;d2], ..., [cm;dm] (все промежутки рассчитаны точно в секундах от текущего момента). Наблюдательный Вася, успевающий в математике, заметил, что иногда может быть выгодно не играть, чтобы не сильно оторваться в полученном опыте от своего друга, и, когда он зайдет в сеть, играть вдвоем, получая больше опыта.
Помогите ребятам составить такое расписание для игры, чтобы в итоге Вася получил как можно больше опыта. Сейчас у их персонажей одинаковое количество набранного опыта. Считайте, что Петя готов скооперироваться с Васей и играть тогда, когда тот скажет, чтобы помочь Васе достичь максимального количества опыта.
В первой строке даны три целых числа n, m, C — количество непрерывных отрезков времени, в которые могут играть Вася и Петя, и максимальная допустимая разница опыта для удвоенного получения опыта, соответственно (1 ≤ n, m ≤ 2·105, 0 ≤ C ≤ 1018).
В следующих n строках дано по два числа ai, bi — промежутки времени, в которые может играть Вася (0 ≤ ai < bi ≤ 1018, bi < ai + 1).
В следующих m строках дано по два числа ci, di — промежутки времени, в которые может играть Петя (0 ≤ ci < di ≤ 1018, di < ci + 1).
Выведите одно целое число — максимальное значение полученного опыта, которое может достичь Вася при правильной игре.
2 1 5
1 7
10 20
10 20
25
1 2 5
0 100
20 60
85 90
125