Tips: this is not a normal solution of 2104F - Numbers and Strings, it's just for fun.If you want to know how to normally solve it,please see others solutions. :)

My submission:317717480

In this problem, we can know that when n is increasing, the answer is non-decreasing. And you can find there is only 568725 diffent strings when n = 999999998.

So we can record when a new S(x) appears when x increases(named as sequnce**A**).Then we can use binary search to find the answer.

Here is the top 300 numbers of A

But codefoces's limit of the length of a code if 65535,and now its too long.(about 5MB)

We can notice that many of the numbers are continuous increasing(as 1, 2, 3, 4), so I made another sequence B that B_{i} = A_{i+1} — A_{i}. And B becomes [1, 1, 1, 1....10, 1, 1, 1...]. So we can record B as [[number, times], [number, times]..](Here number denotes to the continuous appear number in B ,and times denoted to the appear times).

Here is the top 4 numbers of B: [1,209],[10,1],[1,90],[10,2].

Unfortunately, the code is still too long. We need to still work on it.(about 470KB or maybe 200KB, I can't remember the exact size)

You can try the previous steps, and surprisingly you will find there is only 122 different elements in B.

So we can use 122 different characters to replace the elements of B,and use a dict(means unorded_map in c++) to record it.

Finally, my solution file becomes 59KB(60k+ characters), and it can be submitted!

Here is the generate code: py import os os.chdir(os.path.dirname(os.path.abspath(__file__))) ans = [0] memo = set() maxn = 10**9 pre = 0 for i in range(1, maxn-1): # find all number i where a new S(i) appear now = "".join(sorted(str(i) + str(i+1))) if now not in memo: ans.append(i-pre) # a[i] - a[i-1] memo.add(now) pre = i ans.append(maxn-pre) # add the last for binary search def zzip(ans): # transform [1,1,1,1,1,1,1,2] into [[1,7],[2,1]] res = [[0, 1]] for i in range(1, len(ans)): if ans[i] != ans[i-1]: res.append([ans[i], 1]) else: res[-1][1] += 1 return res def chrr(i): #tranform a number into a char if i < 60: ch = chr(i + 32) elif i < 94: ch = chr(i + 33) else: ch = chr(i + 100) return ch def szip(ans): # transform [[1,7],[2,1]] into memo: {'!':[1,7],'"':[2,1]} and s: !" res = [] memo = {} memo2 = {} idx = 0 for i in ans: if tuple(i) not in memo: memo[tuple(i)] = chrr(idx+1) memo2[chrr(idx+1)] = i idx += 1 res.append(memo[tuple(i)]) return memo2, "".join(res) memo2, res = szip(zzip(ans)) with open("Fgenerated.py", "w", encoding='utf-8') as f: # write into the solution file print("s=", "'''",res,"'''", file = f, sep='') print("memo=", str(memo2).replace(": ", ":").replace(", ",","), file=f, sep='') print("""from bisect import bisect_right ans=[0] for i in range(1,len(s)): for _ in range(memo[s[i]][1]):ans.append(ans[-1]+memo[s[i]][0]) for _ in range(int(input())):print(bisect_right(ans,int(input()))-1)""", file=f)