

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
正整数 x に対して,その各桁の和を f(x) と表すことにします.例えば f(144) = 1+4+4 = 9,f(1)=1 です.
正整数 N が与えられます.次のように定まる正整数 M, x を求めてください.
- f(x)=N かつ f(2x)=M を満たす正整数 x が存在するような,最大の正整数 M.
- そのような M に対して,f(x)=N かつ f(2x)=M を満たす最小の正整数 x.
制約
- 1\leq N\leq 10^5
入力
入力は以下の形式で標準入力から与えられます.
N
出力
1 行目には M,2 行目には x を出力してください.
入力例 1
3
出力例 1
6 3
f(x)=3 であるとき必ず f(2x) = 6 となることが証明できます.したがって M=6 です. f(x)=3 かつ f(2x)=6 となる最小の正整数は x=3 です.これらを出力します.
入力例 2
6
出力例 2
12 24
入力例 3
100
出力例 3
200 4444444444444444444444444
Score : 300 points
Problem Statement
For a positive integer x, let f(x) be the sum of its digit. For example, f(144) = 1+4+4 = 9 and f(1)=1.
You are given a positive integer N. Find the following positive integers M and x:
- The maximum positive integer M for which there exists a positive integer x such that f(x)=N and f(2x)=M.
- The minimum positive integer x such that f(x)=N and f(2x)=M for the M above.
Constraints
- 1\leq N\leq 10^5
Input
Input is given from Standard Input in the following format:
N
Output
Print M in the first line and x in the second line.
Sample Input 1
3
Sample Output 1
6 3
We can prove that whenever f(x)=3, f(2x) = 6. Thus, M=6. The minimum positive integer x such that f(x)=3 and f(2x)=6 is x=3. These M and x should be printed.
Sample Input 2
6
Sample Output 2
12 24
Sample Input 3
100
Sample Output 3
200 4444444444444444444444444