Bài 1: Đồng hồ

Author: 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

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

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

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

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\)).