Free Contest Testing Round 3 - DIGITSUM

View as PDF
Submit solution
Points: 0.49 (partial)
Time limit: 1.0s
Memory limit: 256M
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

In case the statement didn't load correctly, you can download the statement here: Statement

Lưu ý: các bạn không nhập, xuất dữ liệu bằng file kể cả khi đề bài có yêu cầu. Đọc, ghi dữ liệu được thực hiện ở stdin và stdout.

Comments

Please read the guidelines before commenting.


  • 6
    KAKOII  commented on March 20, 2024, 8:33 a.m. ← edit 7

    Với thời gian chạy code AC của mình cho bài này là nhanh nhất VNOJ tính đến thời điểm viết comment :)), mình xin chia sẻ cách giải bài này mà không cần digit DP:

    Ta sẽ viết ~n~ dưới dạng ~10q + r~ với ~q \ge 0~ và ~0 \le r < 10~

    Từ đây tổng các chữ số của các số từ ~1~ đến ~n~ sẽ có công thức là:

    $$ D(n) = D(10q + r) = 45q + 10D(q - 1) + \frac{r(r + 1)}{2} + d(q) $$

    Với ~D(x)~ là tổng các chữ số của các số từ 1 đến ~x~, và ~d(x)~ là tổng các chữ số của ~x~

    Nguồn: Link