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

>[!Note] Thông tin
>Sau đây là lời giải của Đề 2 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_de2)
>
>:::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: Truy đuổi

### Lời giải

Mô phỏng lại cuộc truy đuổi bằng cách đặt hai biến tượng trưng cho vị trí của rô-bốt và kẻ trộm. Sau mỗi giây, thay đổi hai vị trí này và kiểm tra khoảng cách.

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

:::success
:::spoiler Code

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

int n, k, p;

int main() {
    cin >> n >> k >> p;

    int ans = 0;
    long long robot = 0, thief = 0;
    while (n--) {
        long long x;
        cin >> x;

        robot += x;
        thief += k;

        if (abs(robot - thief) <= p) {
            ans++;
        }
    }

    cout << ans;
    return 0;
}

:::

## Bài 2: Bài toán khó

### Subtask 1

>[!Tip] Nhận xét
> Vì $\text{BCNN}(A, B) = n$ nên ta có $A, B$ là ước của $n$.

Thử duyệt qua mọi cặp ước của $n$, kiểm tra cặp số có thỏa mãn điều kiện không, sau đó lấy đáp án nhỏ nhất.

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

:::success
:::spoiler Code

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

long long n, m, res = 1e18;

long long __lcm(long long a, long long b) {
    return (a / __gcd(a, b) * b);
}

int main() {
    cin >> m >> n;
    for (long long i = 1; i*i <= n; i++)
        for (long long j = 1; j*j <= n; j++) {
            if (__gcd(i, j) == m && __lcm(i, j) == n)
                res = min(res, i + j);
            if (__gcd(n/i, j) == m && __lcm(n/i, j) == n)
                res = min(res, n/i + j);
            if (__gcd(i, n/j) == m && __lcm(i, n/j) == n)
                res = min(res, i + n/j);
            if (__gcd(n/i, n/j) == m && __lcm(n/i, n/j) == n)
                res = min(res, n/i + n/j);
        }

    if (res == 1e18) res = -1;
    cout << res;

    return 0;
}

:::

### Subtask 2

>[!Tip] Nhận xét
> Vì $\text{UCLN}(A, B) = m$ nên ta có $A, B$ là bội của $m$, viết lại thành:
> - $A = m \times x$
> - $B = m \times y$
> > Với $x, y$ là các số nguyên dương.

Lại có:
$$
\begin{flalign}
\text{BCNN}(A, B) &= \frac {A \times B}{\text{UCLN}(A, B)} = \frac {m \times x \times m \times y}{m} = m \times x \times y \\
\Leftrightarrow n = m \times x \times y \\
\Leftrightarrow x \times y = \frac n m
\end{flalign}
$$
Như vậy, nếu $n$ không chia hết cho $m$ thì không tồn tại đáp án thỏa mãn, ngược lại ta có $x$ và $y$ là ước của $\frac n m$ đồng thời $x \times y = \frac n m$.

Duyệt các cặp $(x,y)$ bằng cách duyệt qua các ước của $\frac n m$, tính $A = m \times x$, và $B = m \times y$, sau đó kiểm tra điều kiện $\text{UCLN}(A, B) = m$

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

:::success
:::spoiler Code

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

long long m, n;

int main() {
    cin >> m >> n;

    if (n % m != 0) {
        cout << -1;
        return 0;
    }

    long long s = n / m;
    long long ans = LLONG_MAX;

    for (long long x = 1; x * x <= s; ++x) {
        if (s % x == 0) {
            long long y = s / x;
            long long a = m*x, b = m*y;
            if (__gcd(a, b) == m) {
                ans = min(ans, a + b);
            }
        }
    }

    cout << (ans == LLONG_MAX ? -1 : ans);
    return 0;
}

:::

## Bài 3: Mật mã

### Lời giải

Bài toán này chỉ kiểm tra khả năng sử dụng kiểu dữ liệu xâu.

