# Ôn tập TS10 & THTB 2025 - Đề 5: Editorial

>[!Note] Thông tin
>Sau đây là lời giải của Đề 5 trong chuỗi đề ôn tập TS10 & THTB 2025.
>
>**Bạn đọc có thể nộp và chấm bài** [TẠI ĐÂY](https://chuyentin-brvt.online/contest/algi_mockts10_2025_de5)s
>
>:::info
>Chuẩn bị bởi ==team Logica==, thuộc khuôn khổ dự án [**The Algitect (ALGI Project)**](https://www.facebook.com/algitect.project)
>:::

[toc]

## Bài 1: Bộ ba máy

### Subtask 1

Ta duyệt qua mọi bộ $3$ phần tử trong mảng rồi tìm giá trị $UCLN$ lớn nhất của chúng.

>[!Tip] Cách tính UCLN của ba số
> - $\text{UCLN}(x, y) =$ `__gcd(x, y)`
> - $\text{UCLN}(x,y,z) = \text{UCLN}(\text{UCLN}(x,y),z)$

**Độ phức tạp thời gian:** $O \left( n^3 \log \right)$.
> Với $\log$ tượng trưng cho độ phức tạp của hàm `__gcd()`.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int n, a[N+5];

int main() {
    cin>>n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    int res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < i; j++)
            for (int k = 1; k < j; k++)
                res = max(res, __gcd(__gcd(a[i], a[j]), a[k]));

    cout << res;

    return 0;
}

:::

### Subtask 2

>[!Tip] Nhận xét
> Vì $A_i \le 10^6$ mà $\text{UCLN}(x, y, z) \le \min(x, y, z)$, nên kết quả của bài chắc chắn sẽ nhỏ hơn hoặc bằng $10^6$.

Do đó, chúng ta có cách tiếp cận khác: ==Duyệt từng số $k$ và kiểm tra xem đó có phải $\text{UCLN}$ của một bộ ba số bất kỳ trong mảng hay không==.

Dễ thấy, nếu $k = \text{UCLN}(x, y, z)$ thì $k$ phải thỏa mãn:
$$
x \bmod k = y \bmod k = z \bmod k =0
$$

Hay $k$ là ==ước chung== của $x, y, z$, tức là trong mảng tồn tại ==ít nhất $3$ số== chia hết cho $k$.

Để thực hiện được điều trên, ta gọi $cnt_j$ là ==số lượng số j có trong mảng $A$==, và số $k$ thỏa mãn điều kiện nếu $\max(cnt_x) \ge 3$ với $x$ là bội của $k$.

>[!Caution] Giải thích
> Mặc dù số $k$ thỏa mãn điều kiện trên ==chưa chắc là $\text{UCLN}$ của $x, y, z$==.
>
> Tuy nhiên, điều này không ảnh hưởng đến kết quả, vì ta sẽ lấy ==kết quả lớn nhất==.
>
> >**VD:** $x = 4, y = 6, z = 8$
> >$k = 2$ thỏa, đồng thời $k = 4$ (đáp án chuẩn) cũng thỏa.

**Độ phức tạp thời gian:** $O \left( X \log X \right)$ với $X = \max(A_1, A_2, \dots, A_n)$.
> Với mỗi số từ $1$ đến $X$, ta phải duyệt qua tất cả các bội của nó. Do đó số thao tác là:
> $$
> \frac X1 + \frac X2 + \dots + \frac XX \approx X \log X
> $$

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int n, cnt[N+5], a[N+5];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }

    for (int x = N; x >= 1; x--) {
        int sum = 0;
        for (int j = x; j <= N; j += x) {
            //Duyệt qua tất cả bội của x
            sum += cnt[j];
            if (sum >= 3) {
                //Đã tìm thấy đáp án lớn nhất, ngừng chương trình
                cout << x;
                return 0;
            }
        }
    }
    
    return 0;
}

:::

## Bài 2: Mua hàng

### Subtask 1

>[!Tip]
> Ta có thể tính $k = \left \lceil \frac{r-l+1}{2} \right \rceil$ như sau:
> Tính $x$ bằng cách lấy $r-l+1$ chia nguyên cho 2: `x = (r-l+1)/2;`
> - Nếu $r-l+1$ lẻ thì $k = x + 1$.
> - Nêú $r-l+1$ chẵn thì $k = x$.

Vì mảng $A$ ==đã được sắp xếp tăng dần==, với mỗi truy vấn $(l, r)$ ta dễ dàng tính được trọng số của đoạn là $a_{l + \left \lceil \frac{r-l+1}{2} \right \rceil - 1}$. Sau đó chỉ cần so sánh giá trị này với $k$.

**Độ phức tạp thời gian:** $O \left( q\right)$

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
long long n, q, k, a[N+5], pre[N+5], l[N+5], r[N+5];

