вроде да, ну вершин 1000, видимо можно

UPD: int operator+ (int a, int b){return a*b;}

12 = 2² + 3 — следовательно нужна перестановка с двумя циклами: длинны 2² = 4 и 3 соответственно. Я просто написал криво %)

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

12 = 2^2*3^1 Соответственно, наша шаффл машина будет работать для 2^2+3^1=7 карт и реализовывать два непересекающихся цикла с длинами 4 и 3, то есть ответ будет, например, "2 3 4 1 6 7 5". Первые 4 карты возвращаются на свои места каждые 4 перемешивания, вторые три карты — каждые три перемешивания, вся система возвращается в исходное положение за НОК(4, 3)=12 шагов, что и требовалось построить.

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

Пусть какой-то цикл имеет непростую длинну a*b. Если мы сделаем два цикла длинны a и b (a и b — взаимно простые), то a+b<a*b (т.к.2<=a<b) и данная перестановка будет переходить в себя с периодом НОК(a,b) = a*b итераций. Поэтому выгодно разбить на простые.

Да, перепутал. Исправлено

Можно написать вполне аккуратно. Посортим вершины по их глубине и начнем обрабатывать в порядке ее уменьшения. Заметим, что вершина на которую мы сейчас смотрим, если она не покрашена, будет яляться листом. И тогда покрасим ее предка(если он есть)

Well, it doesn't explicitly say it, but it says that Kostya is afraid of the page's number, and it is written on the page between 12 and 14, labeled "!#". This is what made it clear to me.

Legend:

he is afraid of this page's number

Output format:

minimal number of symbols that should be removed from the text such that Kostya's unpleasant number will not occur in it as a substring

And my Foxit PDF reader doesn't show the page number until I drag to the end of the page, which I have never done before :(. I always use my keyboard to scroll up/down or turn the page, which doesn't show the page number. Maybe next time I should prepare against Russian joke.

Ее можно и без хешей довольно просто решить (см. ниже)

Точно, что-то не подумал.. Ну ладно, напишу бор. Обидно, что во время тренировки вообще на неё не посмотрел.

У меня решение за O(n*26*10*10). Для каждой строки перебираем все варианты замены символа и ищем получившуюся строку в боре. Вроде просто пишется.

Фигней с хешами.

можно было в хэш-таблицу хэши складывать.

да вроде все таки m*2^n — m тестов, n задач, перебираем маску и смотрим для каждой из m задач, что все хорошо

P.S. жирный текст, что-то не отображается

Usually, when you factor a number, you check all divisors up to square root of this number. In this problem you need only check divisors not greater than 10⁵ — because if factorization of K contains prime number greater than 10⁵, sum of numbers in factorization is surely too large.