>[!Important] Chữ số và kí tự
> Cần phải hiểu, trong kiểu dữ liệu xâu, kí tự `9` khác với giá trị số 9. Ký tự này mang một giá trị mã ASCII để thực hiện tính.
>
> **VD:**
> `9` = $57$ trong bảng mã ASCII.
> `A` = $65$ trong bảng mã ASCII.
>
> Để thao tác với số `9`, ta cần lấy giá trị $9$ của nó bằng cách lấy kí tự `9` - `0`:
> - `9` = $57$ trong bảng mã ASCII.
> - `0` = $48$ trong bảng mã ASCII.
> - `9` - `0` = $57 - 48$ = $9$.
> > Nguyên lí này dựa vào việc các số `0`, `1`, `2`, ..., `9` được sắp xếp liền kề và tăng dần trong bảng mã ASCII, có giá trị từ $48$ đến $57$

Trong bảng mã ASCII, các chữ cái in hoa `A`, `B`, ..., `C` được xếp liền kề nhau. Do đó, khi dịch các chữ cái ta chỉ việc cộng thêm vào ký tự một khoảng cần dịch.

>[!Caution] Lưu ý
> Ta cần mô phỏng việc xoay vòng bảng chữ cái (khi hết ký tự `Z` thì quay lại kí tự `A`).
>
> Dễ dàng thực hiện điều này bằng câu lệnh điều kiện.

**Độ phức tạp thời gian:** $O \left( L \right)$ với $L$ là độ dài xâu.

:::success
:::spoiler Code

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

string s;

int main() {
    cin >> s;
    string res = "";

    for (int i = 0; i < s.size(); i += 2) {
        //Lấy số bước dịch chuyển
        int step = s[i+1] - '0';
        
        //Nếu cộng vào vượt ra khỏi `Z`, cần quay lại `A`.
        if (s[i] + step > 'Z') step -= 26;
        
        res.push_back(s[i] + step);
    }

    cout << res;
    return 0;
}

:::

## Bài 4: Tuyến xe buýt

### Subtask 1

Với $k = 2$, ta thử mọi cặp vị trí để mở trạm.

Giả sử ta mở hai trạm $i, j \; (i \lt j)$, ta có:
- Hành khách đi qua cổng $i$ để đến trạm $i, i+1, \dots, j-1$.
- Hành khách đi qua cổng $j$ để đến trạm $j+1, j+2, \dots, n, 1, 2, \dots, i-1$.

Để dễ xử lý, nhất là trường hợp thứ hai, đoạn bị cắt ra làm hai phần (cuối mảng và đầu mảng), thì ta thực hiện ==nhân đôi mảng ban đầu==. Khi đó, vị trí $n+1, n+2, \dots$ cũng tương ứng với vị trí $1, 2, \dots$

>[!Tip] Tính nhanh tổng quãng đường
> Để tính nhanh được giá trị này, ta cần lưu hai ==mảng cộng dồn== như sau:
> - $S$ là mảng cộng dồn thông thường với $S_i = A_1 + A_2 + \dots + A_i$.
> - $F$ là mảng cộng dồn "bậc thang" với $F_i = A_1 + A_2\times 2 + A_3 \times 3 + \dots + A_i \times i$.
>
> Khi đó, từ trạm $i$, tổng chi phí để đến các trạm $i+1, i+2, \dots, j$ là:
> $$
> \begin{flalign}
> &r_{i+1} \times 1 + r_{i+2} \times 2 + \dots + r_j \times (j - i) \\
> &= (r_i \times i + r_{i+1} \times (i+1) + r_{i+2} \times (i+2) + \dots + r_j \times j) - i \times (r_i + r_{i+1} + \dots + r_j) \\
> &= F_j - F_{i-1} - i \times (S_j - S_{i-1})
> \end{flalign}
> $$

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

:::success
:::spoiler Code

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

const int K = 7, N = 100;
const long long MX = 1e18;

int n, k, A[N+1];
long long S[2*N+1], F[2*N+1], res = MX;

long long cost(int i, int j) {
    if (j < i) j += n;
    return F[j] - F[i-1] - (S[j] - S[i-1])*i;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
        S[i] = S[i-1] + A[i];
        F[i] = F[i-1] + (long long)i*A[i];
    }

    for (int i = n+1; i <= 2*n; i++) {
        S[i] = S[i-1] + A[i-n];
        F[i] = F[i-1] + (long long)i*A[i-n];
    }

    for (int i = 1; i <= n; i++)
        for (int j = i+1; j <= n; j++)
            res = min(res, cost(i, j-1) + cost(j, i-1));

    cout << res;

    return 0;
}

