Đi tìm ẩn số x (VL21)

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp Mã bài VL21

Đề bài

Cho số nguyên dương $N$. Hãy tìm số nguyên dương $x$ lớn nhất thoả mãn

$$1 + 2 + 3 + \ldots + x \le N$$

Dữ liệu vào:

Một dòng chứa số nguyên dương $N$.

Kết quả:

In ra giá trị $x$ tìm được.

Giới hạn:

• $5 \le N \le 10^9$

Giới hạn thời gian: 1 giây, bộ nhớ: 512 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

6

Ví dụ 1 – output

3

Giải thích:

• $1 + 2 + 3 = 6 \le 6$ nhưng $1 + 2 + 3 + 4 = 10 > 6$ nên $x = 3$.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Ý tưởng

Cộng dần 1 + 2 + 3 + ...: chỉ tăng x khi cộng thêm x + 1 mà vẫn chưa vượt N. Vòng lặp chạy khoảng √(2N) ≈ 44 721 lần nên rất nhanh.

Ví dụ N = 6: thêm 1 (S=1), thêm 2 (S=3), thêm 3 (S=6), thêm 4 thì S=10 > 6 → dừng, x = 3.

Lưu ý / bẫy thường gặp

• Cộng cho tới khi tổng vượt N rồi in x sẽ thừa 1 (phải lùi lại).
• Dùng < thay vì ≤: khi tổng bằng đúng N (ví dụ N = 6) sẽ thiếu 1.
• Dùng công thức round(√(2N)) không chính xác.

Lời giải

Code chuẩn bên dưới đã chấm đúng toàn bộ 20 test trên CLUE OJ.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