A. Ясно, что почти для любой строки ответ Yes. Чтобы ответ был No нужно чтобы либо какие-то два соседних сдвига были равны (тогда строка должна состоять из одной и той же буквы), либо чтобы были равны любые два сдвига через 1 (тогда строка имеет вид (xy)^n) B. Генерируем все простые числа до 1000000 решетом Ератосфена, затем для каждого проверяем подходит ли он в качестве x C. Посчитаем динамику с квадратом состояний, в состоянии хранится, что удаляется из подстроки от i-го до j-го символа. Переход делается за O(1) от пары (i,j) к (i, j+1), тк выкидываемая строка может быть другой только если в нее входит j+1 буква (и она последняя), а для каждой буквы мы будем хранить ее самое правое вхождение в подстроку и сразу знать, где начинается тяжелая строка кончающаяся в j+1. D. Ясно, что внутри любой сильносвязной компоненты у всех вершин должен быть одинаковый номер. Поэтому сначала нужно сконденсировать граф и топологически отсортировать то, что получилось. Теперь решаем задачу отдельно для каждой компоненты связности. Перебираем стартовую точку и действуем в этих условиях жадно, идем бфсом, но при помечании новой вершины всех непомеченных предков уже помеченной вершины метим тем же индексом. Непомеченного потомка в бфс метим индексом на 1 больше. E. Действуем пошагово - на каждом шаге отрезаем от всех остальных точек самую левую из всех самых верхних точек почти горизонтальной прямой (чтобы какие-то очень левые точки не помешали) F. Для каждой подстрочки считаем ее хэш и ее хэш если ее пореверсить (все за O(n^2)). Теперь для каждой подстрочки, если она влезает k раз длину слова просто за O(k) проверяем хэшами, является ли она началом k-линдрома G. Для ближайшей окрестности точек 10 на 10 надо подсчитать расстояния поиском в ширину, дальше перебираем эти точки, идем в них кратчаший путем, а потом идем в конечную точку жадной эвристикой (если можем уменьшить обе координаты, то обе уменьшаем, если можем только одну, то уменьшаем большую) H. Если дано всего одно число, то надо увеличить его на один и разбить ее на наиболее равномерное разбиение. Количество слагаемых в нем t=n/k все они отличаются максимум на 1, меньшее равно n/t. Если чисел хотя бы два, то нужно перебором найти минимальное по величине слагаемое, которое можно увеличить на один так, чтобы то, что идет за ним все равно разбивалось на слагаемые I. Вначале надо найти все маленькие простые с помощью решета Эратосфена, соответственно маленькие ответы проверяются втупую перебором. Все большие ответы должны удовлетворять условию того, что по модулям небольшого количества простых (6-8) они могут принимать некоторое ограниченное количество остатков (такое, что они сами и если к ним прибавить a[i] на эти простые не делятся). Все возможные варианты легко запараметризовать тем, какие остатки ответ может принимать по модулю 2*3*5*7*11*13*17 (тут количество простых варируется, надо брать не много и не мало). Далее будем перебирать все варианты пока не найдем ответ, но идти будем только по этим хорошим остаткам. Чтобы проверять ответ нужно уметь проверять большие числа на простоту - это можно делать Рабином-Миллером или даже за корень (но в этом случае надо проверять на делимость сразу все числа x,x+a[1],x+a[2]... Это можно сделать поискав среди них минус остаток x по модулю проверяемого простого). Доказывать такие вещи очень сложно, тут надо просто пробовать разные варианты.
Были еще решения с прекальками, но там надо было либо хорошо отсекать, либо уметь сжимать захардкоженый массив каким-нибудь кодированием. Я видел, что кто-то обощелся 16-ричной системой счисления. J. Ясно, что каждая из прямых в ответе делит многоугольник на две равновеликие части. Заметим, что среди прямых параллельных одному направлению найдется только одна делящая многоугольник на две равные части. Если взять такую в каком-то направлении и в перпендикулярном, то картинка всех 4 пересечений будет выглядеть так: A|B --- B|A По сути на надо найти такое направление, что A=B. Ясно, что можно искать его от нуля до pi/2, причем видно, что разность A-B на концах этого отрезка противоположена по знаку (они просто меняются местами). Эта функция может быть не монотонной по углу, но непрерывной быть обязана. Поэтому просто будем бить отрезок бинпоиском, поддерживая условие противоположенности знаков на концах. Тогда всегда внутри нашего отрезка будет какой-то ноль и мы к нему сойдемся. Остается рассказать, как искать для одного направления равновеликую прямую. Говорят, что тут даже бинпоиск заходит, но можно сделать это и за nlog n. Сортируем вершины, проводим через них параллельные прямые, они делят многоугольник на трапеции. Идем справа налево, прибавляем трапеции пока площадь не станет больше половины. Тогда последнюю рапецию делим ровно там где надо, можно посчитать это аналитически. K. В этой задаче заходил рекурсивный перебор с отсечением по ответу. Доказывать я не умею. У авторов написана какая-то жесть с масками, причем часть действий явно делается жадно. Если пойму, то напишу.
