Gà và chó

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp for Vét cạn

Đề bài

Bài toán dân gian:

"Vừa gà vừa chó, bó lại cho tròn, ba mươi sáu con, một trăm chân chẵn."

Có tất cả $36$ con gà và chó, đếm được tổng cộng $100$ cái chân. Hỏi có bao nhiêu con gà, bao nhiêu con chó?

Dữ liệu vào:

Không có dữ liệu vào.

Kết quả:

In ra hai số nguyên trên một dòng, cách nhau bởi dấu cách: số gà trước, số chó sau.

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

(không có dữ liệu vào)

Ví dụ 1 – output

22 14

22 con gà có $22 \cdot 2 = 44$ chân, 14 con chó có $14 \cdot 4 = 56$ chân; tổng $22 + 14 = 36$ con và $44 + 56 = 100$ chân.

Nguồn: phỏng theo bài "GÀ VÀ CHÓ" – vinhdinhcoder.net (chủ đề Lặp FOR).

Lời mở đầu

Bài toán dân gian "Vừa gà vừa chó…" quen thuộc từ tiểu học. Ở lớp lập trình, mình không cần giả thiết tạm hay lập hệ phương trình: máy tính thử hết mọi khả năng số gà (từ 0 tới 36) chỉ trong nháy mắt. Đây là ví dụ đầu tiên của kỹ thuật vét cạn (brute force). Ghi chú: bài không có dữ liệu vào và chỉ có 1 test; nhớ in số gà trước, số chó sau.

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ộ test1 testÝ tưởngthử mọi số gà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ó 1 test, mỗi test đúng được 1 phần điểm như nhau. Bài không có dữ liệu vào nên chỉ có duy nhất 1 test (input rỗng).

Test	Nội dung kiểm tra
1	Input rỗng, đáp án 22 14

Ý tưởngThử số gà từ 0 đến 36

Gọi số gà là ga thì số chó là 36 - ga (tổng 36 con). Cho ga chạy từ $0$ tới $36$, với mỗi giá trị kiểm tra tổng số chân:

ga * 2 + (36 - ga) * 4 == 100

Gặp giá trị thoả mãn thì in ra và dừng. Chỉ có 37 lần thử – máy tính làm xong tức thì.

Vì sao vét cạn được?

Số khả năng ít (37) và mỗi khả năng kiểm tra rất nhanh. Khi số khả năng nhỏ, "thử hết" là cách chắc ăn nhất – không sợ sai công thức.

Mình cho em đổi tổng số con và số chân để thử bài toán khác. Bấm Tiếp để xem từng lần thử:

số con = số chân =

Ví dụ nhanh:

Lời giảiVòng for thử số gà

Một vòng for, một câu if, tìm thấy thì in rồi break.

C++▶ Chạy tay từng dòng codeThử số gà từ 0 đến 36, kiểm tra tổng số chân.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Có thể giải bằng toán: nếu cả 36 con đều là gà thì có 72 chân, thiếu 28 chân; mỗi lần đổi một gà thành chó thêm 2 chân → có $28 / 2 = 14$ chó. Nhưng vòng lặp thì không cần nghĩ!
2. Chương trình không đọc gì cả (không có cin) – vẫn hợp lệ.
3. Chỉ một lời giải duy nhất nên break không bắt buộc, nhưng thêm vào cho chương trình dừng sớm.

Không gian$O(1)$

Thời gian$O(1)$ (37 lần thử)

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

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

Bài chỉ có 1 test nên sai là mất trắng điểm. Các cách làm sai mình đã chấm thử:

Cách làm sai	Đúng	Ghi chú
In ngược: số chó trước, số gà sau (14 22)	0/1	sai test 1
Nhầm số chân: gà 4 chân, chó 2 chân	0/1	sai test 1
In thêm chữ Ga: 22, Cho: 14	0/1	sai test 1

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++	1/1	0.003s	Full điểm
	Python	1/1	0.023s	Full điểm
In ngược	C++	0/1	–	Mất 1 test
Nhầm số chân	C++	0/1	–	Mất 1 test
In thêm chữ	C++	0/1	–	Mất 1 test

Ghi chú của mình: máy chấm so từng ký tự với đáp án: in đúng thứ tự, đúng định dạng đề yêu cầu, không thêm chữ "trang trí".

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 😇