Một mệt mỏi

Submit solution
Points: 3
Time limit: 0.5s
Memory limit: 977M
Author:
NguyenHaKien_CNTT4_K63
Problem type

Hà Kiên nhận được một số nguyên dương \(T\) quyết định xem cậu có thể vượt qua khó khăn trước mắt hay không.

Nhiệm vụ của cậu là phải tách số nguyên dương \(T\) thành tổng của các số nguyên chỉ chứa toàn chữ số \(1\) hoặc cậu sẽ đắm chìm ở đây nếu không giải được. Và tất nhiên không đơn giản như vậy, số lượng chữ số \(1\) trong phép tính phải là ít nhất có thể.

Đã thử rất nhiều cách nhưng vẫn không cho ra kết quả tốt nhất, Hà Kiên đã quá mệt rồi.

Đầu vào

Nhập vào số nguyên dương \(T\). \((1 \le T \le 10^{18})\)

Đầu ra

In ra kết quả của bài toán là số lượng chữ số \(1\) ít nhất có thể sau khi tách số nguyên dương \(T\).

Ví dụ 1

Đầu vào

56

Đầu ra

11

Ví dụ 2

Đầu vào

132

Đầu ra

8

Giải thích

\(56 = 11 + 11 + 11 + 11 + 11 + 1\)

\(132 = 111 + 11 + 11 + (-1)\)

Comments


  • 0
    ManhDucDong_KHMT_K64  commented on Sept. 5, 2025, 2:18 p.m.

    Cho em xin hướng giải quyết bài này với:<


    • 0
      MANH_IT2_INED_K64  commented on Sept. 5, 2025, 3:02 p.m.

      Đệ qui

      try(n, length) ở mỗi mức length gọi lại chính nó với length -1 cho hai nhánh:

      “làm tròn xuống”: try(n % num, length -1)

      “làm tròn lên”: length + try(num - (n % num), length-1) rồi lấy min(...). Base: n==0 → 0, n==1 → 1. Độ sâu đệ quy ≈ số chữ số của n + 1 nên an toàn.