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 < 1015).
Output
Print expected minimal number of digits 1.
Examples
input
121
output
6
Solution:
import java.lang.Math.abs private fun readLn() = readLine()!! // string line private fun readInt() = readLn().toInt() // single int private fun readLong() = readLn().toLong() // single long private fun readDouble() = readLn().toDouble() // single double private fun readStrings() = readLn().split(" ") // list of strings private fun readInts() = readStrings().map { it.toInt() } // list of ints private fun readLongs() = readStrings().map { it.toLong() } // list of longs private fun readDoubles() = readStrings().map { it.toDouble() } // list of doubles fun main(args: Array<String>) { var s = readLn().reversed() + "000" var len = s.length val MAX = 200 var dp = Array(len + 1, { Array(2 * MAX, { IntArray(2 * MAX, { 12345 }) }) }) dp[0][MAX][MAX] = 0 for (i in 0..len - 1) { for (cur in -MAX..MAX-1) { for (carry in -MAX..MAX-1) { var ft = dp[i][cur + MAX][carry + MAX] if (ft == 12345) { continue } for (delta in -100..100) { var newCur = cur + delta var here = newCur + carry var value = (here % 10 + 10) % 10 if (value != s[i] - '0') { continue } var newCarry = (here - value) / 10 var newFt = ft + abs(delta) * i if (newCur >= -MAX && newCur < MAX && newCarry >= -MAX && newCarry < MAX && newFt < dp[i + 1][newCur + MAX][newCarry + MAX]) { dp[i + 1][newCur + MAX][newCarry + MAX] = newFt } } } } } println(dp[len][MAX][MAX]) }
Related posts:
Factorial modulo $p$
Useful Decomposition
Nastya and Unexpected Guest
Optimal Subsequences (Easy Version)
Quantifier Question
D´Esopo-Pape algorithm
Pudding Monsters
New Year Book Reading
Yash And Trees
Generate a String
Delivery Club
World Eater Brothers
Tổng hợp các bài toán duyệt với gợi ý lời giải
Simple Skewness
Convex Hull construction using Graham's Scan
Bear and Destroying Subtrees
Chicken or Fish?
The Evil Temple and the Moving Rocks
Level Statistics
Circle of Numbers
Good Subsets
Cube Problem
Work Group
Solving assignment problem using min-cost-flow
Mentors
Second price auction
Casinos and travel
Yuhao and a Parenthesis
Points on Line
New Year and Cake
Cinema
PolandBall and Forest