int main() {
    cin >> n >> q >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    while (q--) {
        int l, r;
        cin >> l >> r;
        
        int pos = (r-l+1)/2;
        if ((r-l+1) % 2 != 0) pos++;
        
        if (a[l+pos-1] <= k)
            cout << "YES\n";
        else
            cout<<"NO\n";
    }
    
    return 0;
}

:::

### Subtask 2

>[!Tip] Nhận xét
> Ta không cần ==tính chính xác trọng số của đoạn==.
>
> Thay vào đó ta chỉ cần quan tâm trọng số của đoạn ==lớn hơn hay nhỏ hơn $k$==.

Để giá trị nhỏ thứ $\left \lceil \frac{r-l+1}{2} \right \rceil$ của đoạn lớn hơn hoặc bằng $k$, thì mọi phần tử sau phần tử trên cũng phải lớn hơn hoặc bằng $k$, tức là đoạn đó phải có ít nhất $(r - l + 1) - \left \lceil \frac{r-l+1}{2} \right \rceil$ + 1 phần tử lớn hơn hoặc bằng $k$.
>**VD:** Đoạn có $5$ phần tử, $\left \lceil \frac{r-l+1}{2} \right \rceil = 3$. Để phần tử nhỏ thứ $3$ lớn hơn hoặc bằng $k$ thì mọi phần tử nhỏ thứ $3, 4, 5$ cũng phải lớn hơn hoặc bằng $k$.

Như vậy, bài toán trở thành ==đếm số lượng số trong đoạn lớn hơn hoặc bằng $k$==. Dễ dàng thực hiện được điều này bằng cách gán:
- Những số lớn hơn hoặc bằng $k$ thành $1$.
- Những số bé hơn $k$ thành $0$.

Sau đó sử dụng ==[mảng cộng dồn (prefix sum)](https://howkteam.vn/course/cau-truc-du-lieu-va-giai-thuat/prefix-sum-4280)== để tính nhanh số lượng số $1$ trong đoạn.

**Độ phức tạp thời gian:** $O \left( n \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int n, k, q, a[N+5], pre[N+5];

int main() {
    cin >> n >> q >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        
        if (a[i] > k) a[i] = 1;
        else a[i] = 0;
        
        pre[i] = pre[i-1] + a[i];
    }

    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        
        int len = (r - l + 1);
        int k = len/2;
        if (len % 2 != 0) k++;
        
        if (pre[r] - pre[l-1] >= len - k + 1)
            cout << "NO\n";
        else
            cout << "YES\n";
    }
    
    return 0;
}

:::

## Bài 3: Dịch bệnh

### Subtask 1

>[!Tip] Nhận xét
> Giá trị $d$ không thể lớn hơn phạm vi có đồng cỏ.
>
> Như vậy, vì $a \le b \le 10^4$ nên ==$d \le 10^4$==.

Ta có thể duyệt từng giá trị $d$ và kiểm tra xem giá trị này có hợp lệ hay không như sau:

Đi theo chiều dương của trục số, nếu ta đặt một con bò ở vị trí $i$ thì ta sẽ đặt con bò tiếp theo ở ==vị trí $j$ nhỏ nhất thỏa $j \ge i + len$== nhằm để dành những thảm cỏ ở xa hơn cho những con bò còn lại.

Để làm được như vậy, ta cần sắp xếp các đồng cỏ theo thứ tự tăng dần của đầu mút phải. Sau đó khởi tạo một con trỏ tại đồng cỏ đầu tiên tượng trưng cho vị trí để đặt bò, cùng lúc với việc đặt bò, ta sẽ di chuyển con trỏ từng chút một để ==tìm đồng cỏ gần nhất thỏa mãn điều kiện về khoảng cách==.

**Độ phức tạp thời gian**: $O(mX)$ với $X$ là phạm vi có cỏ.

:::success
:::spoiler Code

#include <bits/stdc++.h>
#define ii pair<long long,long long>
#define fi first
#define se second
using namespace std;
const int N = 1e6;
long long n, m, k, mx;
ii a[N+5];

bool check(long long len) {
    int pos = 1, cur = 1, cnt = 1;
    //pos: vị trí đặt bò hiện tại
    //cur: chỉ số của đồng cỏ đang xét
    
    while (pos+len <= mx) {
        //Nếu pos+len > mx thì không thể đặt thêm bò
        
        while (pos+len > a[cur].se && cur <= m) {
            //Nếu khoảng đồng cỏ cur không chứa tới pos+len
            //thì tìm đồng cỏ tiếp theo
            cur++;
        }
        
        if (cur > m) break;
        //Hết đồng cỏ, không đặt bò được
        
        pos = max(pos+len, a[cur].fi);
        cnt++;
        
        if (cnt == n) {
            //Đã đặt đủ n con bò
            return true;
        }
    }
    
    //Không đặt đủ n con bò
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i].fi >> a[i].se;
        mx = max(mx, a[i].se);
    }

    sort(a+1, a+1+m);
    for (int i = 10000; i >= 1; i--){
        if (check(i)) {
            //Đã tìm thấy đáp án
            cout << i;
            break;
        }
    }
    
    return 0;
}

