Mock CCC '18 Contest 1 S5 - A Palindrome Problem

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 2.5s
Python 4.5s
Memory limit: 1G

Problem type

Given a string of digits, define an operation to be incrementing some digit in the string. Increasing any digit that is not nine increases it by one. Increasing nine switches it to zero and also automatically increases the digit to its left, if any such digit exists, which may cascade and cause digits to its left to also be incremented, but these automatic increases are considered part of the original operation.

Given a string of digits, compute the minimum number of operations needed to make the string a palindrome.

Constraints

1 \le |S| \le 40

Input Specification

The input consists of a single line containing the string S.

Output Specification

Print, on a single line, the minimum number of operations needed to make the string a palindrome.

Sample Input 1

0

Sample Output 1

0

Sample Input 2

009990001

Sample Output 2

3

Sample Input 3

9084194700940903797191718247801197019268

Sample Output 3

54

Comments

There are no comments at the moment.