Mèo và chuột

Nguồn: CLUE OJ Độ khó: Dễ Rẽ nhánh Trị tuyệt đối

Đề bài

Trên một đường thẳng (trục số) có hai chú mèo và một chú chuột. Chú chuột đứng yên ăn mồi, còn hai chú mèo cùng lúc lao về phía chú chuột để bắt nó. Hai chú mèo chạy với tốc độ như nhau.

Mèo A đang ở vị trí $a$, mèo B ở vị trí $b$ và chuột C ở vị trí $c$. Hãy cho biết chú mèo nào bắt được chuột:

• Nếu mèo A tới chỗ chuột trước, in ra Cat_A.
• Nếu mèo B tới chỗ chuột trước, in ra Cat_B.
• Nếu hai mèo tới chỗ chuột cùng một lúc, chúng sẽ tranh nhau và chuột trốn thoát, in ra Mouse_C.

Dữ liệu vào:

Một dòng gồm ba số nguyên $a, b, c$ lần lượt là vị trí của mèo A, mèo B và chuột C.

Kết quả:

In ra Cat_A, Cat_B hoặc Mouse_C theo yêu cầu đề bài.

Giới hạn:

• $-10^9 \le a, b, c \le 10^9$ (các vị trí có thể trùng nhau, có thể âm)

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.

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 4

Ví dụ 1 – output

Cat_B

Ví dụ 2 – input

1 5 3

Ví dụ 2 – output

Mouse_C

• Ví dụ 1: mèo A cách chuột $|1 - 4| = 3$, mèo B cách chuột $|2 - 4| = 2$ nên mèo B tới trước.
• Ví dụ 2: hai mèo đều cách chuột 2 đơn vị (một bên trái, một bên phải) nên tới cùng lúc, chuột trốn thoát.

Nguồn: phỏng theo bài "Mèo và chuột" – vinhdinhcoder.net (chủ đề Rẽ nhánh).

Lời mở đầu

Hai chú mèo chạy cùng tốc độ, nên chú nào ở gần chuột hơn sẽ tới trước. Câu hỏi chỉ còn: "gần" đo thế nào khi vị trí có thể âm, và mèo có thể đứng bên trái hoặc bên phải chuột? Câu trả lời là khoảng cách = trị tuyệt đối của hiệu.

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ưởngso khoảng cáchLờ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ó toạ độ tới $10^9$.

Test	Nội dung kiểm tra
1–10	Số nhỏ: mèo ở hai phía chuột, cùng phía, đứng trùng chuột, hai mèo trùng nhau, toạ độ âm
11–20	Toạ độ tới $\pm 10^9$: hai mèo đối xứng qua chuột (Mouse_C), mèo xa hơn nhưng "số lớn hơn", hai mèo cùng vị trí

Ý tưởngSo sánh hai khoảng cách

Mèo A phải chạy quãng đường $d_A = |a - c|$, mèo B phải chạy $d_B = |b - c|$ (trị tuyệt đối vì mèo có thể ở bên trái hoặc bên phải chuột). Cùng tốc độ nên:

• $d_A < d_B$: mèo A tới trước → Cat_A.
• $d_B < d_A$: mèo B tới trước → Cat_B.
• $d_A = d_B$: tới cùng lúc → Mouse_C.

Lưu ý

Đừng so sánh trực tiếp $a$ với $b$, cũng đừng quên dấu trị tuyệt đối: với ví dụ 2 ($a = 1$, $b = 5$, $c = 3$), $c - a = 2$ còn $c - b = -2$ – không có trị tuyệt đối sẽ tưởng mèo B gần hơn!

Em nhập vị trí hai mèo và chuột rồi bấm Tiếp để xem hai mèo chạy về phía chuột:

a = b = c =

Ví dụ nhanh:

Lời giảiTrị tuyệt đối + if / else if / else

Tính hai khoảng cách bằng hàm abs rồi rẽ 3 nhánh. Dùng long long cho chắc (hiệu hai toạ độ có thể tới $2 \cdot 10^9$, sát giới hạn int).

C++▶ Chạy tay từng dòng codeTính quãng đường của từng mèo rồi so sánh.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Chuỗi if / else if / else xét lần lượt từ trên xuống, gặp điều kiện đúng đầu tiên thì làm rồi bỏ qua phần còn lại – nên nhánh else cuối chính là trường hợp $d_A = d_B$.
2. Hàm abs trong bits/stdc++.h dùng được cho long long; Python có sẵn hàm abs.

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.023s. 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ú
Quên trị tuyệt đối: so sánh c - a với c - b	7/20	sai test 2, 3, 6, 7, 8, 9, 11, 14, 15, 16, 17, 19, 20
Quên trường hợp bằng nhau (chỉ có Cat_A / Cat_B)	13/20	sai test 2, 4, 7, 11, 15, 18, 19
So sánh vị trí $a$ với $b$ thay vì khoảng cách	7/20	sai test 2, 3, 6, 7, 8, 9, 11, 14, 15, 16, 17, 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.023s	Full điểm
Quên trị tuyệt đối	C++	7/20	–	Mất 13 test
Quên TH bằng nhau	C++	13/20	–	Mất 7 test
So sánh a với b	C++	7/20	–	Mất 13 test

Ghi chú của mình: bài chỉ có vài phép tính nên chạy tức thì. Mấu chốt là hiểu "khoảng cách trên trục số = trị tuyệt đối của hiệu" và không bỏ sót trường hợp hai mèo cách đều.

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 😇