Муниципальный этап ВОШ по информатике в Петрозаводске и Карелии 2022-2023
A. Градостроитель
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Таня играет в симулятор градостроителя Cities: Skylines. Новой стратегией развития города стало развитие аграрного сектора, и Таня планирует потратить все оставшиеся деньги в городском бюджете на межевание полей.

Город в игре состоит из маленьких квадратиков со стороной $$$1$$$. Денег в городе осталось ровно на $$$S$$$ таких квадратиков полей.

Поля в игре должны строиться по одному простому правилу: поле обязательно должно быть квадратное. При этом чем больше поле, тем больше потенциальной прибыли оно принесёт аграрному сектору, поэтому Таня заинтересована в том, чтобы построить как можно больше как можно больших по площади полей.

Поля какого размера стоит строить Тане?

Строго говоря, требуется перечислить площади квадратов с целочисленными сторонами, такие что:

  1. Каждый следующий квадрат имеет максимально большую площадь в диапазоне от $$$1$$$ до остатка доступной площади;
  2. Площади всех квадратов в сумме должны давать ровно $$$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$$$

Обратите внимание, что для прохождения подгрупп ваша программа не обязана выдавать верный ответ на примерах из условия.

Пример
Входные данные
3
9
3
63
Выходные данные
9 
1 1 1 
49 9 4 1 
Примечание

Разберём по шагам пример, где $$$S = 63$$$.

  • Нам доступна площадь $$$63$$$. Самый большой квадрат, который имеет площадь, не превышающую $$$63$$$ – это квадрат площадью $$$49$$$ (со стороной $$$7$$$). Это легко проверить: если взять квадрат со стороной $$$8$$$, площадь его получится $$$64$$$, что превышает доступную нам площадь.
  • Нам доступна площадь $$$63 - 49 = 14$$$. Самый большой квадрат, который имеет площадь, не превышающую $$$14$$$ – это квадрат площадью $$$9$$$ (со стороной $$$3$$$).
  • Нам доступна площадь $$$14 - 9 = 5$$$. Самый большой квадрат, который имеет площадь, не превышающую $$$5$$$ – это квадрат площадью $$$4$$$ (со стороной $$$2$$$).
  • Нам доступна площадь $$$5 - 4 = 1$$$. Самый большой квадрат, который имеет площадь, не превышающую $$$1$$$ – это квадрат площадью $$$1$$$ (со стороной $$$1$$$).
  • Нам доступна площадь $$$1 - 1 = 0$$$. Мы выбрали все квадраты.

В итоге квадраты в ответе будут $$$49$$$, $$$9$$$, $$$4$$$ и $$$1$$$.

B. Вступительное испытание в Коллегию Винтерхолда
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Мы — единственная оставшаяся группа в Скайриме, изучающая тайные искусства. Есть, конечно, и другие учёные, но они работают поодиночке и часто вынуждены скрываться
— Фаральда, The Elder Scrolls V: Skyrim

Каждый, кто хочет обучаться искусству магии в Коллегии Винтерхолда, перед поступлением должен показать, что он(-а) обладает магическими способностями вообще. Обычно для этого будущий студент должен продемонстрировать использование какого-нибудь простенького заклинания.

Однако недавно Архимаг Савос Арен пришел к тому, что каждый уважающий себя студент Коллегии Винтерхолда должен также обладать и некоторыми математическими способностями, поскольку ни для кого не секрет, что математика — царица наук. Даже в Скайриме.

Поэтому было решено на вступительном испытании давать, кроме всего прочего, одну математическую задачку. Архимаг даже смог придумать подходящую задачу для испытания, однако для начала он хочет удостовериться в том, что она не слишком простая и не слишком сложная. Поэтому предложил её решить Вам, чтобы проверить это.

Савос Арен называет число $$$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$$$.

C. Будь начеку!
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Каждый посетитель таверны знает, что в хорошей колоде должна быть хотя бы одна легендарная карта.

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

D. Шахматный дозор
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Не умеешь играть по правилам? Придумай свои!
— Разработчики игр.

Вы играете в компьютерную игру «Шахматы 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
Примечание

Картинка к примеру, в которой серым выделены клетки, бьющиеся хотя бы одним разведчиком:

E. Шахтёрское ремесло
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Таня – начинающий гейм-дизайнер и гейм-девелопер – создаёт собственную двухмерную игру, которая совмещает Minecraft и Tetris (Таня знает, что люди очень любят игры с квадратиками). В данный момент она тестирует функционал, который заставляет блоки земли покрываться текстурой травы. По её задумке, если какая-то грань блока земли открыта под небом, она должна отображаться как трава.

Она создала игровой мир длины $$$n$$$ и бесконечной высоты для экспериментов.

На этом участке она несколько раз случайным образом создаёт линии из блоков земли в небе. Каждый раз после создания эти блоки падают вертикально вниз и оказываются либо на земле, либо сверху на другом блоке. Игровой мир изначально покрыт травой.

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

Данные вам логи игры выглядят как список команд. Команды могут быть двух типов:

  • $$$1$$$ $$$a$$$ $$$b$$$ создаёт в небе линию из $$$b$$$ блоков, начиная с координаты $$$a$$$, если считать от края игрового мира длиной $$$n$$$.
  • $$$2$$$ означает, что Таня проверила статистику движка и узнала число текстур, и вашему модулю нужно посчитать и вывести ожидаемое число текстур травы в текущем состоянии игры.

Гарантируется, что текстуры травы не отрисовываются под землёй, а также на границах игрового мира.

Входные данные

В первой строке заданы целые числа $$$n$$$ и $$$q$$$ $$$(1 \le n \le 10^6, \, 1 \le q \le 10^4)$$$ — длина тестового игрового мира и общее количество команд в логах игры.

В следующих $$$q$$$ строках содержатся команды из логов игры:

  • Если команда начинается на $$$1$$$, то следом за ней через пробел заданы целые числа $$$a$$$ и $$$b$$$ $$$(a, \, b \gt 0; \, a + b \le n)$$$ — координата начала линии блоков и длина этой линии блоков.
  • Если команда начинается на $$$2$$$, то больше в этой строке ничего нет.
Выходные данные

В ответ на каждую команду типа $$$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:

 

F. Будь начеку! 2
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Каждый посетитель таверны знает, что в хорошей колоде должна быть хотя бы одна легендарная карта.

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