Phương trình bậc hai

Nguồn: CLUE OJ Độ khó: Dễ Rẽ nhánh Kiểu dữ liệu

Đề bài

Giải phương trình bậc hai $ax^2 + bx + c = 0$ ($a \ne 0$) với $a, b, c$ là các số nguyên.

Gọi $\Delta = b^2 - 4ac$:

• Nếu $\Delta < 0$: in ra VO NGHIEM.
• Nếu $\Delta = 0$: in ra dòng PT CO NGHIEM KEP, dòng tiếp theo in X = rồi tới nghiệm kép $x = \dfrac{-b}{2a}$.
• Nếu $\Delta > 0$: in ra dòng PT CO HAI NGHIEM, hai dòng tiếp theo lần lượt in X1 = rồi tới $x_1 = \dfrac{-b + \sqrt{\Delta}}{2a}$ và X2 = rồi tới $x_2 = \dfrac{-b - \sqrt{\Delta}}{2a}$.

Các nghiệm được làm tròn đến 2 chữ số thập phân.

Dữ liệu vào:

Một dòng gồm ba số nguyên $a, b, c$ cách nhau bởi dấu cách.

Kết quả:

Kết luận nghiệm theo đúng mẫu ở trên.

Giới hạn:

• $1 \le |a| \le 10^9$; $|b|, |c| \le 10^9$

Subtask:

• Subtask 1 (50% số điểm): $|a|, |b|, |c| \le 1000$.
• Subtask 2 (50% số điểm): không có ràng buộc gì thêm.

Chấm điểm:

Các nghiệm được chấm với sai số tuyệt đối không quá $0{,}01$ (ví dụ in -0.00 thay cho 0.00 vẫn được chấp nhận). Các chữ khác phải in đúng như mẫu.

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

1 2 3

Ví dụ 1 – output

VO NGHIEM

Ví dụ 2 – input

1 2 -3

Ví dụ 2 – output

PT CO HAI NGHIEM
X1 = 1.00
X2 = -3.00

Ví dụ 3 – input

1 -2 1

Ví dụ 3 – output

PT CO NGHIEM KEP
X = 1.00

Nguồn: phỏng theo bài "Phương trình bậc hai" – vinhdinhcoder.net (chủ đề Rẽ nhánh).

Lời mở đầu

Giải phương trình bậc hai thì ai cũng thuộc công thức. Nhưng với hệ số tới $10^9$, $\Delta = b^2 - 4ac$ lên tới $5 \cdot 10^{18}$: dùng int thì tràn, dùng double thì sai số – $\Delta = 1$ có thể bị tính thành $0$, biến "hai nghiệm" thành "nghiệm kép"!

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ưởngΔ bằng số nguyênLờ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. Test 1–10 thuộc subtask 1 ($|a|, |b|, |c| \le 1000$), test 11–20 có hệ số tới $10^9$. Nghiệm được chấm với sai số $0{,}01$.

Test	Nội dung kiểm tra
1–10	Đủ ba trường hợp, $a < 0$, $b = 0$, $c = 0$, nghiệm bằng 0
11	$\Delta = 1$ với $b^2 \approx 10^{18}$: tính $\Delta$ bằng double ra 0 → in nhầm "nghiệm kép"
12–13	$\Delta = -3$ với hệ số cỡ $10^9$: double ra 0 → in nhầm "nghiệm kép" thay vì "vô nghiệm"
14–20	Hệ số tới $10^9$: tràn int, $\Delta = 0$ với số lớn, nghiệm rất lớn / rất nhỏ

Ý tưởngTính Δ bằng số nguyên

Công thức quen thuộc: $\Delta = b^2 - 4ac$.

• $\Delta < 0$: vô nghiệm.
• $\Delta = 0$: nghiệm kép $x = \dfrac{-b}{2a}$.
• $\Delta > 0$: $x_1 = \dfrac{-b + \sqrt{\Delta}}{2a}$, $x_2 = \dfrac{-b - \sqrt{\Delta}}{2a}$ (đúng thứ tự đề yêu cầu).

Mấu chốt

Việc rẽ nhánh dựa vào dấu của $\Delta$, nên $\Delta$ phải được tính chính xác tuyệt đối: $a, b, c$ là số nguyên nên tính $\Delta$ bằng long long ($|b^2| \le 10^{18}$, $|4ac| \le 4 \cdot 10^{18}$, tổng vẫn dưới $9{,}2 \cdot 10^{18}$). Chỉ khi tính nghiệm (có căn) mới chuyển sang double.

Em nhập dữ liệu rồi bấm Tiếp để xem chương trình xét từng điều kiện:

a = b = c =

Ví dụ nhanh:

Lời giảiΔ long long, nghiệm double

In số thực 2 chữ số thập phân bằng printf("%.2f", x) (C++) và "%.2f" % x (Python).

C++▶ Chạy tay từng dòng codeTính Δ bằng long long rồi rẽ 3 nhánh theo dấu của Δ.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. 2.0 * a (có .0) để phép chia là chia số thực. Viết -b / 2 * a là sai: máy chia cho 2 rồi nhân với $a$.
2. sqrt((double)delta): ép delta sang double trước khi lấy căn.
3. Python: số nguyên không bao giờ tràn, b*b - 4*a*c luôn chính xác.

Không gian$O(1)$

Thời gian$O(1)$

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.021s. 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ú
Đọc $a, b, c$ vào double rồi tính $\Delta$ bằng số thực	17/20	sai test 11, 12, 13
Dùng int (tràn khi tính $b^2$, $4ac$)	14/20	sai test 14, 15, 16, 18, 19, 20
In nghiệm lớn trước, nhỏ sau (sai thứ tự $x_1, x_2$ khi $a < 0$)	16/20	sai test 5, 6, 15, 19
Viết (-b + sqrt(d)) / 2.0 * a (quên ngoặc)	11/20	sai test 4, 6, 10, 11, 15, 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.021s	Full điểm
Δ bằng double	C++	17/20	–	Mất 3 test
Dùng int	C++	14/20	–	Mất 6 test
Sai thứ tự nghiệm	C++	16/20	–	Mất 4 test
Quên ngoặc 2a	C++	11/20	–	Mất 9 test

Ghi chú của mình: quy tắc vàng: phần nào quyết định rẽ nhánh (ở đây là dấu của $\Delta$) thì phải tính chính xác bằng số nguyên; chỉ dùng số thực cho kết quả cuối cùng cần in ra.

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 😇