README.md

Академия Бэкенда, 1 год, 2023, Алгоритмическая часть

Golang

Антон Цитульский, старший разработчик Edu

Сейчас Golang является одним из самых популярных языков программирования в бэкенде. Он сочетает в себе простоту Python и сравним по эффективности с C++.

За счет внутренней реализации Go позволяет обслуживать тысячи соединений одновременно, что особенно важно при проектировании бэкенда любого продукта.

1 задание

Ограничение времени	2 секунды
Ограничение памяти	256 МБ

Условие

Совсем недавно девочка Лиза узнала о существовании забытой месопотамской цивилизации. Она захотела погрузиться в эту тему и решила начать с изучения архитектуры древних шумеров. Они строили огромные шумериды из обсидиановых кубиков. Кубиком называется куб со стороной $1$.

Шумерида высоты $1$ это кубик. Шумерида высоты $(h⩾2)$ получается из шумериды высоты $h−1$, установкой её на прямоугольный параллелепипед $[2h−1×2h−1×1]$. То есть основание шумериды дублируется, а вокруг него выкладываются кубики.

Древние шумеры были самой продвинутой цивилизацией, поэтому они не строили шумериды, постепенно выкладывая кубики. Вместо этого они находили таинственный куб со стороной $2h−1$, после чего удаляли лишние кубики, чтобы получилась шумерида высоты $h$.

Назовём стоимостью шумериды количество кубиков, которое необходимо удалить при таком процессе постройки. Помогите Лизе посчитать стоимости шумерид с высотами $1,2,…,n$. То есть для каждой шумериды высоты $h (1⩽h⩽n)$ выведите её стоимость.

Формат входных данных

В первой строке дано целое число $n (1⩽n⩽2⋅10 ^ 5)$ — количество шумерид.

Формат выходных данных

Выведите $n$ целых чисел — стоимости шумерид с высотами $1,2,…,n$.

Замечание

Шумерида высоты $1$ состоит из одного кубика. Её стоимость равна $0$, так как ничего не надо удалять.

Шумерида высоты $2$ состоит из $1+9=10$ кубиков. Её стоимость равна $3^3 − 10 = 17$.

Шумерида высоты $3$ состоит из $1+9+25=35$ кубиков. Её стоимость равна $5 ^ 3 − 35 = 90$

Шумерида высоты 3:

Составляющие шумериды высоты 3

Тут должны были быть ещё два квадрата

Примеры данных

Ввод

5   

Вывод

5
0 17 90 259 564

2 задание

Ограничение времени	2 секунды
Ограничение памяти	256 МБ

Условие

Мало кто знает, что древние шумеры пользовались модифицированной версией современной очереди. Помимо запросов добавления в конец и удаления с начала, утерянная очередь умела обрабатывать запрос расширения. При расширении утерянной очереди, каждый элемент в ней дублируется, например: ${4,3,2,2}→{4,4,3,3,2,2,2,2},{1,2,1}→{1,1,2,2,1,1}$.

Лиза нашла глиняный шумерский манускрипт. Он описывает $m$ запросов к утерянной очереди. Запросы бывают трёх типов: добавление, расширение и удаление. Девочка уверена, что изначально утерянная очередь пуста.

Лизе интересно, какие элементы будут удаляться. Помогите ей обработать поступающие запросы.

Формат входных данных

В первой строке дано целое число $m (1⩽m⩽2⋅10 ^ 5) — количество запросов к утерянной очереди.

Следующие $m$ строк описывают запросы.

• $1 x (1⩽x⩽10 ^ 9)$ — добавить в конец утерянной очереди целое число $x$;
• $2$ — выполнить расширение утерянной очереди;
• $3$ — удалить элемент с начала утерянной очереди.

Гарантируется, что при запросах второго и третьего типа, утерянная очередь не пуста.

Формат выходных данных

Для каждого запроса третьего типа выведите удалённый элемент в отдельной строке.

Замечание

• Первый тест: ${}→{7}→{7,7}→{7,7,4}→{7,4}→{4}→{}$.
• Второй тест: ${}→{9}→{9,9}→{9,9,9,9}→{9,9,9}→{9,9}→{9}→{9,5}→{5}→{}→{6}$.
• Третий тест: ${}→{4}→{}→{3}→{3,5}→{3,3,5,5}→{3,5,5}→{3,3,5,5,5,5}→{3,5,5,5,5}→{5,5,5,5}→{5,5,5}$

Примеры данных

Пример 1

Ввод

6
1 7
2
1 4
3
3
3   

Вывод

7
7
4

Пример 2

Ввод

10
1 9
2
2
3
3
3
1 5
3
3
1 6

Вывод

9
9
9
9
5

Пример 3

Ввод

10
1 4
3
1 3
1 5
2
3
2
3
3
3   

Вывод

4
3
3
3
5   

3 задание

Ограничение времени	3 секунды
Ограничение памяти	256 МБ

Условие

Шумерская цивилизация оставила нам в наследство несколько загадочных лабиринтов. Загадочный лабиринт состоит $n$ рядов по $m$ комнат в каждом. Комната на пересечении $i$-й строки и $j$-го столбца имеет опасность $a_{ij}$.

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

Если шумер с выносливостью $k$ начнёт испытание в комнате $a_{ij}$, то за один ход он может переместиться в любую клетку в той же строке или в том же столбце, абсолютная разность опасности которой с $a_{ij}$ не превосходит  $k. Другими словами, из клетки $a_{ij}$ можно перейти в

• $a_{it}(1⩽t⩽m)$, если $∣a_{it} ⩽ −a_{ij}∣⩽k$;
• $a_{tj}(1⩽t⩽n)$, если $∣a_{tj} ⩽ −a_{ij}∣⩽k$;

