# Bài THREE

Có ba trường hợp để ghép số thành một tập hợp có tổng bằng 3: $\{3\}$, $\{1, 2\}$ và $\{1, 1, 1\}$. Ta đặt $f(x)$ là kết quả bài toán, $f(x) = c + x + \lfloor \frac{a - x}{3} \rfloor$, với $x$ là số tập hợp $\{1, 2\}$.

$f(x) \le f(x+1)$
$\Leftrightarrow c + x + \lfloor \frac{a - x}{3} \rfloor \le c + x + 1 + \lfloor \frac{a - x - 1}{3} \rfloor$
$\Leftrightarrow \lfloor \frac{a - x}{3} \rfloor \le \lfloor \frac{a - x - 1}{3} \rfloor + 1$
$\Leftrightarrow \lfloor \frac{a - x}{3} \rfloor \le \lfloor \frac{a - x + 2}{3} \rfloor$

$f(x)$ sẽ luôn không giảm khi $x$ tăng, ta "tham lam" chia nhiều nhóm $\{1, 2\}$ nhất có thể. Kết quả bài toán sẽ "tối ưu" nhất khi $x=min(a, b)$.

Kết quả cuối cùng, $c + min(a, b) + \lfloor \frac{a - min(a, b)}{3} \rfloor$.

# Bài TRANSFORM

Khi nhân đôi $A$ thì ta thu được $A$ là **số chẵn**, còn thêm số 1 vào cuối $A$ ta được **số lẻ và tận cùng là 1**. Thay đổi bài toán, thay vì kiểm tra $A \rightarrow B$, ta kiểm tra $B \rightarrow A$. Với bải toán ban đầu, từ $A$ ta phải chọn một trong hai phép biến đổi, còn với bài toán "ngược", từ $B$ chỉ có **nhiều nhất một** phép biến đổi. Hai phép biến đổi từ $B$:
- Chia đôi gíá trị $B$ (nếu $B$ là số chẵn)
- Xóa số 1 tận cùng của giá trị $B$ (nếu $B$ tận cùng là số 1)

Ta sẽ liên tục biến đổi $B$ cho đến khi gặp $A$, dùng vòng lặp. Trong trường hợp $B$ không thể biến đổi thành $A$, ta sẽ dừng vòng lặp biến đổi khi $B$ nhỏ hơn $A$ (vì sau khi biển đổi $B$ luôn giảm).

# Bài SWORD

Để tiêu diệt con boss $i$, ta cần có sức mạnh, $P \ge p_i$.
Sau khi tiêu diệt con boss $i$, ta được tăng sức mạnh, $P = P + g_i$.

Luôn ưu tiên tiêu diệt con boss có sức mạnh nhỏ hơn, vì:
- Nếu ta tiêu diệt được boss mạnh hơn thì ta luôn tiêu diệt được boss yếu hơn.
- Ngoài ra, có trường hợp ta **không thể** tiêu diệt boss mạnh hơn, nhưng sao
khi tiêu diệt boss yếu hơn và được cộng sức mạnh ta **có khả năng** tiêu diệt được boss mạnh hơn.

Đối với bài này, ta chỉ cần sắp xếp các con boss theo thứ tự tăng dần về sức mạnh, sau đó tiêu diệt theo thứ tự đó.

# Bài COLORBOX

Sau khi bỏ đi một đoạn bất kì, các cây màu còn lại có dạng: "đoạn đầu" $a_1, a_2, ..., a_l$ và đoạn sau $a_r, a_{r+1}, ..., a_n$, tất cả các cây màu có giá trị đôi một khác nhau.

Duyệt các cặp số $(l, r)$ thỏa mãn. Duyệt $l$ từ $0$ đến $n$, và duy trì $r$ là giá trị nhỏ nhất (gần với $l$ nhất để đoạn bỏ đi là nhỏ nhất) thỏa mãn điều kiện. Vì khi $l$ tăng (đoạn đầu thêm màu) thì $r$ cũng sẽ tăng theo (đoạn sau ít màu lại, nếu trùng với màu đã thêm ở đoạn đầu).

Ở đây, ta sử dụng thêm một CTDL (mảng hoặc vector) để duy trì các màu (đã hoặc chưa có) và kĩ thuật "Hai con trỏ" để duyệt $(l, r)$.