Таня играет в симулятор градостроителя Cities: Skylines. Новой стратегией развития города стало развитие аграрного сектора, и Таня планирует потратить все оставшиеся деньги в городском бюджете на межевание полей.
Город в игре состоит из маленьких квадратиков со стороной $$$1$$$. Денег в городе осталось ровно на $$$S$$$ таких квадратиков полей.
Поля в игре должны строиться по одному простому правилу: поле обязательно должно быть квадратное. При этом чем больше поле, тем больше потенциальной прибыли оно принесёт аграрному сектору, поэтому Таня заинтересована в том, чтобы построить как можно больше как можно больших по площади полей.
Поля какого размера стоит строить Тане?
Строго говоря, требуется перечислить площади квадратов с целочисленными сторонами, такие что:
В первой строке ввода содержится целое число $$$t$$$ — количество наборов входных данных ($$$1 \le t \le 1000$$$).
В каждой из следующих $$$t$$$ строк содержится одно целое число $$$S$$$ $$$(1 \le S \le 10^{17})$$$ — доступная площадь.
Обратите внимание, что число $$$S$$$, а также сам ответ на задачу могут не помещаться в 32-битный целочисленный тип данных. Поэтому при решении этой задачи рекомендуется использовать 64-битный целочисленный тип данных. Например, long long в C++ и int64 в Pascal.
Для каждого набора входных данных на новой строке выведите через пробел целые числа — ответ на задачу. Выводить числа нужно в невозрастающем порядке.
| Группа | Доп. ограничения | Баллы | Необх. подгруппы |
| $$$S$$$ | |||
| $$$1$$$ | $$$S \le 1000$$$ | $$$30$$$ | — |
| $$$2$$$ | $$$S \le 10^5$$$ | $$$30$$$ | $$$1$$$ |
| $$$3$$$ | — | $$$40$$$ | $$$1$$$, $$$2$$$ |
Обратите внимание, что для прохождения подгрупп ваша программа не обязана выдавать верный ответ на примерах из условия.
39363
9 1 1 1 49 9 4 1
Разберём по шагам пример, где $$$S = 63$$$.
В итоге квадраты в ответе будут $$$49$$$, $$$9$$$, $$$4$$$ и $$$1$$$.
Каждый, кто хочет обучаться искусству магии в Коллегии Винтерхолда, перед поступлением должен показать, что он(-а) обладает магическими способностями вообще. Обычно для этого будущий студент должен продемонстрировать использование какого-нибудь простенького заклинания.
Однако недавно Архимаг Савос Арен пришел к тому, что каждый уважающий себя студент Коллегии Винтерхолда должен также обладать и некоторыми математическими способностями, поскольку ни для кого не секрет, что математика — царица наук. Даже в Скайриме.
Поэтому было решено на вступительном испытании давать, кроме всего прочего, одну математическую задачку. Архимаг даже смог придумать подходящую задачу для испытания, однако для начала он хочет удостовериться в том, что она не слишком простая и не слишком сложная. Поэтому предложил её решить Вам, чтобы проверить это.
Савос Арен называет число $$$x$$$ $$$d$$$-круглым в системе счисления по основанию $$$b$$$, если в $$$b$$$-ичной записи числа $$$x$$$ в конце находится $$$d$$$ нулей или больше. Например, число $$$123000_{10}$$$ будет $$$3$$$-круглым, $$$2$$$-круглым, $$$1$$$-круглым и даже $$$0$$$-круглым в десятичной системе счисления, а число $$$16_{10} = 10000_{2}$$$ будет $$$4$$$-круглым, $$$3$$$-круглым, $$$2$$$-круглым, $$$1$$$-круглым и $$$0$$$-круглым в двоичной системе счисления.
Савос Арен дает вам четыре числа $$$b$$$, $$$d$$$, $$$l$$$ и $$$r$$$. Задача заключается в том, чтобы найти количество $$$d$$$-круглых чисел в системе счисления по основанию $$$b$$$ между числами $$$l$$$ и $$$r$$$ включительно.
В первой строке задано одно целое число $$$b$$$ $$$(2 \le b \le 100)$$$ — степень счисления.
Во второй строке задано одно целое число $$$d$$$ $$$(0 \le d \le 9)$$$ — параметр «круглости» искомых чисел.
В третьей строке задано одно целое число $$$l$$$ $$$(1 \le l \le 10^{18})$$$ — левая граница отрезка.
В четвертой строке задано одно целое число $$$r$$$ $$$(l \le r \le 10^{18})$$$ — правая граница отрезка.
Обратите внимание, что числа $$$l$$$ и $$$r$$$, а также сам ответ на задачу могут не помещаться в 32-битный целочисленный тип данных. Поэтому при решении этой задачи рекомендуется использовать 64-битный целочисленный тип данных. Например, long long в C++ и int64 в Pascal.
Выведите одно целое число — количество искомых чисел.
| Группа | Доп. ограничения | Баллы | Необх. подгруппы | ||
| $$$b$$$ | $$$d$$$ | $$$l, \, r$$$ | |||
| $$$1$$$ | — | $$$d = 0$$$ | — | $$$10$$$ | — |
| $$$2$$$ | — | — | $$$l = r$$$ | $$$10$$$ | — |
| $$$3$$$ | $$$b = 10$$$ | — | $$$r \le 10^6$$$ | $$$10$$$ | — |
| $$$4$$$ | $$$b = 2$$$ | — | $$$r \le 10^6$$$ | $$$10$$$ | — |
| $$$5$$$ | — | — | $$$r \le 10^6$$$ | $$$20$$$ | $$$3$$$, $$$4$$$ |
| $$$6$$$ | $$$b = 10$$$ | — | — | $$$10$$$ | $$$3$$$ |
| $$$7$$$ | $$$b = 2$$$ | — | — | $$$10$$$ | $$$4$$$ |
| $$$8$$$ | — | — | — | $$$20$$$ | $$$1$$$ — $$$7$$$ |
Обратите внимание, что для прохождения подгрупп ваша программа не обязана выдавать верный ответ на примерах из условия.
10 1 1 100
10
10 0 5 17
13
2 2 7 15
2
5 1 1 100
20
Разберем первый пример из условия.
В нем задана десятичная система счисления. Среди чисел от $$$l$$$ до $$$r$$$ $$$1$$$-круглыми будут следующие: $$$10_{10}$$$, $$$20_{10}$$$, $$$30_{10}$$$, $$$40_{10}$$$, $$$50_{10}$$$, $$$60_{10}$$$, $$$70_{10}$$$, $$$80_{10}$$$, $$$90_{10}$$$, $$$100_{10}$$$.
Рассмотрим также третий пример.
В нем искомыми числами будут $$$8_{10} = 1000_2$$$ и $$$12_{10} = 1100_2$$$.
Каждый посетитель таверны знает, что в хорошей колоде должна быть хотя бы одна легендарная карта.
Порывшись в своей коллекции, Валира заметила, что для создания любой легендарной карты нужно $$$n$$$-значное красивое число волшебной пыли.
Разбойница считает число $$$x$$$ красивым, если каждые две соседние цифры числа $$$x$$$ образуют число, которое делится на $$$3$$$.
Например, число $$$12754$$$ — «красивое», поскольку числа $$$12, \, 27, \, 75, \, 54$$$ делятся на $$$3$$$, а число $$$1221$$$ не является красивым, так как $$$22$$$ не делится на $$$3$$$.
Валира интересуется, сколько всего существует $$$n$$$-значных «красивых» чисел. Помогите ей вычислить их количество!
Дано целое число $$$n$$$ $$$(2 \le n \le 27)$$$ — количество разрядов в числе волшебной пыли, требуемой для создания легендарной карты.
Вывести единственное число — количество «красивых» $$$n$$$-значных чисел.
Обратите внимание, что ответ на задачу может не помещаться в 32-битный целочисленный тип данных. Поэтому при решении этой задачи рекомендуется использовать 64-битный целочисленный тип данных. Например, long long в C++ и int64 в Pascal.
Всего в задаче $$$25$$$ тестов, не считая примера из условия. За каждый успешно пройденный Вашей программой тест Вам будет даваться $$$4$$$ балла.
Обратите внимание, что для прохождения подгрупп ваша программа не обязана выдавать верный ответ на примерах из условия.
3
102
Вы играете в компьютерную игру «Шахматы 2023». Как и в обычных шахматах, здесь есть поле, однако, в отличие от них, оно имеет размеры $$$n \times m$$$.
Кроме того, в «Шахматах 2023» есть особая фигура «Разведчик», которая атакует все клетки, которые находятся правее и ниже этой фигуры. На данный момент на поле находятся $$$q$$$ «Разведчиков». Ваша задача заключается в том, чтобы посчитать количество клеток, атакованных «Разведчиками».
Будем считать, что клетка, на которой стоит «разведчик», тоже считается атакованной.
В первой строке заданы три целых числа $$$n, \, m, \, q$$$ $$$(1 \le n, \, m \le 10^9, \, 1 \le q \le 10^5)$$$ — размеры поля и количество «Разведчиков» соответственно.
В следующих $$$q$$$ строках описываются положение «Разведчиков».
Положение каждого «Разведчика» описывается двумя числами $$$x, \, y$$$ $$$(1 \le x \le n, \, 1 \le y \le m)$$$ — номер строки (считая сверху) и номер столбца (считая слева), на пересечении которых стоит «Разведчик».
Гарантируется, что никакие два разведчика не стоят в одной клетке.
Выведите одно число — количество атакованных клеток.
| Группа | Доп. ограничения | Баллы | Необх. подгруппы |
| $$$1$$$ | $$$n, \, m, \, q \le 100$$$ | $$$20$$$ | — |
| $$$2$$$ | $$$n, \, m \le 1000$$$ | $$$30$$$ | $$$1$$$ |
| $$$3$$$ | $$$n = 1, \, m \le 10^5$$$ | $$$10$$$ | — |
| $$$4$$$ | $$$n \le 10^5, \, m = 1$$$ | $$$10$$$ | — |
| $$$5$$$ | — | $$$30$$$ | $$$1, \, 2, \,\ 3,\ 4$$$ |
Обратите внимание, что для прохождения подгрупп ваша программа не обязана выдавать верный ответ на примерах из условия.
8 15 3 3 10 5 7 6 12
48
Картинка к примеру, в которой серым выделены клетки, бьющиеся хотя бы одним разведчиком:
Таня – начинающий гейм-дизайнер и гейм-девелопер – создаёт собственную двухмерную игру, которая совмещает Minecraft и Tetris (Таня знает, что люди очень любят игры с квадратиками). В данный момент она тестирует функционал, который заставляет блоки земли покрываться текстурой травы. По её задумке, если какая-то грань блока земли открыта под небом, она должна отображаться как трава.
Она создала игровой мир длины $$$n$$$ и бесконечной высоты для экспериментов.
На этом участке она несколько раз случайным образом создаёт линии из блоков земли в небе. Каждый раз после создания эти блоки падают вертикально вниз и оказываются либо на земле, либо сверху на другом блоке. Игровой мир изначально покрыт травой.
У Тани есть доступ к статистике игрового движка, и она знает, сколько раз отрисовалась текстура травы в игре. Она хочет быстро сравнивать это число с ожидаемым числом этих текстур. Она просит вас написать для тестирования модуль, который по логам игры при необходимости подсчитывает ожидаемое число текстур травы в игровом мире.
Данные вам логи игры выглядят как список команд. Команды могут быть двух типов:
Гарантируется, что текстуры травы не отрисовываются под землёй, а также на границах игрового мира.
В первой строке заданы целые числа $$$n$$$ и $$$q$$$ $$$(1 \le n \le 10^6, \, 1 \le q \le 10^4)$$$ — длина тестового игрового мира и общее количество команд в логах игры.
В следующих $$$q$$$ строках содержатся команды из логов игры:
В ответ на каждую команду типа $$$2$$$ выведите ожидаемое количество текстур травы, которое должно отображаться в заданном игровом мире в соответствии с внесёнными в него изменениями.
Обозначим за $$$x$$$ количество команд второго типа.
| Группа | Доп. ограничения | Баллы | Необх. подгруппы | ||
| $$$n$$$ | $$$b$$$ | $$$x$$$ | |||
| $$$1$$$ | $$$n \le 10^3$$$ | $$$b = 1$$$ | $$$x = 1$$$ | 30 | — |
| $$$2$$$ | — | — | $$$x \le \frac{q}{100}$$$ | 30 | $$$1$$$ |
| $$$3$$$ | — | — | — | 40 | $$$1$$$, $$$2$$$ |
3 7 2 1 1 2 1 2 2 2 1 1 1 1 3 1 2
3 5 3
Для наглядности ниже указана иллюстрация того, что происходит с блоками земли и текстурами травы в примере при добавлении линий блоков в игровой мир.
Команда 1 1 2:
![]() | ![]() |
Команда 1 2 2:
![]() | ![]() |
Каждый посетитель таверны знает, что в хорошей колоде должна быть хотя бы одна легендарная карта.
Порывшись в своей коллекции, Валира заметила, что для создания любой легендарной карты нужно $$$n$$$-значное красивое число волшебной пыли.
Разбойница считает число $$$x$$$ красивым, если каждые две соседние цифры числа $$$x$$$ образуют простое число.
Число $$$p$$$ называется простым, если оно отлично от $$$1$$$ и делится без остатка только на $$$1$$$ и на само $$$p$$$. Так, некоторыми двузначными простыми числами являются $$$11, \, 29$$$ и $$$97$$$, а числа $$$15 = 3 \cdot 5$$$ и $$$39 = 3 \cdot 13$$$ таковыми не являются.
Число $$$41197$$$ — «красивое», поскольку числа $$$41, 11, 19, 97$$$ простые, а число $$$1161$$$ не является красивым, так как число $$$16$$$ не является простым.
Валира интересуется, сколько всего существует $$$n$$$-значных «красивых» чисел. Помогите ей вычислить их количество!
Поскольку ответ может оказаться очень большим, от вас требуется вывести не сам ответ, а его остаток от деления на число $$$10^9 + 7$$$.
Дано целое число $$$n$$$ $$$(2 \le n \le 10^{15})$$$ — количество разрядов в числе волшебной пыли требуемой для создания легендарной карты
Вывести единственное число — остаток от деления количества «красивых» $$$n$$$-значных чисел на число $$$10^9 + 7$$$.
| Группа | Доп. ограничения | Баллы | Необх. подгруппы |
| $$$1$$$ | $$$ n = 2 $$$ | $$$10$$$ | — |
| $$$2$$$ | $$$ 3 \le n \le 6 $$$ | $$$30$$$ | 1 |
| $$$3$$$ | $$$7 \le n \le 10^5 $$$ | $$$30$$$ | 1, 2 |
| $$$4$$$ | — | $$$30$$$ | 1, 2, 3 |
Обратите внимание, что для прохождения подгрупп ваша программа не обязана выдавать верный ответ на примерах из условия.
3
52
7
2622