Блог пользователя danhnguyen0902

Автор danhnguyen0902, 11 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think greedy solution works here

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

can i use an integer twice?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    @Psychologist: Do you have any idea yet?

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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