danhnguyen0902's blog

Digits sum
By danhnguyen0902, 11 years ago, In English

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?

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think greedy solution works here

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

can i use an integer twice?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    @Psychologist: Do you have any idea yet?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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].

        → Reply