Энтерпрайз наконец нашел Куб борг, и теперь Пикару придется попасть во внутрь. Понятно, что борги защитили свой Куб специальным кодом. Раньше код можно было легко посчитать, прочитав числа прямо в космосе, расположенные на углах куба, но борги закрыли эти числа защитным полем. Сам код — это сумма всех восьми чисел, спрятанных в углах Куба.
Но теперь их не видно...
Но так как борги должны были сами возвращаться на Куб, а помнили код не все из них, была оставлена подсказка — числа на сторонах Куба. Каждое угловое число можно вычислить, перемножив три числа на гранях, которые сходятся в этом углу.
Энтерпрайз облетел Куб борг — теперь у Пикара есть числа со всех сторон Куба.
Помогите Пикару: зная числа на сторонах Куба, вычислите сумму всех угловых чисел.
В первой строке даны 6 целых чисел через пробел $$$v_1, \ldots, v_6$$$ $$$(1 \le v_i \le 500)$$$ — числа, расположенные на верхней, нижней, левой, правой, передней и задней сторонах Куба соответственно.
В первой строке выведите одно целое число $$$C$$$ $$$(1 \le C \le 10^9)$$$ — код для доступа в Куб борг.
1 2 3 4 4 5
189
Первый тестовый пример
Числа в углах куба соответственно равны:
Сумма всех чисел в углах равна $$$12 + 15 + 16 + 20 + 24 + 30 + 32 + 40 = 189$$$.
Айдар, Бегимай и Виктор пришли на пробный тур чемпионата.
Они увидели в списке доступных компиляторов Scratch и вспомнили, как начинали изучение программирования с этого языка.
Например, при ручном тестировании часто было непонятно, что программа ждёт ввода той или иной переменной. Поэтому иногда они локально добавляли вывод имени переменной перед вводом (но после убирали его при отправке в тестирующую систему).
Ребята даже нашли в системе несколько своих отправок на Scratch с тех давних времён.
Теперь ребятам стало интересно — а сколько суммарно символов они дополнительно выводили при локальном тестировании по сравнению с итоговой посылкой в систему?
В первой строке дано целое число $$$n$$$ $$$(2 \le n \le 10^5)$$$ — количество строк в коде программы на языке Scratch.
Следующие $$$n$$$ строк содержат по одной команде анализируемой программы.
Команды бывают одного из следующих видов:
Гарантируется, что
Гарантируется, что op может быть только одним из следующих символов:
Гарантируется, что
Гарантируется, что все переменные используются в правой части арифметических выражений только после их корректной инициализации.
Выведите единственное целое число $$$P$$$ $$$(1 \le P \le 10^9)$$$ — суммарное количество символов, выведенных ребятами дополнительно при локальном тестировании данной программы.
6Ask read_token and waitSet first to answerAsk read_token and waitSet second to answerSet result to first + secondSay result
11
15Ask read_token and waitSet a to answerAsk read_token and waitSet bb to answerSet ccc to a * bbSet dddd to a / bbSet dddd to ccc + ddddSay ddddAsk read_token and waitSet bb to answerAsk read_token and waitSet ccc to answerSet x to bb * ddddSet x to ccc - xSay x
8
Первый тестовый пример
В рамках программы производится две операции ввода:
Суммарно ребята выводили дополнительно ровно $$$5 + 6 = 11$$$ символов.
Второй тестовый пример
В рамках программы производится четыре операции ввода:
Суммарно ребята выводили дополнительно ровно $$$1 + 2 \cdot 2 + 3 = 8$$$ символов.
Анатолий и Антитолий пересеклись на форуме по проблемам числовой несправедливости.
Выяснилось, что кроме их любви к математике, у них очень много различий.
Например, Анатолий всегда стремится к честному распределению благ и не боится сложностей.
Антитолий же находит удовольствие в несправедливом распределении ресурсов, а также стремится к простоте во всём.
В данный момент Антитолий разрабатывает свою модель идеального общества, заданного параметром $$$n$$$.
Для завершения Антитолию осталось вычислить ровно одну величину — количество целых чисел $$$x$$$ в промежутке от $$$1$$$ до $$$n$$$ таких, что:
В первой строке дано целое нечётное число $$$n$$$ $$$(3 \le n \le 11^{13})$$$ — параметр идеального общества в модели Антитолия.
Выведите единственное целое число $$$R$$$ $$$(0 \le R \le n)$$$ — количество целых чисел $$$x$$$ в промежутке от $$$1$$$ до $$$n$$$ таких, что:
3
0
5
0
9
1
111
4
9753113579
9563
Определение Целое положительное число называется простым, если у него ровно два различных делителя.
Например, числа $$$3$$$, $$$17$$$ и $$$59$$$ являются простыми, а числа $$$1$$$ ($$$1$$$ делитель), $$$9$$$ ($$$3$$$ делителя), $$$30$$$ ($$$8$$$ делителей) и $$$111$$$ ($$$4$$$ делителя) простыми не являются.
Первый тестовый пример
Рассмотрим каждое из чисел, не превышающих $$$3$$$:
Соответственно, нет ни одного подходящего Антитолию чисел.
Второй тестовый пример
По сравнению с первым тестом добавляются два числа:
До сих пор нет подходящих Антитолию чисел.
Третий тестовый пример
По сравнению со вторым тестом добавляются четыре числа:
Лиса Алиса и Кот Базилио убежали от Буратино, но оставили ему кубик. Сказали, что на нём написано, где зарыт клад. Он, конечно, поверил.
На каждой грани кубика была выжжена цифра.
Буратино сказали, что нужно двигаться по граням кубика, каждый раз переходя на соседнюю грань и записывая цифры, которые на них нарисованы. На каждую грань можно зайти только один раз.
Самое большое число, которое удастся собрать таким образом, укажет, где зарыт клад. Первые три цифры — шаги на север от старой мельницы, остальные — на восток.
Помогите Буратино найти самое большое число, которое можно получить указанным способом. Он всё-таки хочет проверить, правду ли ему сказали.
В первой строке даны $$$6$$$ целых чисел $$$d_1, \ldots, d_6$$$ $$$(0 \le d_i \le 9)$$$ — цифры, выжженные на верхней, нижней, левой, правой, передней и задней гранях кубика соответственно.
Гарантируется, что хотя бы одна из цифр $$$d_i$$$ отлична от $$$0$$$.
В первой строке выведите одно целое число $$$X$$$ $$$(10^5 \le X \lt 10^6)$$$ — наибольшее число, которое можно получить описанным Буратино способом.
2 3 1 4 5 6
645312
Первый тестовый пример
Максимальное число $$$645312$$$ может быть получено при обходе граней кубика в следующем порядке:
Обратите внимание, что следующие числа получить нельзя:
Айдар, Бегимай и Виктор для решения сложной задачи написали своё первое дерево отрезков.
Но возникла проблема — их дерево выдавало неверные ответы даже на тестовых примерах из условия задачи.
В первую очередь, ребята предположили, что они неверно сопоставили полуинтервалы массива узлам. Виктор сказал, что надо вывести по порядку все узлы и их полуинтервалы.
Бегимай на это заметила, что простой построчный вывод не сильно ускорит процесс — надо визуализировать всё дерево целиком!
Внимание: Данная задача использует определённые правила построения дерева отрезков — ознакомьтесь с ними в примечании к задаче.
В первой строке дано целое число $$$n$$$ $$$(1 \le n \le 10^4)$$$ — размер массива.
Дерево необходимо визуализировать по слоям, каждому слою соответствует одна строка.
Ознакомьтесь с тестовыми примерами для уточнения подробностей.
1
[0;1)
2
[0;2)
[0;1) | [1;2)
3
[0;3)
[0;1) | [1;3)
| [1;2) | [2;3)
7
[0;7)
[0;3) | [3;7)
[0;1) | [1;3) | [3;5) | [5;7)
| [1;2) | [2;3) | [3;4) | [4;5) | [5;6) | [6;7)
9
[0;9)
[0;4) | [4;9)
[0;2) | [2;4) | [4;6) | [6;9)
[0;1) | [1;2) | [2;3) | [3;4) | [4;5) | [5;6) | [6;7) | [7;9)
| | | | | | | [7;8) | [8;9)
Определение
Дерево отрезков, построенное для массива длины $$$n$$$, представляет из себя бинарное дерево, в котором каждый узел сопоставлен какому-либо полуинтервалу данного массива:
Позислав и Минуслав пересеклись на форуме по физике целых чисел.
Выяснилось, что их области исследований очень схожи — Позислав изучает энергетические выбросы положительных чисел, а Минуслав — энергетические всплески отрицательных чисел.
Ребята решили объединить свои усилия и провести масштабное исследование знаковой спутанности:
Ребята объединили свои записи — теперь им остаётся найти количество пар спутанных по знаку событий.
В первой строке даны два целых числа $$$n$$$ и $$$d$$$ $$$(1 \le n \le 3 \cdot 10^5; 1 \le d \le 10^9)$$$ — количество исследованных энергетических событий и наибольшая разница во времени для существования спутанности.
Вторая строка содержит $$$n$$$ целых чисел $$$t_i$$$ $$$(1 \le t_i \le 10^9)$$$ — момент времени, когда произошло $$$i$$$-е событие.
Третья строка содержит строку $$$S$$$ $$$(|S| = n)$$$ — знаки полуосей, на которых произошли события:
Гарантируется, что записи даны в хронологическом порядке: $$$t_1 \le t_2 \le \ldots \le t_n$$$.
Выведите единственное целое число $$$T$$$ $$$(0 \le T \le 10^{18})$$$ — количество пар спутанных по знаку событий.
14 31 1 3 3 3 3 5 5 6 6 6 8 9 11+--+++--+++++-
23
Первый тестовый пример
События на положительной оси произошли в моменты времени $$$[1, 3, 3, 3, 6, 6, 6, 8, 9]$$$. События на отрицательной оси произошли в моменты времени $$$[1, 3, 5, 5, 11]$$$.
Перечислим спутанные пары событий:
Суммарно получаем $$$1 + 3 + 3 + 6 + 6 + 2 + 1 + 1 = 23$$$ пары спутанных событий.
Сирин переместился в параллельный мир, и Сказочному патрулю надо отправляться за ним.
Снежка подошла к старому камину и заметила, что за кирпичом торчит уголок какого-то старого свитка. Она осторожно вытащила его и развернула. На пергаменте был написан сплошной поток непонятных букв и символов, а рядом лежал небольшой листок со списком загадочных слов.
Девочки поняли, что это ещё один шифр Сирина. На краю листа была пометка — «Тем, кто хочет добраться до параллельного мира, нужно разбить весь текст на отдельные тайные слова из этого списка. Каждое слово можно использовать любое число раз, но ничего лишнего добавлять нельзя. Учтите: символы «?» в тексте заменяют любые буквы тайного слова».
Маша, взглянув на текст, который достала Снежка, поняла, что этот текст можно разбивать на слова множеством способов! Как же узнать, сколько всего таких способов существует? Она поняла, что придется считать. Но самим девочкам это, похоже, не осилить — нужна ваша помощь!
Помогите девочкам из Сказочного патруля догнать Сирина — определите, сколько существует различных способов разбить текст из пергамента на тайные слова из листочка.
В первой строке дано целое число $$$n$$$ $$$(1 \le n \le 100)$$$ — число тайных слов.
Каждая из следующих строк содержит строку $$$W_i$$$ $$$(1 \le |W_i| \le 10)$$$ — $$$i$$$-е тайное слово.
Гарантируется, что все слова $$$W_i$$$ уникальны, то есть для $$$i \ne j$$$ выполняется $$$W_i \ne W_j$$$.
Последняя строка содержит строку $$$T$$$ $$$(1 \le |T| \le 100)$$$ — текст из пергамента.
Гарантируется, что
Пусть $$$P$$$ — количество способов разбиения текста из пергамента на тайные слова.
В единственной строке выведите единственное целое число — остаток от деления $$$P$$$ на $$$M = 10^9 + 7$$$.
7abcdabbccdab?d
11
2ab??
4
Первый тестовый пример
Перечислим возможные способы разбиения текста:
Второй тестовый пример
Перечислим возможные способы разбиения текста:
Бегимай вернулась домой после соревнования — и её встретила очень радостная младшая сестра Динара.
Динара сказала, что она пристально следила за соревнованием — и даже придумала, как решать одну непростую задачу!
Единственное, в чём Динара пока сомневалась — насколько эффективным было придуманное ею решение. Поэтому Динара подготовила псевдокод своего решения, чтобы Бегимай его оценила.
Псевдокод Динары представляет собой комбинацию операторов трёх типов:
Теперь Бегимай должна определить суммарное количество операций, выполняемых данным решением, и сделать вывод из его эффективности.
Бегимай сразу увидела, что итоговое суммарное количество операций получилось просто огромным — и, чтобы слишком не расстраивать сестру, решила сказать ей остаток от деления данного количества на число $$$10^9 + 7$$$.
В первой строке дано целое число $$$n$$$ $$$(1 \le n \le 10^5)$$$ — количество строк в псевдокоде решения.
Каждая из следующих $$$n$$$ строк содержит один из трёх операторов:
Гарантируется, что
Пусть $$$T$$$ — суммарное количество операций, выполняемых описанным решением.
В таком случае выведите единственное целое число — остаток от деления $$$T$$$ на $$$10^9 + 7$$$.
13for 10for 300calc 5endfor 40calc 7calc 4endendcalc 45for 3calc 123end
19814
7for 2000for 1000for 3000calc 4000endendend
999832007
Первый тестовый пример
Декомпозируем представленный псевдокод:
Суммарно получается $$$T = 19400 + 45 + 369 = 19814$$$ операций.
Второй тестовый пример
Суммарно данное решение выполняет $$$T = 2000 \cdot 1000 \cdot 3000 \cdot 4000 = 24 \cdot 10^{12}$$$ операций.
Необходимо вывести остаток от деления $$$T$$$ на $$$10^9 + 7$$$, который равен $$$999832007$$$.
Сидя на звонке по livecoding по теме «деревья», два программиста «Kanda Software» начали играть на бумажке в игру — рисовать деревья. Естественно, не зеленые с листьями, а графы.
Сначала взяли дерево из единственной вершины с номером $$$1$$$. Потом дорисовали к нему вершину с номером $$$2$$$ и соединили их ребром, получив второе дерево, и назвали вершину номер $$$2$$$ его корнем.
Затем договорились, что каждое последующее $$$n$$$-е дерево будет строиться из $$$(n - 1)$$$-го дерева по следующей процедуре:
После нескольких деревьев у них закончилось место на бумаге, и они решили вместо рисования заняться подсчетами и начали задавать друг другу задачи на вычисление характеристик своей последовательности деревьев.
Один загадывал два числа, $$$n$$$ и $$$v$$$, а второй должен был посчитать сумму номеров вершин на кратчайшем пути от корня $$$n$$$-го дерева до вершины $$$v$$$ (включая начальную и конечную вершину).
Тут Слава заметил их игру и предложил для лучшего усвоения материала вычислить требуемую сумму для достаточно больших значений $$$n$$$. Естественно, провести на бумажке столь сложные вычисления невозможно. Помогите им это сделать.
В первой строке даны два целых числа $$$n$$$ и $$$v$$$ $$$(1 \le v \le n \le 10^{18})$$$ — номер дерева и номер вершины в дереве, соответственно.
В единственной строке выведите целое число $$$S$$$ – сумму номеров вершин на кратчайшем пути от корня $$$n$$$-го дерева до вершины $$$v$$$ (включая начальную и конечную вершину).
Гарантируется, что $$$S$$$ не превышает $$$9 \cdot 10^{18}$$$.
2 1
3
3 2
5
6 1
12
9 6
23
 |  |
