Tìm S

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp while Số chính phương

Đề bài

Cho số nguyên dương $N$. Xét tổng $S = 1 + 3 + 5 + 7 + \ldots$ được cộng dần các số lẻ liên tiếp bắt đầu từ $1$. Hãy tìm giá trị $S$ nhỏ nhất sao cho $S \ge N$.

Dữ liệu vào:

Một số nguyên dương $N$.

Kết quả:

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

Giới hạn:

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

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

Ví dụ 1 – input

7

Ví dụ 1 – output

9

Ví dụ 2 – input

15

Ví dụ 2 – output

16

Ví dụ 3 – input

16

Ví dụ 3 – output

16

• Ví dụ 1: $S$ lần lượt là $1, 4, 9$; $9$ là giá trị đầu tiên $\ge 7$.
• Ví dụ 2: $S$ lần lượt là $1, 4, 9, 16$; $16 \ge 15$.
• Ví dụ 3: $S = 16$ bằng đúng $N$ nên thoả mãn (điều kiện là $S \ge N$).

Nguồn: phỏng theo bài "TÌM S" – vinhdinhcoder.net (chủ đề Lặp WHILE).

Lời mở đầu

Cộng dồn các số lẻ $1 + 3 + 5 + \ldots$ cho tới khi tổng đạt $N$. Một bài while điển hình, kèm một điều thú vị: các tổng này luôn là số chính phương $1, 4, 9, 16, \ldots$ Ghi chú: mình thêm ví dụ $N = 16$ vào đề để nhấn mạnh điều kiện là $S \ge N$ (bằng cũng được).

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

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởngwhile (S < N)Lời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau. Mọi test thoả $1 \le N \le 10^9$.

Test	Nội dung kiểm tra
1–12	$N$ nhỏ, có các số chính phương ($1, 4, 9, 16, 25$) và các số ngay sát chúng
13–17	$N$ quanh $31622^2 = 999\,950\,884$ và $10^9$ (đáp án $31623^2$)
18–20	$N$ ngẫu nhiên lớn

Ý tưởngCộng số lẻ tiếp theo khi S còn nhỏ hơn N

Dùng hai biến: S = 0 và le = 1 (số lẻ sắp cộng). Chừng nào S < N: cộng S += le rồi le += 2. Khi dừng, $S \ge N$ và là giá trị nhỏ nhất như vậy (vì $S$ tăng dần).

Tổng $k$ số lẻ đầu tiên bằng $k^2$ nên số vòng lặp chỉ khoảng $\sqrt{N} \le 31\,623$ – rất nhanh.

Bằng cũng được

Đề yêu cầu $S \ge N$. Nếu $N$ là số chính phương (như $16$) thì đáp án là chính $N$. Điều kiện lặp phải là S < N, không phải S <= N.

Em nhập dữ liệu rồi bấm Tiếp để xem từng vòng lặp chạy thế nào:

N =

Ví dụ nhanh:

Lời giảiHai biến S và le

Dùng long long cho chắc (thật ra $S \le 31623^2 \approx 1{,}00001 \cdot 10^9$ vẫn vừa int).

C++▶ Chạy tay từng dòng codeCộng dần các số lẻ cho tới khi S ≥ n.

Dữ liệu vào (stdin) – sửa thoải mái7

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Có thể giải bằng sqrt: lấy $k = \lceil \sqrt N \rceil$, in $k^2$. Nhưng làm tròn số thực rất dễ sai ở các số chính phương – vòng lặp an toàn hơn.
2. Thứ tự trong vòng lặp: cộng le vào S trước, rồi mới tăng le.

Không gian$O(1)$

Thời gian$O(\sqrt N)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.003s. Bản Python đúng 20/20 test, chạy lâu nhất 0.034s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Điều kiện lặp S <= N (đòi $S > N$)	14/20	sai test 3, 5, 6, 8, 11, 14
In ((int)sqrt(N) + 1)²	14/20	sai test 3, 5, 6, 8, 11, 14
Tăng le++ (cộng cả số chẵn)	1/20	sai test 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
In số lẻ cuối cùng thay vì $S$	1/20	sai test 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.003s	Full điểm
	Python	20/20	0.034s	Full điểm
Điều kiện <=	C++	14/20	–	Mất 6 test
sqrt + 1	C++	14/20	–	Mất 6 test
le++	C++	1/20	–	Mất 19 test
In nhầm biến	C++	1/20	–	Mất 19 test

Ghi chú của mình: "nhỏ nhất thoả $\ge$" ⇒ lặp khi <; "nhỏ nhất thoả $>$" ⇒ lặp khi <=. Đọc kỹ dấu trong đề trước khi viết điều kiện.

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 😇