Educational Codeforces Round 108 (Rated for Div. 2) - A & B

Code nhiều nhưng vẫn ngu

---

A. Red and Blue Beans

Tóm tắt: có $r$ hạt đậu đỏ, $b$ hạt đậu xanh. Ta chia số đậu này thành nhiều (có thể chỉ chia 1 túi) túi đậu, mỗi túi có $r_t$ hạt đậu đỏ và $b_t$ hạt đậu xanh sao cho:

• Mỗi túi có ít nhất 1 hạt đậu đỏ $(r_t \geq 1)$
• Mỗi túi có ít nhất 1 hạt đậu xanh $(b_t \geq 1)$
• Chênh lệch giữa số đậu đỏ và đậu xanh trong túi không vượt quá $d\ (|r_t - b_t| \leq d)$

Tìm xem có thể chia đậu theo yêu cầu hay không?

Hướng dẫn: bài này có thể làm greedy: nhận thấy chênh lệch tối đa giữa số đậu đỏ và đậu xanh trong mỗi túi là $d$, vậy ta chia mỗi túi gồm 1 hạt đậu đỏ và $d + 1$ hạt đậu xanh, nếu cuối cùng còn lại một lượng đậu không thể chia ($r > 0$ hoặc $b > 0$) thì kết luận không thể chia.

Code mẫu (C++)

---

B. The Cake Is a Lie

Tóm tắt: cho lưới có kích thước $n \times m$, bạn đang đứng ở ô $(1, 1)$ và bạn muốn đi đến ô $(n, m)$. Chi phí di chuyển được tính như sau:

Nếu đi từ ô $(x, y)$ sang ô $(x, y + 1)$, chi phí di chuyển là $x$.

Nếu đi từ ô $(x, y)$ sang ô $(x + 1, y)$, chi phí di chuyển là $y$.

Tìm xem có đường đi nào từ ô $(1, 1)$ đến $(n, m)$ tốn chi phí là $k$ hay không.

Hướng dẫn: đường đi từ $(1, 1)$ đến $(n, m)$ tốn chi phí $(n - 1) + n \times (m - 1)$ (độ dài đi theo Khoảng cách Manhattan).

Code mẫu (C++)

---

Happy coding!