$$$2$$$-е и $$$3$$$-е деревья соответственно.
 |  |
$$$6$$$-е и $$$9$$$-е деревья соответственно.
Первый тестовый пример
Сумма номеров вершин на пути равна $$$2 + 1 = 3$$$.
Второй тестовый пример
Сумма номеров вершин на пути равна $$$3 + 2 = 5$$$.
Третий тестовый пример
Сумма номеров вершин на пути равна $$$6 + 5 + 1 = 12$$$.
Четвёртый тестовый пример
Сумма номеров вершин на пути равна $$$9 + 8 + 6 = 23$$$.
В некоторой лаборатории к потолку подвешено $$$n$$$ лазеров. Изначально каждый лазер подвешен на расстоянии $$$a_i$$$ от потолка. При этом все лазеры висят в одной плоскости, и у каждого есть своя уникальная координата $$$x_i = i$$$.
На другом конце комнаты стоит экран. Все лазеры излучают свет в сторону экрана, поэтому если $$$2$$$ лазера висят на одной высоте, то свет из лазера с меньшей координатой не доходит до экрана.
Вы можете не более $$$k$$$ раз взять какой-то лазер и увеличить его расстояние от потолка на $$$1$$$. Вас интересует — при оптимальном использовании операции, свет какого наибольшего числа лазеров будет регистрироваться экраном?
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит $$$2$$$ целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^9$$$) — общее число лазеров и число операций соответственно.
Вторая строка каждого набора входных данных содержит через пробел $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — изначальные расстояния от лазеров до потолка.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите в единственной строке целое число — максимальное количество лазеров, свет от которых попадает на экран после применения не более $$$k$$$ операций.
34 41 2 3 44 51 1 1 19 24 3 3 10 5 5 5 99 11
437
Первый тестовый пример
Все лазеры уже находятся на разных высотах, поэтому не перекрывают свет друг от друга.
Второй тестовый пример
Изначально все лазеры находятся на одной и той же высоте, поэтому только свет от $$$4$$$-го лазера доходит до экрана.
Можно увеличить расстояние для $$$2$$$-го лазера на $$$1$$$ и расстояние для $$$3$$$-го лазера на $$$2$$$ — в таком случае лазеры будут висеть на расстояниях $$$[1, 2, 3, 1]$$$.
Всего операций изменения будет совершено $$$3$$$ (доступно $$$5$$$), и свет от $$$3$$$ лазеров доходит до экрана.
Обратите внимание, что с помощью $$$5$$$ доступных операций никак нельзя сделать, чтобы все $$$4$$$ лазера висели на различной высоте.
Третий тестовый пример
Один из лазеров на расстоянии $$$5$$$ можно переместить на $$$1$$$ — в таком случае до экрана будет доходить свет от $$$7$$$ различных лазеров.
Обратите внимание, что расстояние от потолка нельзя уменьшать — вы не можете переместить один из лазеров на расстоянии $$$3$$$ на $$$1$$$ ближе к потолку (чтобы его новое расстояние равнялось $$$2$$$).