Prof. Vasechkin wants to represent positive integer n as a sum of addends, where each addends is an integer number containing only 1s. For example, he can represent 121 as 121=111+11+–1. Help him to find the least number of digits 1 in such sum.


-----Input-----

The first line of the input contains integer n (1 ≤ n < 10^15).


-----Output-----

Print expected minimal number of digits 1.


-----Examples-----
Input
121

Output
6

Difficulty: MEDIUM_HARD
Tags: Complete search

Graph traversal

Divide and conquer
Skill types: Complete search

Starter code:

Solutions:
n = int(input())
d = {n: 0}
u = 10 ** (len(str(n)) + 2) // 9
for i in range(len(str(n)) + 1, 0, -1):
	(d, e) = ({}, d)
	u //= 10
	for (v, c) in list(e.items()):
		lim = v // u
		for x in range(-1 - lim, 1 - lim):
			t = v + x * u
			d[t] = min(c + i * abs(x), d.get(t, 999))
print(d[0])


import math
acc = []
n = int(input())

def OneNum(num, One):
	onetrans = num // acc[One]
	num = num % acc[One]
	if num == 0:
		return onetrans * One
	else:
		return onetrans * One + min(OneNum(num, One - 1), One + OneNum(acc[One] - num, One - 1))
acc.append(0)
for i in range(1, 17):
	acc.append(acc[i - 1] * 10 + 1)
print(OneNum(n, 16))


import math

def find(n, i):
	ans = 0
	k = n // ones[i]
	n = n % ones[i]
	ans = ans + k * i
	if n == 0:
		return ans
	return ans + min(find(n, i - 1), i + find(ones[i] - n, i - 1))
n = int(input())
ones = [0]
for i in range(1, 17):
	one = 10 * ones[i - 1] + 1
	ones.append(one)
print(find(n, 16))


multiplos_de_onze = [0, 1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111, 11111111111, 111111111111, 1111111111111, 11111111111111, 111111111111111, 1111111111111111, 11111111111111111]

def procura_onze(n, i):
	divisao = int(n / multiplos_de_onze[i])
	resto = n % multiplos_de_onze[i]
	if resto == 0:
		return divisao * i
	else:
		return divisao * i + min(i + procura_onze(multiplos_de_onze[i] - resto, i - 1), procura_onze(resto, i - 1))

def divide():
	n = int(input())
	m = procura_onze(n, 16)
	print(m)
divide()


n = int(input())
d = {}

def count(x):
	if x == 0:
		return 0
	elif x in d:
		return d[x]
	x_s = str(x)
	low = int('1' * len(x_s)) if int('1' * len(x_s)) <= x else int('1' * (len(x_s) - 1))
	high = int('1' * len(x_s)) if int('1' * len(x_s)) >= x else int('1' * (len(x_s) + 1))
	(l_val, h_val) = (-1, -1)
	if abs(x - low) < x:
		l_val = len(str(low)) + count(abs(x - low))
	if abs(x - high) < x:
		h_val = len(str(high)) + count(abs(x - high))
	ret = min(l_val, h_val) if min(l_val, h_val) >= 0 else max(l_val, h_val)
	d[x] = ret
	return ret
print(count(n))


one = []
for i in range(17):
	one.append(0)

def code():
	i = 1
	j = 0
	k = 0
	one[0] = 0
	for i in range(1, 17):
		one[i] = one[i - 1] * 10 + 1
	n = int(input())
	print(df(n, 16))

def df(n, i):
	k = int(n / one[i])
	n %= one[i]
	if n == 0:
		return k * i
	else:
		return k * i + min(i + df(one[i] - n, i - 1), df(n, i - 1))
code()


ans = 1000000000000
mul = []

def dfs(now, num, opt):
	if num == 0:
		global ans
		ans = min(ans, opt)
		return
	if now == -1:
		return
	i = -10
	while i * mul[now] <= num:
		i += 1
	dfs(now - 1, num - (i - 1) * mul[now], opt + abs(i - 1) * (now + 1))
	dfs(now - 1, num - i * mul[now], opt + abs(i) * (now + 1))

def main():
	mul.append(int(1))
	num = int(input())
	for i in range(1, 18, 1):
		mul.append(mul[i - 1] * 10)
	for i in range(1, 18, 1):
		mul[i] += mul[i - 1]
	i = 1
	while mul[i] <= num:
		i += 1
	n = i
	dfs(n, num, 0)
	print(ans)
main()


class OneArithmetic:

	def __init__(self, n):
		self.n = n
		self.m = [0] * 17
		v = 0
		for i in range(1, 17):
			v = 10 * v + 1
			self.m[i] = v

	def dfs(self, v, d):
		v = abs(v)
		if d == 1:
			return v
		elif v == 0:
			return 0
		else:
			k = int(v / self.m[d])
			ans = min(self.dfs(v - k * self.m[d], d - 1) + k * d, self.dfs((k + 1) * self.m[d] - v, d - 1) + (k + 1) * d)
			return ans

	def min_digits(self):
		v = self.dfs(self.n, 16)
		return v
n = int(input())
print(OneArithmetic(n).min_digits())


def read(mode=2):
	inputs = input().strip()
	if mode == 0:
		return inputs
	if mode == 1:
		return inputs.split()
	if mode == 2:
		return [int(x) for x in inputs.split()]

def write(s='\n'):
	if isinstance(s, list):
		s = ' '.join(s)
	s = str(s)
	print(s, end='')

def g(n):
	return (10 ** n - 1) // 9

def solve(n):
	if n <= 6:
		return n
	if 7 <= n <= 11:
		return 13 - n
	l = 1
	while g(l) < n:
		l += 1
	l -= 1
	gl = g(l)
	a = n
	res1 = 0
	res1 += a // gl * l
	a %= gl
	res1 += solve(a)
	b = g(l + 1) - n
	res2 = l + 1
	res2 += b // gl * l
	b %= gl
	res2 += solve(b)
	return min(res1, res2)
(n,) = read()
print(solve(n))