Крош и Ёжик собрали для Совуньи $$$n$$$ грибов. Для их засолки Совунья подготовила $$$k$$$ банок и хочет разложить грибы поровну в каждую из них.
К сожалению, количество собранных грибов $$$n$$$ может не делиться нацело на число банок $$$k$$$. Совунья не хочет выбрасывать грибы, поэтому просит Кроша и Ёжика принести ещё немного. Однако, чтобы не перетруждать друзей, она хочет попросить как можно меньше дополнительных грибов.
В первой строке входных данных вводится число $$$1 \le n \le 10^9$$$ — количество грибов, которые принесли Крош и Ёжик.
Во второй строке входных данных вводится число $$$1 \le k \le 10^9$$$ — количество банок, которые подготовила Совунья.
Выведите минимальное количество грибов, которое Совунье надо попросить у своих друзей, чтобы можно было разложить грибы по банкам поровну.
В задаче $$$20$$$ тестов, каждый из которых оценивается в $$$5$$$ баллов.
Решения, корректно работающие для $$$1 \le n, k \le 10^5$$$, получат не менее $$$50$$$ баллов.
34
1
75
3
В первом тесте Ёжик и Крош принесли $$$3$$$ гриба. У Совуньи $$$4$$$ банки. Совунье надо попросить $$$1$$$ гриб, тогда суммарно грибов станет $$$4$$$, и она сможет в каждую банку положить $$$1$$$ гриб.
Во втором тесте Крош и Ёжик принесли Совунье $$$7$$$ грибов, у неё есть $$$5$$$ банок. Ей необходимо попросить ещё $$$3$$$ гриба, тогда всего грибов будет $$$10$$$, и она сможет положить в каждую банку по $$$2$$$ гриба.
Пин, гениальный изобретатель из Ромашковой долины, снова что-то мастерит. На этот раз он создал новый механизм для Биби и назвал его «Числовые шестерёнки». Сердце механизма — две пары шестерёнок, которые нужно соединить особым образом. Пин экспериментальным путём выяснил, что механизм запустится, если у двух соединённых пар совпадают их гармонические числа.
У Пина есть четыре шестерёнки, на каждой из которых написано одно число: на первой шестерёнке — $$$a$$$, на второй — $$$b$$$, на третьей — $$$c$$$ и на четвёртой — $$$d$$$.
Гармоническое число упорядоченной пары шестерёнок $$$(x, y)$$$ (где $$$y \neq 0)$$$ — это остаток от деления $$$x$$$ на $$$y$$$. Например, для пары $$$(7, 3)$$$ гармоническое число равно $$$1$$$, так как $$$7 \bmod 3 = 1$$$.
Порядок в паре важен: для пары $$$(7, 3)$$$ гармоническое число равно $$$1$$$, а для пары $$$(3, 7)$$$ — $$$3$$$.
Помогите Пину понять, сможет ли он запустить механизм, используя эти четыре шестерёнки.
В четырёх строках вводятся числа $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ ($$$0 \le a, b, c, d \le 10^9$$$) — числа на шестерёнках Пина.
Если возможно соединить шестерёнки, выведите две строки. В каждой строке — два числа (в нужном порядке), образующие пары с одинаковыми гармоническими числами.
Если запустить механизм невозможно, выведите $$$-1$$$.
Если решений несколько, можно вывести любое.
Оценка складывается из баллов за пройденные тесты. За каждый правильно пройденный тест вы получаете $$$2$$$ балла.
7 5 3 9
9 7 5 3
2322
-1
В первом примере для первой пары гармоническое число $$$9 \bmod 7 = 2$$$.
Для второй пары — $$$5 \bmod 3 = 2$$$.
Два гармонических числа совпадают, значит, механизм можно запустить.
Во время очередной экспедиции в пустыню Крош и Ёжик наткнулись на загадочную глиняную табличку, покрытую древними знаками. Поверхность таблички была аккуратно расчерчена на сетку из $$$N$$$ строк и $$$M$$$ столбцов. Некоторые клетки таблицы были закрашены. Друзья догадались, что каждый прямоугольник $$$5 \times 3$$$ может скрывать какую-то цифру от $$$0$$$ до $$$9$$$. Пример представления цифр (звёздочки обозначают закрашенные клетки, а точки — незакрашенные):
0: *** 1: ..* 2: *** 3: *** 4: *.*
*.* ..* ..* ..* *.*
*.* ..* *** *** ***
*.* ..* *.. ..* ..*
*** ..* *** *** ..*
5: *** 6: *** 7: *** 8: *** 9: ***
*.. *.. ..* *.* *.*
*** *** ..* *** ***
..* *.* ..* *.* ..*
*** *** ..* *** ***
Но, как это часто бывает с древними артефактами, всё оказалось не так просто! Похоже, авторы таблички (возможно, шумеры, а может, просто очень взволнованный кактус) в спешке закрасили лишние клетки.
Крош и Ёжик подумали и решили, что прямоугольник $$$5\times 3$$$ содержит цифру $$$d$$$, если все клетки, которые должны быть закрашены у цифры $$$d$$$, действительно закрашены на табличке. А если где-то добавились лишние звёздочки — ничего страшного! Главное, чтобы ничего не пропало.
Например, прямоугольник:
***
.**
***
**.
***
А что, если прямоугольник подходит сразу под несколько цифр? Тогда выберем самую большую! — решили Крош и Ёжик. Например, прямоугольник:
***
***
***
..*
***
подходит и под $$$1$$$, и под $$$3$$$, и под $$$5$$$, и даже под $$$9$$$. Но поскольку $$$9$$$ — самая большая из них, именно $$$9$$$ и будет записана в ответ.
Важно! Цифры не могут быть перевернуты и всегда расположены вертикально.
Теперь друзья хотят узнать: чему равна сумма всех цифр, закодированных в табличке?
Для этого нужно рассмотреть все возможные позиции прямоугольника $$$5\times 3$$$, которые полностью помещаются в таблицу — двигая его по строкам сверху вниз и по столбцам слева направо, как будто «скользя» по поверхности. Прямоугольники могут пересекаться — это не разбиение на блоки, а именно все возможные окна размером $$$5\times 3$$$.
Если в каком-то окне не получается распознать ни одну цифру, оно просто ничего не добавляет к сумме.
Помогите Крошу и Ёжику расшифровать древнее число!
В первой строке вводится два числа $$$5 \le N \le 100$$$ и $$$3 \le M \le 100$$$.
В следующих $$$N$$$ строках вводятся строки длины $$$M$$$, состоящие из символов звездочек ('*') и точек ('.') — исходная таблица.
Выведите одно число — сумму всех цифр, закодированных в таблице.
В задаче 50 тестов, каждый оценивается на 2 балла. Тесты разбиты на 3 группы, внутри каждой группы действует потестовая оценка, то есть баллы начисляются за каждый тест независимо. Группа 3 тестируется, только если все тесты первой и второй группы были пройдены.
| Группа | Ограничения | Доп. условия | Баллы | Зависимые группы |
| $$$0$$$ | Тесты из условия | - | $$$0$$$ | |
| $$$1$$$ | $$$5 \le N \le 100$$$, $$$3 \le M \le 100$$$ | Только цифра $$$1$$$* | $$$20$$$ | |
| $$$2$$$ | $$$N = 5$$$, $$$M = 3$$$ | - | $$$40$$$ | |
| $$$3$$$ | $$$5 \le N \le 100$$$, $$$3 \le M \le 100$$$ | - | $$$40$$$ | $$$0, 1, 2$$$ |
5 3****..***..****
5
6 6.***.*.*...*.***.*.*.*.*.***.*....**
8
10 10..*.........*.....*...*.....*...*..*..*...*..*..*...*..*..*...*..*..*...*..*..*...*.....*...*.......
11
В первом примере явно закодирована цифра $$$5$$$.
Во втором примере входных данных в прямоугольнике, с левым верхним углом в клетке с координатами $$$(1,2)$$$ закодирована цифра 6. И в прямоугольниках с верхними левыми углами в координатах $$$(1,4)$$$ и $$$(2,4)$$$ закодирована цифра $$$1$$$. Сумма всех закодированных чисел равна $$$8$$$.
Во время инвентаризации в музее Кар-Карыча Смешарики нашли коробки с лентами, на которых записаны цифры. Пин предполагает, что на какой-то ленте записано Великое Тождество — равенство вида $$$a = a$$$, где $$$a$$$ — некоторое натуральное число. При этом первая запись числа $$$a$$$ не содержит ведущих нулей, а вторая может начинаться с нуля.
Со временем знак равенства стёрся, и теперь на ленте осталась только последовательность цифр. Крош утверждает, что тождество можно восстановить, если поставить знак «равно» где-то внутри найденной строки.
Помогите Смешарикам определить, можно ли восстановить Великое Тождество на каждой из найденных лент.
В первой строке дано целое число $$$N$$$ ($$$1 \le N \le 10$$$) — количество лент.
Далее следуют $$$N$$$ непустых строк, состоящих только из десятичных цифр. Гарантируется, что никакая строка не начинается с $$$0$$$. Длины строк не превышают $$$4\cdot 10^5$$$.
Выведите $$$N$$$ строк. В $$$i$$$-й строке выведите:
- номер позиции цифры, после которой следует поставить знак «равно», чтобы получилось корректное тождество;
- или $$$-1$$$, если это невозможно.
Позиции нумеруются с $$$1$$$. Если подходящих позиций несколько, выведите любую.
В задаче тесты разбиты на группы. Внутри каждой группы действует потестовая оценка, то есть баллы начисляются за каждый тест независимо. Группа 3 тестируется, только если все тесты первой и второй групп были пройдены.
| Группа | Ограничения | Баллы | Зависимые группы | Примечание |
| $$$1$$$ | $$$N = 1$$$, длины строк $$$\le 18$$$ | $$$20$$$ | 20 тестов по 1 баллу | |
| $$$2$$$ | $$$N \le 10$$$, длины строк $$$\le 1000$$$ | $$$30$$$ | 6 тестов по 5 баллов | |
| $$$3$$$ | $$$N \le 10$$$, длины строк $$$\le 10^5$$$ | $$$50$$$ | $$$1, 2$$$ | 5 тестов по 10 баллов |
3123123123122120012
3 -1 2
В первой строке получаем тождество 123=123, ответ 3.
Во второй строке поставить знак равенства невозможно.
В третьей строке тождество 12=0012, т.е. $$$12=12$$$. Ответ 2, знак равенства необходимо поставить после второй позиции в числе.
Нюша — большая модница и поклонница косметики. В её коллекции сотни баночек с пудрами, помадами и кремами. Перед каждой прогулкой с Барашем она наносит макияж, чтобы подчеркнуть свою элегантность.
Как известно любой моднице, не все косметические средства хорошо сочетаются друг с другом. Чтобы навести порядок в своей огромной коллекции, Нюша расставила всю косметику в один длинный ряд. Каждой баночке $$$i$$$ она сопоставила целое число $$$a_i$$$ — числовую характеристику её стиля.
Нюша придумала особое правило для оценки сочетаемости средств: для любого набора баночек она вычисляет так называемое магическое число — наибольший общий делитель (НОД) их числовых характеристик. Для одного средства магическое число равно самому этому числу: НОД$$$(a_i)= a_i$$$.
Поскольку ряд косметики получился очень длинным, для одного макияжа Нюша решила использовать только средства, стоящие подряд, то есть некоторый подотрезок в этом ряду. Прогулок с Барашем предстоит много, и Нюша хочет каждый раз выглядеть по-новому.
Нюша хочет рассмотреть все возможные подотрезки (все способы выбрать подряд идущие баночки), вычислить магическое число для каждого из них, а затем найти сумму всех этих магических чисел. Помогите Нюше найти это итоговое число!
Так как ответ может быть очень большим, выведите его по модулю $$$10^9+7$$$ (т.е. остаток от деления на $$$10^9+7$$$).
В первой строке находится одно целое число $$$n\ (1 \le n \le 200\ 000)$$$ — количество косметических средств.
Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — числовые характеристики стиля средств.
Выведите одно целое число — сумму магических чисел всех подотрезков по модулю $$$10^9 + 7$$$.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи | Информация о проверке |
| $$$1$$$ | $$$15$$$ | $$$n \le 50 $$$ | первая ошибка | |
| $$$2$$$ | $$$35$$$ | $$$n \le 1000$$$ | $$$1$$$ | первая ошибка |
| $$$3$$$ | $$$20$$$ | $$$n \le 50\ 000$$$ | $$$1,2$$$ | первая ошибка |
| $$$4$$$ | $$$30$$$ | — | $$$1,2,3$$$ | первая ошибка |
36 10 15
39
512 4 8 6 1
53
Массив $$$a = [6, 10, 15]$$$. Найдём сумму наибольших общих делителей для всех подотрезков.
- Подотрезки длины 1:
- $$$[6]$$$ $$$\rightarrow$$$ НОД = $$$6$$$;
- $$$[10]$$$ $$$\rightarrow$$$ НОД = $$$10$$$;
- $$$[15]$$$ $$$\rightarrow$$$ НОД = $$$15$$$.
- Подотрезки длины 2:
- $$$[6, 10]$$$ $$$\rightarrow$$$ НОД$$$(6, 10) = 2$$$;
- $$$[10, 15]$$$ $$$\rightarrow$$$ НОД$$$(10, 15) = 5$$$.
- Подотрезки длины 3:
- $$$[6, 10, 15]$$$ $$$\rightarrow$$$ НОД$$$(6, 10, 15) =$$$ НОД$$$(2, 15) = 1$$$.
Общая сумма: $$$6 + 10 + 15 + 2 + 5 + 1 = 39$$$.