← 返回题目列表

AtCoder · icpc2015summer_day3_d

D. 数字的偏心率

中文机器翻译题面 查看原题

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

Degree Of Number's Eccentricity - 原题 PDF
赛事原始英文题册页面
可复制的 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