Phân số nhỏ nhất (Tin học trẻ 2022, bảng A)

Nguồn: Hội thi Tin học trẻ toàn quốc 2022 – Vòng sơ khảo, bảng A (Bài 2) Độ khó: Dễ Phân số UCLN – Euclid

Đề bài

Cho ba số tự nhiên $A, B, C$. Từ ba số đó, hãy tạo ra một phân số nhỏ nhất có thể. In ra tổng của tử số và mẫu số của phân số nhỏ nhất đã được tối giản.

Dữ liệu: nhập vào ba số tự nhiên $A, B, C$ $(0 < A, B, C \le 1000)$, mỗi số trên một dòng.

Kết quả: ghi ra một số duy nhất là kết quả của bài toán.

Giới hạn: thời gian 1 giây.

Ví dụ – input

3
2
4

Ví dụ – output

3

Giải thích ví dụ: những phân số có thể tạo ra: $\frac{3}{2}, \frac{3}{4}, \frac{2}{3}, \frac{2}{4}, \frac{4}{3}, \frac{4}{2}$. Phân số bé nhất là $\frac{2}{4} = \frac{1}{2}$. Vậy kết quả là $1 + 2 = 3$.

Lời mở đầu

Bài dành cho bảng A (tiểu học) nhưng chứa hai kỹ năng nền tảng: so sánh phân số không dùng số thực (nhân chéo) và rút gọn phân số bằng UCLN. Mình đi từ cách liệt kê đủ 6 phân số như ví dụ, tới cách nhận xét "tử nhỏ nhất, mẫu lớn nhất".

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ộ test100 testÝ tưởngtử bé, mẫu lớnCách 1liệt kê 6 phân sốCách 2min / maxTổng kếtkết quả chạy thật

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

Test	Giá trị A, B, C	Đáp án	Test có số trùng nhau
1 – 100	2 … 998	4 … 1.751	1

• Đề không chia subtask, 100 test đều cùng giới hạn $\le 1000$.
• Có 1 test trong đó hai trong ba số bằng nhau – cần nhớ tử và mẫu phải là hai số ở hai vị trí khác nhau (nếu trùng giá trị thì vẫn được dùng).

Ý tưởngPhân số nhỏ nhất = số nhỏ nhất / số lớn nhất

Với các số dương, phân số $\frac{x}{y}$ càng nhỏ khi tử $x$ càng nhỏ và mẫu $y$ càng lớn. Chọn tử là số nhỏ nhất, mẫu là số lớn nhất (hai số này ở hai vị trí khác nhau, kể cả khi bằng giá trị) ta được phân số nhỏ nhất:

Kết luận

$$\frac{\min(A, B, C)}{\max(A, B, C)} \;\xrightarrow{\text{chia cho } g = \gcd}\; \frac{\min/g}{\max/g}, \qquad \text{đáp án} = \frac{\min + \max}{g}$$

Rút gọn bằng UCLN tính theo thuật toán Euclid: $\gcd(a, b) = \gcd(b, a \bmod b)$. Em nhập 3 số rồi bấm Tiếp:

A = B = C =

Ví dụ nhanh:

Cách 1Liệt kê đủ 6 phân số, so sánh bằng nhân chéo

Cho $v[0], v[1], v[2]$ là 3 số. Duyệt mọi cặp chỉ số $i \ne j$ để có phân số $\frac{v[i]}{v[j]}$. So sánh $\frac{v_i}{v_j} < \frac{tu}{mau}$ bằng nhân chéo $v_i \cdot mau < tu \cdot v_j$ – tránh hoàn toàn sai số của số thực.

C++▶ Chạy tay từng dòng codeCách 1: duyệt mọi cặp (i, j) với i ≠ j, giữ phân số nhỏ nhất bằng nhân chéo, rút gọn bằng __gcd.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Chỉ có đúng 6 phân số nên chương trình chạy tức thì. Giá trị tối đa $1000 \cdot 1000 = 10^6$ khi nhân chéo vẫn vừa kiểu int.
• Không dùng double để so sánh phân số – đây là thói quen tốt cho các bài phân số lớn hơn.

Không gian$O(1)$

Thời gian$O(1)$

Kết quả chạy thật: bản C++ đúng 100/100 test (Tất cả: 100/100), test đúng chạy lâu nhất 0,005 giây; bản Python đúng 100/100 test (Tất cả: 100/100), test đúng chạy lâu nhất 0,037 giây.

Cách 2Tử = min, mẫu = max, rút gọn bằng Euclid tự viết

Dùng nhận xét ở phần Ý tưởng, không cần liệt kê. Hàm gcd tự viết bằng vòng lặp Euclid để học sinh thấy rõ từng bước.

C++▶ Chạy tay từng dòng codeCách 2: tử = min, mẫu = max, gcd bằng thuật toán Euclid rồi in tổng tử + mẫu sau rút gọn.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(1)$

Thời gian$O(\log 1000)$

Kết quả chạy thật: bản C++ đúng 100/100 test (Tất cả: 100/100), test đúng chạy lâu nhất 0,006 giây; bản Python đúng 100/100 test (Tất cả: 100/100), test đúng chạy lâu nhất 0,037 giây.

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

Mình chấm cả 2 cách (C++ và Python) trên toàn bộ 100 test với giới hạn 1 giây, đo thời gian CPU:

Lời giải	Tất cả test 1–100	Tổng	CPU lớn nhất (test đúng)
Cách 1 – C++	100/100	100/100	0,005s
Cách 1 – Python	100/100	100/100	0,037s
Cách 2 – C++	100/100	100/100	0,006s
Cách 2 – Python	100/100	100/100	0,037s

Ghi chú của mình: cả 2 cách đều đúng 100/100 và chạy tức thì. Cách 1 dạy kỹ năng so sánh phân số bằng nhân chéo (không dùng số thực), cách 2 rút gọn suy luận thành "tử nhỏ nhất, mẫu lớn nhất". Đừng quên rút gọn bằng UCLN trước khi cộng tử và mẫ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 😇