Илья увлекается математикой. Недавно он прочитал про вампирские числа. Они настолько восхитили Илью, что теперь он постоянно придумывает задачи, связанные с этими числами, и пытается их решить.
Число \(a\), десятичная запись которого состоит из \(n\) цифр (\(n\) четно), называется вампирским, если его можно представить в виде
произведения двух
\(n/2\)-значных чисел \(b\) и \(c\), причем используя все цифры \(b\) и \(c\)
можно записать число \(a\). Каждую цифру при этом разрешается использовать столько раз, сколько
раз она суммарно встречается в \(b\) и в \(c\).
Числа \(b\) и \(c\) называются клыками числа \(a\).
Например, число \(6880\) - вампирское, так как \(6880 = 80 \times 86\), а число \(1023\) - нет.
Для его новой задачи Илья попросил вас найти \(k\) различных вампирских чисел, состоящих из \(n\) цифр.
В единственной строке входного даны два числа \(k\) и \(n\) - требуемое количество вампирских чисел и количество цифр в каждом из них соответственно (\(1 \le k \le 100\), \(4 \le n \le 100\), \(n\) - четно).
В выходной файл выведите \(k\) различных \(n\)-значных вампирских числа в формате \(A_i\)=\(B_{i}\)x\(C_{i}\), где \(A_i\) - \(i\)-е из найденных вампирских чисел, \(B_i\) и \(C_i\) - его клыки (между \(B_i\) и \(C_i\) следует вывести маленькую латинскую букву «x»).
Если ответов несколько, то разрешается вывести любой из них. Гарантируется, что для приведенных во входном файле \(n\) и \(k\) существует \(k\) различных \(n\)-значных вампирских чисел.
1 6
139500=150x930
Олег очень любит двоичные последовательности - последовательности из нулей и единиц. Совсем недавно он написал в тетради очередную двоичную последовательность из \(n\) элементов. Для выписанной последовательности Олег посчитал Z-функцию.
Z-функцией последовательности \(s_1, \ldots, s_n\) называется массив \(z[1..n]\), в котором:
Записав в тетради последовательность и ее Z-функцию, Олег лег спать. Пока он спал, его младший брат Егор прокрался в комнату и закрасил фломастером последовательность и некоторые значения Z-функции. Проснувшись, Олег заинтересовался, сколько различных двоичных последовательностей он мог вечером написать в тетради, чтобы незакрашенные значения Z-функции были правильными.
Найдите число искомых последовательностей и выведите его по модулю \(10^9 + 7\). Заметьте, что Олег мог и ошибиться при вычислении Z-функции, в этом случае ни одна последовательность не подходит и ответ равен 0.
В первой строке входного файла находится целое число \(n\) - длина исходной двоичной последовательности (\(1 \le n \le 1000\)). Во второй строке входного файла находятся \(n\) целых чисел \(z[1], \ldots, z[n]\), где \(z[i]\) - значение Z-функции в позиции \(i\), или \(-1\), если значение в \(i\)-й позиции было закрашено (\(-1 \le z[i] \le n\)).
В выходной файл выведите единственное число - остаток от деления числа подходящих двоичных последовательностей на число \(10^9 + 7\).
В первом примере подходят последовательности \(\langle 0, 1, 0 \rangle\) и \(\langle 1, 0, 1 \rangle\).
Во втором примере не существует ни одной двоичной последовательности длины 4 с заданной Z-функцией.
В третьем примере \(z[2] = 3\), что противоречит определению Z-функции, поэтому ответ 0.
В четвертом примере подходит любая двоичная последовательность длины 3.
3 0 0 1
2
4 0 0 1 0
0
3 0 3 -1
0
3 -1 -1 -1
8
В центре города Че есть пешеходная улица - одно из самых популярных мест для прогулок жителей города. По этой улице очень приятно гулять, ведь вдоль улицы расположено \(n\) забавных памятников.
Девочке Маше из города Че нравятся два мальчика из ее школы, и она никак не может сделать выбор между ними. Чтобы принять окончательное решение, она решила назначить обоим мальчикам свидание в одно и то же время. Маша хочет выбрать два памятника на пешеходной улице, около которых мальчики будут ее ждать. При этом она хочет выбрать такие памятники, чтобы мальчики не увидели друг друга. Маша знает, что из-за тумана мальчики увидят друг друга только в том случае, если они будут на расстоянии не более \(r\) метров.
Маше заинтересовалась, а сколько способов есть выбрать два различных памятника для организации свиданий.
В первой строке входного файла находятся два целых числа \(n\) и \(r\) (\(2 \le n \le 300\,000\), \(1 \le r \le 10^9\)) - количество памятников и максимальное расстояние, на котором мальчики могут увидеть друг друга.
Во второй строке задано \(n\) положительных чисел \(d_1, \ldots, d_n\), где \(d_i\) - расстояние от \(i\)-го памятника до начала улицы. Все памятники находятся на разном расстоянии от начала улицы. Памятники приведены в порядке возрастания расстояния от начала улицы (\(1 \le d_1 < d_2 < \ldots < d_n \le 10^9\)).
Выведите одно число - число способов выбрать два памятника для организации свиданий.
В приведенном примере Маша может выбрать памятники под номерами 1 и 4 или памятники 2 и 4.
4 4 1 3 5 8
2
Гномы продолжают искать золото предков в недрах Одинокой горы. Недра Одинокой горы представляют собой \(n\) пещер, некоторые из которых соединены двусторонними переходами. При этом из каждой пещеры в любую другую можно попасть по переходам, причем это можно сделать единственным способом.
Гномы разделились на два отряда, которые начали свои поиски с пещер \(u_0\) и \(v_0\), соответственно. Гномы каждого из отрядов перемещаются вместе. На обследование пещеры у отряда гномов уходит ровно одна минута, после чего каждый отряд быстро перемещается по переходу в одну из соседних пещер. При этом гномы никогда не заходят в пещеру, если они или другой отряд в ней уже побывали. Оба отряда никогда не заходят в одну и ту же пещеру. Если хотя бы один из отрядов гномов не может переместиться в соответствии с этими правилами, оба отряда сразу прекращают поиски сокровищ.
Чтобы как можно лучше обследовать недра Одинокой горы, гномы хотят, чтобы поиски продолжались как можно дольше. По заданной карте пещер в Одинокой горе и начальному положению отрядов гномов определите, какое максимальное время могут продолжаться поиски сокровищ.
В первой строке число \(n\) (\(2 \le n \le 200\,000\)) - число пещер в Одинокой горе.
В следующих \(n - 1\) строках заданы переходы между пещерами. В каждой строке записаны номера двух пещер \(v\) и \(u\), соединенных переходом
(\(1 \le v, u \le n\)).
В следующей строке заданы номера пещер \(v_0\) и \(u_0\), в которых исходно находятся два отряда гномов (\(1 \le v_0, u_0 \le n\), \(v_0 \ne u_0\)).
Выведите максимальное число минут, которое могут продолжаться поиски сокровищ.
6 1 2 2 3 3 4 4 5 5 6 4 5
2
8 1 2 2 3 3 4 2 5 5 6 3 7 7 8 1 8
4
Том Сойер уговорил \(n\) своих друзей помочь ему в нелегком деле покраски забора, окружающего дом тетушки Полли. Забор представляет собой \(k\) последовательных досок, пронумерованных от 1 до \(k\), причем после \(k\)-й доски опять идет первая.
Друзья Тома очень привередливы, \(i\)-й друг согласен участвовать в покраске только в том случае, если ему дадут покрасить участок из ровно \(a_i\) последовательных досок.
Кисточка у Тома только одна, поэтому друзья будут красить по очереди и сразу весь отведенный им отрезок. Тому остается лишь выбрать порядок, в котором приглашать друзей, а также выбрать для каждого желаемое количество последовательных досок.
При этом каждый из друзей Тома готов красить как еще неокрашенную доску забора, так и доску, которую уже покрасил один из его предшественников. Тем не менее, друзья получают больше удовольствия от покраски неокрашенной доски. Том хочет выбрать число \(x\) и распределить отрезки забора для покраски таким образом, чтобы каждый из его друзей покрасил хотя бы \(x\) неокрашенных досок. Том очень любит своих друзей и хочет, чтобы каждый из них получил от процесса покраски забора максимальное удовольствие, поэтому он пытается максимизировать \(x\).
Помогите Тому понять, сколько радости он сможет доставить своим друзьям.
Первая строка входного файла содержит два целых числа \(n\) (\(1 \le n \le 10^5\)) и \(k\) (\(1 \le k \le 10^9\)). Следующая строка содержит \(n\) целых чисел - значения \(a_i\) (\(1 \le a_i \le k\)).
Выведите одно число - максимальное возможное значение \(x\).
В первом примере \(x = 5\), так как один из друзей просто не хочет красить больше пяти досок. Он придет первым, покрасит свои пять, после чего еще 10 неокрашенных досок достанется второму другу Тома. Оставшиеся 85 досок Тому придется красить самому.
Во втором примере достичь \(x = 2\) можно, например, так. Сначала третий друг красит доски с 4 по 6 (3 неокрашенных доски). Затем четвертый друг красит доски с 1 по 5 (3 неокрашенных доски). Затем второй друг красит доски с 1 по 8 (2 неокрашенных доски). Наконец, первый друг красит доски с 6 по 10 и с 1 по 2 (2 неокрашенных доски, заметим, что забор идет по циклу и эти доски образуют последовательный отрезок).
2 100 5 10
5
4 10 7 8 3 5
2