# Bài 1: Đồng hồ

Author: [noodles0428](https://oj.duong3982.com/user/noodles0428)

Gọi giờ hiện tại là $n$ và $k$ là phút hiện tại. Dễ thấy, thời gian hiện tại (tính bằng phút) là: $n \times 60 + k$

Tại thời điểm $9$ giờ, dễ thấy số phút là $540$ phút.

Qua đó, ta sẽ tìm số phút $x$ sao cho: $n \times 60 + k + x \equiv 540$ (mod $720$)

=> $x = 540 - (n \times 60 + k)$ (mod $720$)

Bên cạnh đó, nếu $x < 0$, ta sẽ cộng $x$ lên $720$.

# Bài 2: Mua hoa

Author: [noodles0428](https://oj.duong3982.com/user/noodles0428)

Dễ thấy, nếu như ta duyệt số lượng bông hoa, ta sẽ dẫn đến tình trạng TLE (do $n \le 10^9$).

Chính vì vậy, ta sẽ tiếp cận bài toán như sau: Duyệt qua từng **nhóm hoa** và tính tổng chi phí của mỗi nhóm cho đến khi đạt $n$ bông hoa.

Do ta có công thức tính tổng như sau:

$1 + 2 + ... + n$ = $\frac{(n + 1) \times n}{2}$

=> Độ phức tạp trung bình của cách tiếp cận này là O($\sqrt{n}$), hoàn toàn thỏa mãn với điều kiện đề bài.

# Bài 3: Đèn lồng

Author: [noodles0428](https://oj.duong3982.com/user/noodles0428)

Nhận xét: Một đèn ở vị trí $x$ bị đổi trạng thái nếu $i$ là ước của $x$.

Do đó, số lần đảo trạng thái của $x$ chính là **số ước** của $x$.

Để đèn lồng bật sau khi thực hiện thao tác, thì số ước của $x$ phải là số lẻ. Mà một số có số ước lẻ khi và chỉ khi đó là số chính phương.

(Bạn đọc tự chứng minh tính chất này).

=> Đáp số của bài toán chính là phần nguyên của $\sqrt{n}$.

# Bài 4: Ghép số

Author: [noodles0428](https://oj.duong3982.com/user/noodles0428)

Nhận xét: Ta chỉ cần quan tâm tới $3$ số có số chữ số lớn nhất. Nếu số chữ số lớn nhất nhỏ hơn $3$, ta sẽ quan tâm tiếp tới các số có số chữ số nhỏ hơn.

Thật vậy, chuyển hết các số ban đầu dưới dạng `string`, lưu vào mảng $a$. Sắp xếp mảng $a$ ưu tiên theo:
- Số chữ số theo thứ tự giảm dần.
- Nếu số chữ số bằng nhau, sắp xếp theo giá trị theo thứ tự giảm dần.

Nhận thấy, ta chỉ cần quan tâm duy nhất $3$ giá trị đầu tiên trong mảng. Từ đó, ta có thể duyệt hoán vị để kiểm tra xem đâu là cách sắp xếp lớn nhất.

Độ phức tạp: O($nlog(n)$), do phụ thuộc vào thuật toán sắp xếp.

# Bài 5: Chia đoạn

Author: [huyjavalt](https://oj.duong3982.com/user/huyjavalt)

Ta sẽ lưu toàn bộ các giá trị có thể là tổng của 1 đoạn con bất kỳ vào một vector, gọi đó là $vec$.

Lúc này, ta sẽ duyệt mọi cặp giá trị trong $vec$ và xem có tồn tại cách chia dãy $a$ thành các đoạn, mà $min$ của cả đoạn là $vec_i$, và $max$ của đoạn là $vec_j$ hay không.

Ta sẽ xây dựng hàm

bool check (int mn, int mx)

với ý nghĩa: có tồn tại cách chia dãy thành các đoạn con, mà đoạn nhỏ nhất có tổng là $mn$, đoạn lớn nhất có tổng là $mx$ hay không.

Gọi $ps_i = a_1 + a_2 + \cdot \cdot \cdot + a_i$.

Gọi $f_{i, j}$ là số cách chia $j$ phần tử đầu tiên vào $i$ đoạn con.

Đầu tiên ta có : $f_{1, j} = (ps[i] >= mn$ $\&$ $ps[i] <= mx)$.
Với mỗi con $i >= 2$, ta sẽ phải nối con $j$ với 1 con $j'$ sao cho $mn <= ps_j - ps_{j'-1} <= mx$.

Dễ thấy, khi $j$ tăng thì đoạn $j'$ thỏa mãn sẽ dịch lên 1 đoạn nên ta sẽ có ý tưởng dùng kỹ thuật two pointer.

Gọi $l$ là con $j'$ nhỏ nhất thỏa mãn và $r$ là con $j'$ lớn nhất thỏa mãn, ta có $ps_j$ luôn tăng nên $l$ và $r$ sẽ tăng khi $j$ tăng.

Việc còn lại chỉ là kiểm tra xem trong đoạn $f_{i-1,l}$ đến $f_{i-1,r}$ có con nào thỏa mãn không (Có thể dễ dàng kiểm tra bằng prefix sum).

Độ phức tạp : O($n^3 \times k$).