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})}\le 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})}\le 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 $(2min(a_i,a_{i+1})\le max(a_i,a_{i+1}))$. 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(\mathrm{mod}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\le a,b\in \mathbb{Z})$ hay không?

Hướng giải: ${\displaystyle a^3+b^3=x⟺a^3=x-b^3⟺a=\sqrt[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!