Бамп

>>140370679 (OP)
а пока у ОПа неведомая хуйня с трубой мы будем решать тут задачу.

A KMP algorithm takes a string, S, of length N as input. Let's assume that the characters in S are indexed from 1 to N; for every prefix of S, the algorithm calculates the length of its longest valid border in linear complexity. In other words, for every i (where 1<= i <= N) it calculates the largest l (where 0 <= l <= i-1) such that for every p (where 1 <= p <= l) there is S[p]=S[i-l+p].

Given a sequence x1,..x26, construct a string, S, that meets the following conditions:

1.The frequency of letter 'a' in is exactly x1, the frequency of letter 'b' in is exactly x2, and so on.
2. Let's assume characters of S are numbered from 1 to N, where sum x=N. We apply the KMP algorithm to S and get a table, kmp, of size N. You must ensure that the sum of kmp for all i is minimal.

If there are multiple strings which fulfill the above conditions, print the lexicographically smallest one.

как можно заметить, в этой задаче берутся все префиксы p для S, каждого из них берется r такая что r и префикс p и суффикс. и считается sum len(r).

что это означает. во-первых это означает, что часть ответа, которая зависит от префикса S зависит только от него. то есть это выглядит как
заход на перебор, если бы нас не ждал комбинаторный взрыв в тестах.

попробуем частные случаи. для строк из одной буквы получаем
x 0... => x(x-1)/2.
для строк из двух букв вырисовывается формула
1 2 3 4 5
1 0 0 0 0 0
2 0 1 1 1 1
3 0 1 2 2 2
4 0 1 2 3 3
5 0 1 2 3 4
x y => min(x,y)-1

>>140372341
гипотеза: если x не равно нулю больше одного, то min(sum(kmp)) = min(x)-1

Макару привет

>>140372984
во-первых, надо взять меньшую букву из меньше всех встречающихся букв. она будет первой, а все оставшиеся ее вхождения в S будут давать единицы в kmp.
во-вторых, остальные буквы надо отсортировать по алфавиту и приконкатить к этой первой букве.

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

>>140373932
для первой буквы хорошо то, что вторая первая буква идет рядом с первой, а все остальные через одну - в этом случае в kmp значение получается ровно 1, т.к. нигде не будет суффикса из двух подряд первых букв. а это уже выглядит как решение.

норм, решение прошло тесты.

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

>>140370679 (OP)
Х значит хуй, попробуй нажать, чтобы победить

>>140370679 (OP)
бочку уже делал?
хуйцы сосал?