— А что, если сделать задачу про BSUIR Open, где нужно будет искать подстроку BSUIR Open?
— Нет, это сильно просто.
— Действительно!
Вам дана строка s состоящая только из цифр и прописных букв латинского алфавита. Вы можете выбрать некоторые символы из этой строки и из выбранных символов составить новую строку. Определите, сколькими способами вы можете получить строку «BSUIROPEN» (без кавычек). Два способа считаются различными, если найдется такой индекс i, что i-й символ строки был выбран только в одном из способов.
Вам задана единственная строка s (1 ≤ |s| ≤ 1 000) — исходная строка, состоящая только из цифр и строчных букв латинского алфавита.
Выведите единственное число — количество способов получить строку «BSUIROPEN». Так как ответ может быть слишком большим, выведите его по модулю 109 + 7.
BSUIROPEN2018
1
BOSOQIVBONEOMOPTURSOCOS
42
Вы работаете в команде из n человек. У вас сложилась традиция, по которой человек на свой день рождения угощает всех пиццами. Если день рождения выпадает на выходной день, то угощение переносится на понедельник. Вы решили узнать, как часто может случиться так, что в один день угощать пиццами будут сразу несколько человек (хотя бы двое). А именно вы хотите найти математическое ожидание количества таких дней в 2019 году, первое января которого приходится на вторник. Считайте, что все дни рождения равновероятны и независимы для всех людей и что вероятность родиться 29 февраля равна нулю.
Единственная строка входных данных содержит одно целое число n (1 ≤ n ≤ 200).
В единственной строке выходных данных выведите вещественное число — ответ на задачу. Абсолютная или относительная погрешность не должна превышать 10 - 9.
1
0.000000000000
2
0.005081628823
Назовем множество X хорошим, если XOR-сумма всех его элементов 
равна 42.
У вас есть очередь (изначально пустая). Над очередью выполняют n операций двух типов:
Ваша задача заключается в том, чтобы после каждой операции ответить, можно ли в очереди выделить хорошее подмножество, или нет.
В первой строке задано одно целое число n (1 ≤ n ≤ 100 000) — количество запросов.
В следующих n строках записаны операции. Операция первого типа записывается в формате '+ x', где x (0 ≤ x ≤ 42) — число, которое необходимо добавить в очередь. Операция второго типа записывается как символ '-'.
Выведите n строк. В каждой строке выведите 'Yes', если после очередной операции можно выделить хорошее подмножество, и 'No' — в противном случае.
2
+ 42
-
Yes
No
5
+ 2
+ 8
+ 32
+ 11
-
No
No
Yes
Yes
No
Однажды, во время вечерней прогулки по лесу, мальчик Вова пришел к реке и увидел, что на другом берегу застрял его друг Ваня. Вове нужно спасти его друга, так как тот не умеет плавать! В реке находится n × (n + 1) островов в виде сетки. Однако между ними нет мостов! Там же на берегу Вова встретил злого волшебника Зедикуса, который согласился помочь только при условии, что Вова решит одну непростую задачу. Вове нужно посчитать количество способов построить мосты так, чтобы существовал хотя бы один путь с одного берега на другой. Помогите Вове решить эту задачу. Вове разрешено строить мосты только между соседними островами.
Более формально, каждый остров имеет координаты (r, c) (1 ≤ r ≤ n, 1 ≤ c ≤ n + 1), где r — номер строки, а c — номер столбца. Если остров имеет координаты (r, c), то соседние острова имеют координаты (r + 1, c), (r, c + 1), (r - 1, c), (r, c - 1), если таковые существуют. Острова, которые находятся в первом и последнем столбце, то есть острова с координатами (r, c), где 
(т. e. c равно либо 1, либо n + 1), уже соединены с берегами.
Путем с одного берега на другой является такая последовательность островов (r1, c1), (r2, c2), ..., (rk, ck), что для каждого i (1 ≤ i < k) существует мост между островами (ri, ci) и (ri + 1, ci + 1), также остров (r1, c1) находится в первом столбце (c1 = 1), а остров (rk, ck) находится в последнем столбце (ck = n + 1).
Два способа построить мосты считаются различными, если найдется такой мост, что в одном из способов он построен, а в другом нет. Для лучшего понимания условия смотрите иллюстрацию ниже. На иллюстрации приведен один из способ построить мосты, чтобы перейти с одного берега на другой.
На данной иллюстрации присутствуют два берега, описанные в условии. Левый берег обозначен через L, а правый через R. Островами на данной иллюстрации являются зеленые кружки. Мостами являются прямоугольники с закругленными углами. Как можно видеть, данная конфигурация мостов содержит путь между левым берегом и правым. Напомним, что мосты между берегом L и левым столбцом островов присутствуют изначально. Тоже самое для правого берега R и правого столбца островов. Также стрелки rows и columns соответствуют осям координат для строк и столбцов. В единственной строке входных данных содержится единственное целое число n (1 ≤ n ≤ 42) — размерность сетки островов.
Выведите единственное целое число — ответ на задачу по модулю 109 + 7.
1
1
42
37237670
Вам дана строка s состоящая только из цифр «1»-«9», символов «a»-«z», «*» и «=» представляющая из себя уравнение. В уравнении присутствуют только операции умножения (символ «*»), целые положительные числа меньшие 10, а также неизвестные переменные. Переменные могут находиться только по левую сторону уравнения, могут встречаться несколько раз, а их имена являются строчными буквами латинского алфавита.
Если вместо неизвестных переменных подставить некотороые целые положительные числа так, что результат выполнения операций левой части уравнения совпадет с результатом правой, то такой набор чисел называется решением данного уравнения.
Определите, сколько всего решений существует у данного уравнения. Два решения считаются различными, если найдется хотя бы одна присутсвующая в уравнении переменная, значение которой отличается.
Вам дана единственная строка s (|s| ≤ 1 000) — исходное уравнение. В строке присутсвует ровно один символ «=».
Гарантируется, что в уравнении присутсвует как минимум одна неизвестная переменная.
В единственной строке выведите одно целое число — количество решений данного уравнения по модулю 109 + 7.
Выведите «-1», если уравнение имеет бесконечное количество решений.
a*b=4*2
4
x*y*1=7*9*8*8
42
Все решения для уравнения из первого примера:
Вам дан массив A состоящий из n целых чисел, а также некоторое число k. Вас просят найти такую подпоследовательность массива A, что медиана m данной подпоследовательности будет как можно ближе к числу k, то есть |m - k| — минимально, а среди всех таких — подпоследовательность с максимальной длиной.
Медианой массива X длины len называется число, находящееся в отсортированном в порядке неубывания массиве X (xi ≤ xi + 1) на позиции 
, если считать, что индексы массива X начинаются с 1.
В первой строке задано два целых числа n и k (1 ≤ n ≤ 200 000, 1 ≤ k ≤ 109) — размер массива A и значение, к которому нужно найти ближайшую медиану, соответственно.
Во второй строке задано n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109) — элементы массива A.
В первой строке выведите одно целое число l (1 ≤ len ≤ n) — размер подпоследовательности.
Во второй строке выведите len целых чисел p1, p2, ..., plen (1 ≤ pi ≤ n, pi < pi + 1) — номера элементов массива A, включенных в данную подпоследовательность.
5 3
1 2 3 4 5
5
1 2 3 4 5
5 42
1 2 3 4 5
1
5
Назовем цифровой характеристикой числа n некоторую функцию f(n) такую, что:
где g(n) — сумма цифр десятичной записи числа n.
Ваня уже научился быстро вычислять цифровую характеристику для довольно больших чисел в уме, чем, собственно, и решил похвастаться перед всеми участниками BSUIR Open 2018. Участникам не слишком понравилось такое хвастовство, поэтому они предложили ему вычислить цифровую характеристику для очень большого числа, настолько большого, что записать его на бумаге не представляется возможным.
Вместо самого числа Ване предложили его описание, по которому можно восстановить это число. Описание представляет из себя четверку чисел a, b, m и k. Чтобы получить исходное число, Ване необходимо в первую очередь сгенерировать k чисел ai таких, что 
при i > 1, 
. Полученные числа ему необходимо выписать на листок бумаги в обратном порядке, таким образом получив одно большое число. Для этого числа он и должен найти цифровую характеристику.
Теперь осталось научиться проверять ответ. Напишите программу, которая по заданному описанию числа определит его цифровую характеристику.
В первой строке задано одно целое число t (1 ≤ t ≤ 10 000) — количество чисел, для которых необходимо вычислить цифровую характеристику.
В следующих t строках записаны описания чисел. Каждое описание состоит из четырех целых чисел a, b, m и k (0 ≤ a, b ≤ 109, 2 ≤ m ≤ 109 + 7, 1 ≤ k ≤ 109) — параметров генерации числа.
Гарантируется, что числа, восстановленные по каждому описанию, не содержат лидирующих нулей. Обратите внимание, что число 0 не содержит лидирующих нулей.
Выведите t строк. В каждой строке выведите ans (0 ≤ ans ≤ 9) — цифровую характеристику соответствующего числа.
4
1 1 10 5
4 5 7 8
1 2 3 4
42 42 2018 18
6
7
4
9
По первому описанию было получено число 54321. Его цифровая характеристика равна f(54321) = f(15) = f(6) = 6.
По четвертому описанию было получено число 7567146726305885465044624203783362942522101681268442.
Пусть f(x) — максимальный четный делитель x или 0, если такого нет.
Вам дано n запросов li, ri. Для каждого запроса вам необходимо найти 
.
В первой строке входных данных содержится одно целое число n (1 ≤ n ≤ 105) — количество запросов.
В каждой из следующих n строк содержатся по два целых числа li и ri (1 ≤ li ≤ ri ≤ 105) — описание i-го запроса.
Выведите n строк. В i-й строке выведите одно целое число — ответ на i-й запрос.
1
2 12
42
2
1 42
42 45
462
86
Треугольничком будет называть невырожденный тупоугольный треугольник, наименьшие по длине стороны которого отличаются не более чем в q раз. Для заданного множества точек требуется найти количество треугольничков, которые могут быть образованы с углами в этих точках.
В первой строке задается два числа n и q (1 ≤ n ≤ 1 000, 1 ≤ q ≤ 30 000) — количество точек и множитель сравнения для сторон соответственно. Множитель q задается ровно с двумя знаками после запятой.
В следующих n строках задается по два целых числа xi yi (|xi|, |yi| ≤ 104) — координаты i-й точки.
Гарантируется, что точки попарно различны и для любой тройки различных точек A B C выполняется условие |D(A, B) - D(A, C) * Q| > 10 - 6, где D(A, B) это евклидово расстояние между точками A и B.
В единственной строке выведите искомое количество треугольничков.
6 2.01
0 2
2 4
-1 3
0 0
1 3
1 2
6
9 2.64
10 -7
0 -6
-1 8
9 -3
-1 10
-3 -1
9 9
-1 -5
4 -3
42
Вова постоянно желает узнать что-то новое. Много чего он спрашивает у Леши. На этот раз Леша дал ему следующую задачу...
Задан массив из n целых чисел a1, a2, ..., an. Необходимо найти такую перестановку p, что 
будет максимально. Вова пока не придумал решение, но вам выдался шанс придумать решение быстрее его.
Напомним, что операция 
, она же XOR, она же исключающее ИЛИ. Данной операции соответствует оператор ^ в языках программирования C++ и Java. В языке Pascal за данную операцию отвечает оператор xor. Для чисел 5 и 3 результат операции будет равен: 
.
В первой строке ввода находится целое число n (1 ≤ n ≤ 8) — размер массива A.
В следующей строке находятся n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109) — массив A.
В единственной строке выведите n целых чисел p1, p2, ..., pn (1 ≤ pi ≤ n) — перестановка, при которой достигается максимальная XOR-сумма массива. Напомним, что в перестановке все элементы различны. Если существует несколько правильных ответов, разрешается вывести любой.
4
21 2 2018 42
2 4 1 3
Пока скучные соседские дети играют в скучный футбол за окном, маленький Джим играет со своим деревом, состоящим ровно из n вершин. Джим кладет в некоторую вершину S фишку. Игра заканчивается как только фишка окажется в вершине F. Очевидно, что для того, чтобы игра закончилась, фишку нужно как-то передвигать (для наших самых скрупулёзных читатей отметим, что S и F не совпадают). Любая последовательность передвижений, которая хоть сколько-нибудь напоминает Джиму одну из ранее увиденных им последовательностей, кажется ему невероятно скучной. Для того, чтобы избежать невероятно скучных последовательностей, мальчик двигает фишку случайно: если фишка сейчас находится в вершине v, то он равновероятно выбирает одну из соседних c v вершин в дереве и перемещает фишку в нее. Но после того, как Джим сыграл чуть более 4↑↑ 2 раз в данную игру, она также стала казаться ему немного скучной. С другой стороны, большое количество сыгранных игр научило Джима интуитивно понимать, сколько раз в среднем нужно переместить фишку для того, чтобы закончить игру для данных S и F. На следующий день Джим решил, что ставить эксперименты на невинных людях немного интереснее, чем играть с деревом. Для начала, он решил узнать, насколько хорошо справляются с определенем математического ожидания количества перемещений, требуемого для завершения игры другие люди.
В первой строке входных данных находятся два числа 2 ≤ n ≤ 105 и 1 ≤ q ≤ 105 — количество вершин в дереве и количество пар вершин S и F, для которых нужно найти матожидание количества перемещений.
Далее следует n - 1 строка, каждая из них содержит числа v и u (1 ≤ ui, vi ≤ n, ui ≠ vi) — номера вершин дерева, соединенных очередным ребром. Гарантируется, что заданный граф представляет собой дерево.
Каждая из следующих q строк содержит числа 1 ≤ Si, Fi ≤ n (Si ≠ Fi) — номера стартовой и конечной вершин для i-го эксперимента.
Можно показать, что для любого дерева и заданных стартовой и конечной вершин S, F ответ можно выразить как 
, где P и Q — взаимно простые целые числа, а 
. Выведите значение P × Q - 1 по модулю 109 + 7 для каждой пары (Si, Fi) на отдельной строке.
3 2
1 2
2 3
1 3
1 2
4
1