AtCoder 原图名称已被搁置;此后,原始图像取自英语原文,现已完整保存。

可复制的 PDF 提取文本
Gennady Korotkevich Contest 1
Petrozavodsk Training Camp, Day 1, Friday, August 23, 2013
Problem D. Degree Of Number's Eccentricity
Input le: done.in
Output le: done.out
Time limit: 2 seconds
Memory limit: 256 megabytes
Do you think that being eccentric is easy? This is not the case when you're a number.
The degree of eccentricity of a 2N-digit integer X (possibly with leading zeroes) is de ned as the
smallest possible value of |a + b −10N| for some N-digit integers a and b (again, possibly with
leading zeroes) such that Sd(X) = Sd(a) + Sd(b) holds for every digit d, where Sd(P) (0 ≤d ≤9)
is the number of occurrences of digit d in the decimal representation of P. For example, the degree
of eccentricity of amusing numbers (see problem Counting Amusing Numbers) is equal to 0, while
the degree of eccentricity of 192747 is equal to 7 (|274 + 719 −1000| = 7).
You are given a bunch of numbers of even lengths. Find the degree of eccentricity of each of them.
Input
The rst line of the input le contains the number of test cases T (1 ≤T ≤1000). Each of the
next T lines contains an integer number of an even length (possibly with leading zeroes). The
total length of all numbers in the input le (except T) doesn't exceed 106.
Output
For each test case, output one line containing the degree of eccentricity of the corresponding
number in the input le.
Examples
done.in done.out
3 0
9820 7
192747 900
000001
Page 4 of 10