Лиза хотела бы провести $q$ испытаний. В $i$-м испытании будет участвовать шумер с выносливостью $k_i$. Он начнёт в комнате $a_{x_i,y_i}$. Лизе интересно, сколько различных первых ходов этот шумер может сделать. Дальнейшая его судьба Лизу не интересует.

bruv...

Помогите Лизе найти ответ для каждого из $q$ испытаний.

Формат входных данных

В первой строке даны целые числа $ n,m,q (1⩽n,m,q⩽2⋅10 ^ 5 , n⋅m⩽2⋅10 ^ 5)$ — размеры загадочного лабиринта и количество испытаний.

В следующих $n$ строках даны целые числа $a_{i1} , a_{i2},…,a_{im} (a_{ij} ⩽ 10^ 9)$ — опасности комнат лабиринта в $i$-й строке.

Следующие $q$ строк содержат целые числа $x_i, y_i ,k_i (1⩽ x_i ⩽n, 1⩽ y_i ⩽m, 1⩽k_i ⩽10 ^ 9)$— описание $i$-го запроса.

Формат выходных данных

Для $i$-го испытания выведите единственное целое число — количество комнат, в которые может перейти шумер за один ход, начав с выносливостью $k_i$ в комнате $a_{x_i,y_i}.

Примеры данных

Ввод

3 4 5
5 1 3 3
7 6 2 4
5 9 1 8
2 2 1
3 3 3
2 4 5
1 4 3
1 1 2   

Вывод

1
2
5
4
4

4 задание

Ограничение времени	3 секунды
Ограничение памяти	256 МБ

Условие

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

Девочка Лиза смогла смогла получить доступ к секретным документам, в которых описан принцип работы этого алгоритма. Пусть вам понадобилось сжать целое положительное число $x$.

Если $x⩽9$, алгоритм завершает работу; Число $x$ заменяется суммой своих цифр и алгоритм продолжает работу. Лиза быстро освоила эту технологию и научилась сжимать небольшие числа. Жаль, но на практике шумерам часто приходилось сжимать число, равное произведению последовательных целых чисел от $l$ до $r$, то есть $l⋅(l+1)⋅…⋅(r−1)⋅r$.

Помогите Лизе ответить на $m$ запросов сжатия такого типа.

Формат входных данных

В первой строке дано целое число $q (1⩽q⩽2⋅10^5)$ — количество запросов на сжатие.

В следующих $q$ строках даны целые числа $l_i,r_i (1⩽l_i ⩽r_i ⩽10 ^ 9)$ — описание запросов.

Формат выходных данных

Выведите $q$ целых чисел $c_i (1⩽c_i ⩽9)$, в $i$-й строке выведите ответ на $i$-й запрос.

Замечание

Рассмотрим некоторые запросы первого теста.

1. $4⋅5=20→2+0=2$
2. $13⋅14⋅15=2730→2+7+3+0=12→1+2=3$
3. $1⋅2⋅3⋅4⋅5=120→1+2+0=3$
4. $2⋅3⋅4⋅5⋅6⋅7⋅8=40320→4+0+3+2+0→9$

Примеры данных

Ввод

8
4 5
13 15
1 5
2 8
3 3
4 6
5 11
19 19

Вывод

2
3
3
9
3
3
9
1

5 задание

Ограничение времени	3 секунды
Ограничение памяти	256 МБ

Условие

Величайший шумерский царь Гильгамеш любил дорогих лошадей. Однажды он устроил ярмарку, на которую были приглашены $n$ именитых конезаводчиков. Каждый конезаводчик пригнал табун, состоящий из некоторого количества лошадей, каждая из которых относится к типу «a» или «b» или «c». Царь Гильгамеш купит несколько табунов для своей конюшни. Каждый табун можно купить не более одного раза и необходимо купить хотя бы один табун.

Лошади разных типов отличаются окраской и повадками. Обозначим за  $n_i$ количество лошадей типа $i$ в конюшне. Назовём уродством конюшни величину  $max(n_a,n_b ,n_c)−min(n_a,n_b ,n_c)$, то есть разность количеств самого частого и самого редкого типа лошадей. Назовём силой конюшни величину $n_a+n_b+n_c$, то есть количество лошадей в конюшне. Например, если конюшня состоит из табунов «abcccca» и «babb», её уродство составит $max(1+2,1+3,4+0)−min(1+2,1+3,4+0)=4−3=1$.

Царь Гильгамеш старался минимизировать уродство своей конюшни. Из конюшен с одинаковым уродством он выбирал конюшню с максимальной силой.

Лиза заполучила секретные документы с описанием $n$ табунов и хочет вообразить себя Гильгамешем. Помогите девочке выбрать табуны, которые она возьмёт в свою конюшню, чтобы при минимальном уродстве конюшни, её сила была максимальна.

Формат входных данных

В первой строке дано целое число $n (1⩽n⩽300)$ — количество табунов на ярмарке.

В следующих $n$ строках даны строки $s_i$, состоящие из букв «a», «b», «c» — описание табунов. Гарантируется, что суммарная длина строк не превосходит $500$.

Формат выходных данных

Выведите единственное целое число — максимально возможную силу при минимально возможном уродстве царской конюшни.

Примеры данных

Пример 1

Ввод

2
abcccca
babb

Вывод

11

Пример 2

Ввод

5
aaa
aba
ccccc
bbbbbbbb
bbbb

Вывод

15

Пример 3

Ввод

5
babccba
abcca
ababaaaabbbbcc
abcaaaccbb
ababbbba

Вывод

12