Hướng dẫn cho Saving


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: shiba

Ta sẽ sử dụng công thức tính tổng các số tự nhiên từ \(1\) đến \(k\)\(\frac{k \times (k+1)}{2}\).

Ta có thể giải phương trình \(\frac{k(k+1)}{2} \geq N\) để tìm ra giá trị ngày cần tìm. Chuyển đổi phương trình ta được \(k^2 + k - 2N \geq 0\). Giải phương trình bậc hai này ta sẽ được \(k = \lceil \frac{-1+\sqrt{1+8N}}{2} \rceil\)

Trong đó, hàm \(\lceil x \rceil\) là hàm trả về số nguyên nhỏ nhất không nhỏ hơn \(x\). Ví dụ: \(\lceil 1.2 \rceil = 2\).

Vì số ngày là số nguyên dương, nên ta sử dụng hàm trên để làm tròn số kết quả tìm được lên.

Độ phức tạp của lời giải này là \(O(1)\) vì chỉ cần tính một phép tính căn bậc hai và một phép tính trên số nguyên.



Bình luận


  • 0
    xthabao1    10:28 p.m. 31 Tháng 3, 2024

    vẫn chx hiểu cái dấu ⌈​ ⌉ là gì