Czech ACM Student Chapter

Czech Technical University in Prague

acm

Charles University in Prague

Technical University of Ostrava

cz

Slovak University of Technology

Masaryk University

ˇ

ˇ ´

University of Zilina

Pavol Jozef Safarik University in Koˇice

s

CTU Open Contest 2010

The Easiest Problem is This One

easy.c, easy.C, easy.java, easy.p

If you are the lucky one to advance to the ACM-ICPC World Finals, one of the situations you

will face is the world finals competition itself. Wait, isn't that the main reason to go there?

In the beginning of each ACM-ICPC competition, there are two separate goals each team tries

to accomplish:

1. among the given set of problems, find the easiest one,

2. solve that problem as fast as possible.

To evaluate the performance of all teams in detail, we want to test your abilities for each of

these two goals separately. The former goal (finding the easiest problem) is analyzed in another

problem (difficult), here we deal with the latter goal (solving the easiest problem).

To isolate other influences, we will tell you clearly which problem is the easiest one to solve in

this problem set (CTU Open Contest 2010). It is this one! What more can we do to emphasize

that fact? The title says it. The problem name is easy. And believe us, it is true. This is

indeed the easiest of all nine problems. We recommend you to do it first.

A positive integer number N can be expressed in the decimal system (numeral system with the

base of 10) as the sequence of digits di

N = d1d2d3d4 . . . dk

where ∀i, 1 ≤ i ≤ k : 0 ≤ di ≤ 9.

The digits express the value which has to be multiplied by a power of ten:

k-1

i

N = d1 · 10k-1 + d2 · 10k-2 + . . . + dk-1 · 10 + dk =

di+1 · 10k-i-1

=0

The sum of the digits S(N ) is then defined as the plain sum of all individual digits without

multiplying them by powers of ten:

k-1

i

S(N ) = d1 + d2 + d3 + . . . + dk =

di+1

=0

For example:

N = 3029 = 3 · 103 + 2 · 10 + 9

S(N ) = 3 + 0 + 2 + 9 = 14

If we multiply the original number N with another number m, the sum of the digits typically

changes. For example, if m1 = 26:

N · m1 = 78754 = 7 · 104 + 8 · 103 + 7 · 102 + 5 · 10 + 4

S(N · m1) = 7 + 8 + 7 + 5 + 4 = 31

However, there are some numbers that, if multiplied by N , will result in the same sum of the

digits as the original number N . For example, consider m2 = 37:

N · m2 = 112073 = 105 + 104 + 2 · 103 + 7 · 10 + 3

S(N · m2) = 1 + 1 + 2 + 0 + 7 + 3 = 14 = S(N )

Your task is to find the smallest positive integer p among those that will result in the same sum

of the digits when multiplied by N . To make the task a little bit more challenging, the number

must also be higher than ten.

Input Specification

The input consists of several test cases. Each case is described by a single line containing one

positive integer number N , 1 ≤ N ≤ 100 000. The last test case is followed by a line containing

zero.

Output Specification

For each test case, print one line with a single integer number p which satisfies all of the following

conditions:

· p > 10

· S(N ) = S(N · p)

· ∀q ∈ N : [S(N ) = S(N · q)] ⇒ [(q ≥ p) ∨ (q ≤ 10)]

Sample Input

3029

4

5

42

0

Output for Sample Input

37

28

28

25