**This is old solution**, completely new 6 bajillion times faster solution is on the bottom.

Solution:

```
time { python solution.py; }
0: 0
1: 199990
2: 1999919999999980
3: 19999199999999919999999970
4: 199991999999999199999999919999999960
5: 1999919999999991999999999199999999919999999950
6: 19999199999999919999999991999999999199999999919999999940
7: 199991999999999199999999919999999991999999999199999999919999999930
8: 1999919999999991999999999199999999919999999991999999999199999999919999999920
9: 19999199999999919999999991999999999199999999919999999991999999999199999999919999999918
real 1m53.493s
user 1m53.183s
sys 0m0.036s
```

Code:

```
OPTIMIZE_1 = True # we assum that '1' will run out first (It's easy to prove anyway)
if OPTIMIZE_1:
NUMBERS = [1]
else:
NUMBERS = range(10)
def how_many_have(dight, n, stickers):
return stickers * n
cache = {}
def how_many_used(dight, n):
if (dight, n) in cache:
return cache[(dight,n)]
result = 0
if dight == "0":
if OPTIMIZE_1:
return 0
else:
assert(False)
#TODO
else:
if int(n) >= 10:
if n[0] == dight:
result += int(n[1:]) + 1
result += how_many_used(dight, str(int(n[1:])))
result += how_many_used(dight, str(int(str(int(n[0])-1) + "9"*(len(n) - 1))))
else:
result += 1 if n >= dight else 0
if n.endswith("9" * (len(n)-4)): # '4' constant was pick out based on preformence tests
cache[(dight, n)] = result
return result
def best_jump(i, stickers_left):
no_of_dights = len(str(i))
return max(1, min(
stickers_left / no_of_dights,
10 ** no_of_dights - i - 1,
))
def solve(stickers):
i = 0
stickers_left = 0
while stickers_left >= 0:
i += best_jump(i, stickers_left)
stickers_left = min(map(
lambda x: how_many_have(x, i, stickers) - how_many_used(str(x), str(i)),
NUMBERS
))
return i - 1
for stickers in range(10):
print '%d: %d' % (stickers, solve(stickers))
```

Prove that '1' will run out first:

```
def(number, position):
""" when number[position] is const, this function is injection """
if number[position] > "1":
return (position, number[:position]+"1"+number[position+1:])
else:
return (position, str(int(number[:position])-1)+"1"+number[position+1:])
```