:::

### Subtask 2

>[!Tip] Bài toán con
> Xét bài toán đơn giản hơn như sau:
>
> *Cho $n$ trạm xe buýt xếp thành một hàng thẳng được đánh số từ $1$ đến $n$ từ trái sang phải. Từ trạm $i$ chỉ có thể đi đến trạm $i+1$. Chỉ có $k$ trạm được mở, mỗi trạm có chỉ tiêu $r_i$ hành khách. **Tìm tổng quãng đường ít nhất các hành khách phải di chuyển mà vẫn đạt chỉ tiêu.***
>
> Bản chất, bài toán này là bài toán ==chia đoạn thành $k$ nhóm liên tiếp==. Trong đó, để ghép một đoạn liên tiếp $i, i+1, i+2, \dots, j$ thành một nhóm sẽ mất chi phí là tổng quãng đường để các hành khách xuất phát từ trạm $i$ và đến trạm $i+1, i+2, \dots, j$.
>
> **Đó là:**
> $$
> r_{i+1} \times 1 + r_{i+2} \times 2 + \dots + r_j \times (j - i)
> $$
>
> Để tính chi phí này nhanh cho nhiều đoạn, có thể áp dụng ==mảng cộng dồn== như subtask trước, hoặc duyệt ngược và duy trì tổng hậu tố (xem code để rõ hơn).

:::success
Nếu xem xét kỹ, để giải bài toán gốc, ta chỉ cần giải bài toán con như trên với vị trí bắt đầu lần lượt là $1, 2, \dots ,n$. Sau đó lấy ==đáp án nhỏ nhất==.

**VD:** Với $n$ = 5. Đặt vị trí bắt đầu là $3$, ta có $n$ trạm xe buýt thẳng hàng là:
$$
3, 4, 5, 1, 2
$$
:::

==**SAU ĐÂY LÀ HƯỚNG DẪN GIẢI BÀI TOÁN CON**==

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

- **Định nghĩa:** ==$dp_{i, j}$== là tổng quãng đường nhỏ nhất các hành khách phải đi thỏa mãn $n$ trạm đều đạt chỉ tiêu, khi đã mở cửa $i$ trạm, và $j$ trạm đầu tiên đạt chỉ tiêu.
- **Khởi gán:**
- ==$dp_{0, 0} = 0$==: Khi chưa mở cửa trạm nào thì cũng không trạm nào đạt chỉ tiêu.
- ==Mọi giá trị $dp$ còn lại== gán bằng $\infty$.
- **Công thức:**
- ==$dp_{i, j} = \min(dp_{i-1, t-1} + C(t, j))$== với $1 \le t \le j$ và $C(t, j)$ là tổng quãng đường để hành khách đi từ trạm $t$ đến các trạm $t+1, t+2, \dots, j$. Tức là thử các TH sau:
- Ghép trạm $j$ thành một nhóm
- Ghép trạm $j, j-1$ thành một nhóm
- ...
- Ghép giạm $1, 2, \dots, j$ thành một nhóm

- **Kết quả:** ==$dp_{k, n}$==: Mở cửa $k$ trạm, và cả $n$ trạm đều đạt chỉ tiêu.

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

:::success
:::spoiler Code

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

const int K = 10, N = 100;
const long long MX = 1e18;
int n, k, A[N+1], B[N+1];
long long dp[K+1][N+1], res = MX;

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

    for (int beg = 1; beg <= n; beg++) {
        for (int i = 1; i <= n; i++) {
            int pos = beg + i - 1;
            if (pos > n) pos -= n;
            B[i] = A[pos];
        }

        for (int p = 0; p <= k; p++)
            for (int i = 0; i <= n; i++)
                dp[p][i] = MX;

        dp[0][0] = 0;
        for (int p = 1; p <= k; p++)
            for (int i = 1; i <= n; i++) {
                long long sum = 0, cost = 0;
                for (int j = i; j >= 1; j--) {
                    cost += sum;
                    sum += B[j];
                    dp[p][i] = min(dp[p][i], dp[p-1][j-1] + cost);
                }
            }

        res = min(res, dp[k][n]);
    }

    cout << res;

    return 0;
}

:::