Bộ ba Pytago

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

Đề bài

Bộ ba số nguyên dương $a, b, c$ được gọi là bộ số Pi-ta-go nếu tổng bình phương của hai số nào đó trong ba số bằng bình phương của số còn lại. Ví dụ $3, 4, 5$ là bộ số Pi-ta-go vì $3^2 + 4^2 = 5^2$; $5, 4, 3$ cũng vậy vì $4^2 + 3^2 = 5^2$.

Cho ba số nguyên dương $a, b, c$, hãy kiểm tra chúng có phải là bộ số Pi-ta-go hay không.

Dữ liệu vào:

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

Kết quả:

• Nếu là bộ số Pi-ta-go, in ra Ba so da nhap la bo so Pi-ta-go.
• Ngược lại, in ra Ba so da nhap khong la bo so Pi-ta-go.

Giới hạn:

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

Subtask:

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

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

3 4 5

Ví dụ 1 – output

Ba so da nhap la bo so Pi-ta-go

Ví dụ 2 – input

3 4 3

Ví dụ 2 – output

Ba so da nhap khong la bo so Pi-ta-go

Ví dụ 3 – input

5 4 3

Ví dụ 3 – output

Ba so da nhap la bo so Pi-ta-go

• Ví dụ 1: $3^2 + 4^2 = 9 + 16 = 25 = 5^2$.
• Ví dụ 2: không có cách chọn nào thoả mãn ($3^2 + 3^2 = 18 \ne 16$, $3^2 + 4^2 = 25 \ne 9$).
• Ví dụ 3: số lớn nhất đứng đầu, nhưng $4^2 + 3^2 = 5^2$ nên vẫn là bộ số Pi-ta-go.

Nguồn: phỏng theo bài "Bộ ba Pytago" – vinhdinhcoder.net (chủ đề Rẽ nhánh).

Lời mở đầu

Bài kiểm tra "bộ số Pi-ta-go" nghe rất quen, nhưng có hai cái bẫy: số lớn nhất (cạnh huyền) không nhất thiết đứng cuối, và với $a, b, c$ tới $10^9$ thì bình phương lên tới $10^{18}$ – vượt xa kiểu int. Mình sẽ đi từ ý tưởng xét đủ 3 khả năng, xem mô phỏng từng điều kiện, rồi tới code và các cách làm sai hay gặ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ưởng3 khả năngLờ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–8 thuộc subtask 1 ($a, b, c \le 1000$), test 9–20 là subtask 2 với số tới $10^9$.

Test	Nội dung kiểm tra
1–8	Số nhỏ: đủ các thứ tự cạnh huyền (đầu, giữa, cuối), bộ không phải Pi-ta-go
9–10	Bộ $(6\cdot10^8, 8\cdot10^8, 10^9)$: bình phương tới $10^{18}$ – tràn int
11–13, 15	Bộ "suýt nữa": $a^2 + b^2$ và $c^2$ chỉ chênh nhau 2 đơn vị ở mức $10^{18}$ – dùng số thực (double, sqrt, pow) sẽ không phân biệt nổi
14	$65536^2 = 2^{32}$: khi tràn int giá trị này "biến thành" 0 → trả lời sai
16–20	Các bộ Pi-ta-go lớn (sinh từ công thức $m^2 - n^2, 2mn, m^2 + n^2$), xáo trộn thứ tự, và các bộ lệch 1 đơn vị

Ý tưởngXét đủ 3 khả năng cạnh huyền

Đề không nói số nào là cạnh huyền, nên ta thử cả 3 khả năng:

• $c$ là số "còn lại": $a^2 + b^2 = c^2$
• $b$ là số "còn lại": $a^2 + c^2 = b^2$
• $a$ là số "còn lại": $b^2 + c^2 = a^2$

Chỉ cần một trong ba đúng là bộ số Pi-ta-go → nối 3 điều kiện bằng || (hoặc or trong Python).

Chọn kiểu dữ liệu

$a, b, c \le 10^9$ nên $a^2 \le 10^{18}$ và tổng hai bình phương $\le 2 \cdot 10^{18}$. Kiểu int chỉ chứa tới khoảng $2{,}1 \cdot 10^9$ → phải dùng long long (chứa tới khoảng $9{,}2 \cdot 10^{18}$). Và tuyệt đối không dùng số thực: double chỉ chính xác khoảng 15–16 chữ số, không phân biệt được hai số cỡ $10^{18}$ chênh nhau vài đơn vị.

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ảiBa điều kiện nối bằng "hoặc"

Đọc 3 số vào biến long long, kiểm tra 3 khả năng bằng một câu lệnh if với toán tử ||. Code bên dưới chỉ dùng kiến thức của chương Biến – kiểu dữ liệu và câu lệnh rẽ nhánh.

C++▶ Chạy tay từng dòng codeĐọc 3 số, tính bình phương và xét 3 khả năng cạnh huyền.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Các ô bình phương được tính bằng số nguyên lớn (giống long long), nên em thử số tới 10^9 vẫn đúng.

1. Toán tử || (hoặc) cho kết quả đúng khi ít nhất một vế đúng; C++ dừng xét ngay khi gặp vế đúng.
2. Biến khai báo long long nên a*a được tính trong long long, không tràn số. Nếu khai báo int a, b, c thì a*a tràn trước khi kịp so sánh.
3. Python tự xử lý số nguyên lớn nên không lo tràn số, nhưng cũng không được dùng math.sqrt hay **0.5 (số thực) để so sánh.

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.005s. Bản Python đúng 20/20 test, chạy lâu nhất 0.024s. Full điểm.

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

Mình đã viết thử các cách làm sai mà học viên hay mắc phải rồi chấm trên chính bộ test của bài:

Cách làm sai	Đúng	Ghi chú
Chỉ kiểm tra $a^2 + b^2 = c^2$ (nghĩ $c$ luôn là cạnh huyền)	14/20	sai test 3, 4, 6, 10, 11, 18
Khai báo int (bình phương bị tràn số)	19/20	sai test 14
Dùng double và pow(a, 2) để so sánh	18/20	sai test 12, 13
So sánh sqrt(a*a + b*b) == c	17/20	sai test 12, 13, 15

Vì sao tràn int lại "đúng" gần hết?

Khi tràn số, máy tính chỉ giữ lại phần dư khi chia cho $2^{32}$. Đẳng thức đúng thì vẫn đúng sau khi lấy dư, nên phần lớn test vẫn qua – nhưng test 14 ($65536^2 = 2^{32}$ "biến thành" 0) làm lộ ngay lỗi. Đừng ỷ vào việc "nộp thử thấy gần đủ điểm"!

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.005s	Full điểm
	Python	20/20	0.024s	Full điểm
Chỉ xét c là cạnh huyền	C++	14/20	–	Mất 6 test
Dùng int	C++	19/20	–	Mất 1 test
double + pow	C++	18/20	–	Mất 2 test
Dùng sqrt	C++	17/20	–	Mất 3 test

Ghi chú của mình: mọi cách đều chạy tức thì vì chỉ có vài phép tính. Điểm khác biệt nằm ở kiểu dữ liệu: số nguyên tới $10^{18}$ thì dùng long long, và khi so sánh "bằng nhau" thì tránh số thực.

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 😇