Let function S(X) equal sum of X's digits.
For ex: S(357) = 3 + 5 + 7 = 15
Given M and N (0 < M, N <= 10^12). Find the minimum number K such that:
a1 + a2 + ... + aK = N
S(a1) + S(a2) + ... + S(aK) = M
(a1, a2, ..., aK are arbitrary integers <= N)
Example:
Input (M and N)
1 100
Output (K, if K doesn't exist, print -1)
1
Source: http://vn.spoj.com/problems/A2DIGIT/
Does anyone have any idea for this problem?
I think greedy solution works here
Could you please give me more details about it?
oops I didn't notice a1 + a2 + ... + aK = N
sorry
My bad. Sorry for the unclear format...
can i use an integer twice?
@Psychologist: Do you have any idea yet?
Notice that s(n) <= n
If n<m no solution
If n=m k=n
Notice that n-s(n) is always divisible by 9
If (n-m) is not divisible by 9 then no solution
To make m divisible by 9, n-=(m%9),m-=(m%9),ans=(m%9)
(Thinking to be cont)
Your approach is unclear.
For example, if n = 18 and m = 18 right answer is k = 2 with a1 = 9, a2 = 9.
So for n = m case right answer seems to be [n/9].
yes. my mistake there.
actually [(n + 8) / 9]