''' Copyright (c) 2019 Serguei Zolotov This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. ''' import math def counter(astr, N): n = len(astr) Q = int(N * (N + 1) / 2) dX = [0] * (n - N) if n > N: dX[0] = 1 for e in astr[N + 1:]: if e == 'a': dX[0] += 1 else: break l = N r = l - 1 for i in range(N + 1, n): u = 1 if i <= r: u = min(dX[l + r - i - N], r - i + 1) while i - u >= 0 and i + u < n and astr[i - u] == astr[i + u]: u += 1 dX[i - N] = u if i + u - 1 > r: l = i - u + 1 r = i + u - 1 Q = Q + sum(dX) dX = [0] * (n - N) l = N r = l - 1 for i in range(N + 1, n): u = 0 if i <= r: u = min(dX[l + r - i + 1 - N], r - i + 1) while i - u - 1 >= 0 and i + u < n and astr[i - u - 1] == astr[i + u]: u += 1 dX[i - N] = u if i + u - 1 > r: l = i - u r = i + u - 1 Q = Q + sum(dX) return Q def getnextstring(astr, N): l = len(astr) for k in range(l): p = l - k - 1 o = astr[p] if o in astr[0:p]: astr = astr[0:p] + chr(ord(o) + 1) + astr[p + 1:] break astr = astr[0:p] + 'a' + astr[p + 1:] N = min(N, p) return astr, N def buildcloseststring(k): N = int(math.sqrt(2 * k)) while (N * (N + 1) / 2 > k): N = N - 1 mstr = 'a' * N r = k - int(N * (N + 1) / 2) if r > 0: Q = int(math.sqrt(2 * r)) while (Q * (Q + 3) // 2 > r): Q = Q - 1 mstr = mstr + 'b' + 'a' * Q return mstr, N # Complete the solve function below. def calculate(k): mstr, N = buildcloseststring(k) while (True): ret = counter(mstr, N) if (ret == k): break elif (ret < k): mstr = mstr + 'a' if N == len(mstr) + 1: N = N + 1 else: mstr, N = getnextstring(mstr, N) return len(mstr), mstr if __name__ == '__main__': # open output files fb = open("b340458.txt",'w') fa = open("a340458.txt",'w') # loop through boundaries for n in range(1, 5001): num, mstr = calculate(n) print ("%d %d"%(n, num), file=fb) print ("%d %d %s"%(n, num, mstr), file=fa) # close output fb.close() fa.close()