Финальный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"A" Теория множеств
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Маша и Гриша очень любят изучать свойства множеств натуральных чисел.

В некоторый момент Гриша выписал на доске множество 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).

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

Для каждого теста в отдельной строке сначала выведите ответ на него:

  • NO, если не существует ни одного способа построить множество B, чтобы выполнить условие задачи.
  • YES, если способ решить задачу есть. В этом случае в следующей строке выведите n различных целых положительных чисел bj — элементы множества B (1 ≤ bj ≤ 106). Если подходящих ответов несколько, выведите любой из них.

Примеры
Входные данные
3
3
1 10 100
1
1
2
2 4
Выходные данные
YES
1 2 3 
YES
1 
YES
1 2 
"B" Похожие слова
Ограничение по времени 4 секунды
Ограничение по памяти 512 мегабайт

Назовем словом непустую последовательность, состоящую из строчных букв латинского алфавита. Префиксом слова x называется слово y, которое можно получить из x удалением нуля или более последних букв x.

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

Дано множество слов S. Требуется найти размер максимального множества непустых слов 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
"C" Одиннадцатилетие
Ограничение по времени 4 секунды
Ограничение по памяти 512 мегабайт

На одиннадцатый день рождения Боре подарили 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
"D" Кактусомания
Ограничение по времени 4 секунды
Ограничение по памяти 256 мегабайт

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

Напомним, что дерево — это неориентированный связный граф, в котором нет циклов. А кактус — это неориентированный связный граф, через каждую вершину которого проходит не более одного простого цикла.

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

Помогите Маше выяснить, какую максимальную красоту итогового кактуса Маша может получить.

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

В первой строке записаны два целых числа 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
"E" Спутники
Ограничение по времени 4 секунды
Ограничение по памяти 256 мегабайт

Real Cosmic Communications — самая крупная телекоммуникационная компания на далёкой планете на самом краю Вселенной. Основное направление деятельности RCC — запуск спутников связи.

Поскольку планета находится на краю Вселенной, она имеет форму полукруга. Его радиус равен r, концы диаметра — A и B. Прямая AB — это край Вселенной, поэтому в нижней полуплоскости нет ни планеты, ни спутников компании RCC, ни чего бы то ни было ещё. Введём систему координат следующим образом: начало отсчёта — в середине отрезка AB, ось OX совпадает с прямой AB, планета лежит в полуплоскости y > 0.

Спутник связи может находиться в любой точке Вселенной, кроме точек планеты. Спутник не находится за краем вселенной или на ее границе, то есть имеет координату y > 0. Антенны спутника направлены таким образом, что для связи ему доступен угол с вершиной в спутнике и сторонами, которые проходят через точки A и B. Будем называть эту область зоной покрытия спутника. Границы этой области тоже принадлежат зоне покрытия.

На рисунке показана система координат и зона покрытия одного спутника.

В момент основания RCC около планеты не было ни одного их спутника. С тех пор происходили события следующих типов:

  1. 1 x y — запустить новый спутник и поместить его в точку с координатами (x, y). Спутники компании RCC никуда не двигаются и остаются на месте, пока их не уберут. Спутник, запущенный i-м, получает номер i, нумерация с единицы.
  2. 2 i — убрать спутник номер i.
  3. 3 i j — попытаться установить связь между спутниками i и j. Для этого необходимо установить ретранслятор. Он не может располагаться внутри планеты, но может быть на поверхности или висеть над ней. Ретранслятор должен находиться в зоне покрытия спутников i и j. Кроме того, чтобы не создавать помех, он не должен находиться в зоне покрытия никакого другого спутника. Разумеется, ретранслятор должен находиться внутри вселенной, то есть иметь координату y > 0.

Для каждой попытки установить связь требуется определить, возможно ли это сделать.

В примере входных данных расположение спутников следующее:

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

В первой строке входных данных заданы целые числа 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
"F" Играть или не играть
Ограничение по времени 4 секунды
Ограничение по памяти 256 мегабайт

Вася и Петя играют в онлайн-игру. Как и во многих онлайн-играх, в этой есть своя схема прокачки, которая заключается в том, что чем больше опыта получил персонаж, тем он сильнее. Конечно, Вася хочет как можно быстрее получить максимальное количество опыта. Внимательно изучив правила игры, Вася понял, что если человек играет в игру один, то он получает одну единицу опыта каждую секунду, пока играет. Но если два игрока играют в одно время, и их текущий опыт отличается не больше, чем на число 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

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.