Codeforces Round #702 (Div. 3) A, B & C

 Contest này giải được có 3 bài.

Được cái nghĩ sai problem F nên sub sai 2 sub - bằng chứng không thể chối cãi cho việc mình làm được mấy problem là do đề dễ.

---

A - Dense Array

Tóm tắt: Mảng $a$ được gọi là mảng dày đặc nếu xét 2 phần tử liên tiếp bất kỳ trong mảng, ta luôn thỏa điều kiện $\displaystyle \frac{\max(a_i, a_{i + 1})}{\min(a_i, a_{i + 1})} \leq 2$. Nếu 2 phần tử liên tiếp bất kỳ không thỏa điều kiện trên, bạn có thể chèn thêm bất kỳ phần tử nào vào giữa $a_i$ và $a_{i + 1}$. Tính số lần chèn ít nhất (hoặc có thể không chèn lần nào) để mảng $a$ trở thành mảng dày đặc như đề bài.

Hướng giải: Algoritham

$\displaystyle \frac{\max(a_i, a_{i + 1})}{\min(a_i, a_{i + 1})} \leq 2$ nghĩa là giữa 2 phần tử $a_i$ và $a_{i + 1}$ chênh lệch nhau nhiều nhất là 2 lần $\left(2 \min(a_i, a_{i + 1}) \leq max(a_i, a_{i + 1})\right)$. Do đó, mỗi cặp $a_i$ và $a_{i + 1}$ không thỏa điều kiện, ta chỉ cần gấp đôi $\min(a_i, a_{i + 1})$ đến khi lớn hơn hoặc bằng $\max(a_i, a_{i + 1})$. Đếm tổng số lần gấp đôi đó, ta thu được kết quả.

Code mẫu (C++). 

---

B - Balanced Remainders

Tóm tắt: Cho mảng $a$ gồm $n$ phần tử, $n \equiv 0 \pmod 3$. Trong một thao tác, bạn được chọn một vị trí $i$ và tăng $a_i$ lên một đơn vị (gán $a_i := a_i + 1$). Gọi

• $x$ là số phần tử chia 3 dư 0
• $y$ là số phần tử chia 3 dư 1
• $z$ là số phần tử chia 3 dư 2

Tìm xem cần phải thực hiện ít nhất bao nhiêu thao tác để $x, y, z$ bằng nhau.

Hướng giải: quan sát ta thấy

• Nếu tăng một số chia 3 dư 1 lên 1 đơn vị, ta sẽ thu được 1 số chia 3 dư 2. Khi đó $y$ giảm 1, $z$ tăng 1.
• Nếu tăng một số chia 3 dư 2 lên 1 đơn vị, ta sẽ thu được 1 số chia 3 dư 0. Khi đó $z$ giảm 1, $x$ tăng 1.
• Nếu tăng một số chia 3 dư 0 lên 1 đơn vị, ta sẽ thu được 1 số chia 3 dư 1. Khi đó $x$ giảm 1, $y$ tăng 1.

Vậy chừng nào $x, y, z$ còn chưa bằng nhau, ta cứ thực hiện tăng giảm phù hợp là được.

Code mẫu (C++).

---

C - Sum of Cubes

Tóm tắt: Cho số nguyên $x$, xác định xem có thể biểu diễn $x$ dưới dạng $a^3 + b^3 = x\ (1 \leq a, b \in \mathbb{Z})$ hay không?

Hướng giải: $\displaystyle a^3 + b^3 = x \iff a^3 = x - b^3 \iff a = \sqrt[\leftroot{3}\uproot{-1}\scriptstyle 3]{x - b^3}\ (a \in \mathbb{Z})$. Ta có thể duyệt hoặc binary search trên mảng $a$ tính toán sẵn. Code mẫu sử dụng phương pháp duyệt.

Code mẫu (C++).

---

Happy coding!