:::

### Subtask 2

Kế thừa tư tưởng của subtask 1, tuy nhiên có thêm nhận xét quan trọng sau đây:

>[!Tip] Nhận xét
>Vì khoảng cách giữa hai con bò càng nhỏ thì số bò đặt được càng nhiều, ngược lại với khi khoảng cách càng lớn, nên:
>- Nếu tồn tại cách đặt $n$ con bò với $d = x$, các khoảng cách $d \lt x$ cũng thỏa mãn.
>- Nếu không tồn tại cách đặt $n$ con bò với $d = x$, các khoảng cách $d \gt x$ cũng sẽ không thỏa mãn.

Đây là điều kiện cần thiết để thực hiện ==[tìm kiếm nhị phân trên tập đáp án]()==. Thay vì phải duyệt hết mọi giá trị $d$ để thử, ta chỉ phải thử $\log X$ giá trị $d$ với $X$ là khoảng tối đa mà có tồn tại cỏ.

**Độ phức tạp thời gian**: $O(m \log X)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
#define ii pair<long long, long long>
#define fi first
#define se second
using namespace std;
const int N = 1e5;
long long n, m, k, mx;
ii a[N+5];

bool check(long long len) {
    long long pos = a[1].fi, cur = 1, cnt = 1;
    //pos: vị trí đặt bò
    //cur: chỉ số của đồng cỏ đang xét

    while (pos+len <= mx) {
        while (pos+len > a[cur].se && cur <= m) {
            cur++;
        }

        if (cur > m) break;

        pos = max(pos+len, a[cur].fi);
        cnt++;

        if (cnt == n) {
            //Đã đặt đủ n con bò
            return true;
        }
    }

    //Không đặt đủ n con bò
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i].fi >> a[i].se;
        mx = max(mx, a[i].se);
    }

    sort(a+1, a+1+m);

    long long l = 1, r = 1e18, res = 0;
    while (l <= r) {
        long long mid = (l+r)/2;
        if (check(mid)) {
            l = mid+1;
            res = mid;
        }
        else {
            r = mid-1;
        }
    }

    cout << res;

    return 0;
    }

:::

## Bài 4: Vương quốc

### Lời giải

Áp dụng ==quy hoạch động==.

- Định nghĩa:
- ==$dp_{1, i}$== là chi phí nhỏ nhất để chiếu đèn cho $i$ tòa nhà đầu tiên, trong đó tòa nhà thứ $i$ được chiếu đèn màu lam.
- ==$dp_{2, i}$== là chi phí nhỏ nhất để chiếu đèn cho $i$ tòa nhà đầu tiên, trong đó tòa nhà thứ $i$ được chiếu đèn màu chàm.
- ==$dp_{3, i}$== là chi phí nhỏ nhất để chiếu đèn cho $i$ tòa nhà đầu tiên, trong đó tòa nhà thứ $i$ được chiếu đèn màu tím.
- Khởi gán:
- ==$dp_{1, i} = a_1$==: Chiếu đèn màu lam cho tòa nhà $1$ tốn chi phí $a_1$.
- ==$dp_{2, i} = b_1$==: Chiếu đèn màu chàm cho tòa nhà $1$ tốn chi phí $b_1$.
- ==$dp_{3, i} = c_1$==: Chiếu đèn màu tím cho tòa nhà $1$ tốn chi phí $c_1$.
- Công thức (với $i \ge 2$):
- ==$dp_{1, i} = \min(dp_{2,i-1},dp_{3,i-1}) + a_i$==: Nếu chiếu đèn màu lam cho tòa nhà thứ $i$, thì tòa nhà thứ $i-1$ chỉ có thể chiếu đèn màu chàm hoặc tím.
- ==$dp_{2, i} = \min(dp_{1,i-1},dp_{3,i-1}) + b_i$==: Nếu chiếu đèn màu chàm cho tòa nhà thứ $i$, thì tòa nhà thứ $i-1$ chỉ có thể chiếu đèn màu lam hoặc tím.
- ==$dp_{3, i} = \min(dp_{1,i-1},dp_{2,i-1}) + c_i$==: Nếu chiếu đèn màu tím cho tòa nhà thứ $i$, thì tòa nhà thứ $i-1$ chỉ có thể chiếu đèn màu lam hoặc chàm.

- Kết quả: ==$\min(dp_{1, n}, dp_{2, n}, dp_{3, n})$==.

**Độ phức tạp thời gian:** $O(n)$

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6;
int n;
long long a[N+5], b[N+5], c[N+5], dp[5][N+5];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }

    for (int i = 1; i <= n; i++) {
        dp[1][i] = min(dp[2][i-1], dp[3][i-1]) + a[i];
        dp[2][i] = min(dp[1][i-1], dp[3][i-1]) + b[i];
        dp[3][i] = min(dp[1][i-1], dp[2][i-1]) + c[i];
    }

    cout << min({f[1][n], f[2][n], f[3][n]});

    return 0;
}

:::