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
Some observations:
As $$$n$$$ increases, the answer is non-decreasing.
For $$$n = 999999998$$$, there are only $$$568,725$$$ distinct $$$S(x)$$$ values.
So we can record the positions where new $$$S(x)$$$ appears as $$$x$$$ increases(call this sequence 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$$$ characters,and now its too long.(about $$$5$$$ MB)
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 store B as $$$[[value, count], [value, count]..]$$$.
For example the top $$$4$$$ elemnts of B are $$$[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 map them via a dict (C++ unordered_map).
Finally, the size of my solution file becomes 59KB(60k+ characters), and it can be submitted!
Here is the generate code(it is used to generate a solution file，takes about 20 minutes) :
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("# Generator Author:FZANOTFOUND",file=f)
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)
