# Đề TS10 - BRVT - 2021: Editorial

>[!Note] Thông tin
>Sau đây là lời giải của Kỳ thi Tuyển sinh 10 trường THPT chuyên Lê Quý Đôn tỉnh Bà Rịa - Vũng Tàu năm học 2021 - 2022.
>
>**Bạn đọc có thể nộp và chấm bài (test tự sinh)** [TẠI ĐÂY](https://chuyentin-brvt.online/contest/algi_ts10_15_24).
>
>:::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:
### Tóm tắt đề bài
Cho số nguyên dương $n$. Yêu cầu tính:
$$
\begin {flalign}
S &= \frac{2}{3} + \frac{3}{4} + \cdots + \frac{n-1}{n} \\
T &= \frac{1}{3} - \frac{1}{3^2} + \frac{1}{3^3} - \cdots + \frac{1}{3^{2n-1}} - \frac{1}{3^{2n}}
\end {flalign}
$$

**Dữ liệu đảm bảo: $3 \le n \le 100$**.

### **Tính S**
Cho biến $i$ chạy vòng lặp từ $3$ đến $n-1$, cộng ==$\frac{i-1}{i}$== vào kết quả.

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

### **Tính T**
>[!Tip]Nhận xét:
>$$
>\frac {1}{3^i} = \frac{1}{3^{i-1}} \cdot \frac{1}{3}
>$$

Với mỗi số hạng từ $1$ đến $2n$, duy trì một biến ==$cur = \frac{1}{3^i}$== là giá trị của số hạng đang xét, nếu ==$i$ lẻ==, cộng $cur$ vào đáp án, ngược lại trừ đáp án đi $cur$.

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

### **Mã nguồn mẫu**

:::info
Độ phức tạp thời gian của cả bài toán là ==tổng độ phức tạp thời gian== của từng yêu cầu.
:::

:::success
:::spoiler Code

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

int main(){
    int n;
    cin >> n;
    
    double S = 0.0, T = 0.0;
    
    for (int i = 3; i <= n; i++) {
        S += 1.0 * (i-1) / i;
    }

    double cur = 1.0 / 3;
    for (int i = 1; i <= 2*n; i++) {
        if (i % 2 == 1 {
            T += cur;
        }
        else {
            T -= cur;
        }
        cur /= 3;
    }

    cout << fixed << setprecision(5) << S << '\n' << T;

    return 0;
}

:::

## Bài 2:

### Tóm tắt đề bài
Cho số nguyên dương $n$ và $a$, thực hiện các yêu cầu:
- Tìm số nguyên $k$ là số $n$ sau khi đã xóa đi tất cả các số $0$.
- Tìm chữ số tận cùng của $a^n$.

**Dữ liệu đảm bảo:** $2 \le n \le 10^{18}$ và $1 \le a \le 100$.

### **Yêu cầu 1**

Dùng cấu trúc dữ liệu [**vector**](https://blog.28tech.com.vn/stl-vector-trong-c), lần lượt tách và đưa từng chữ số sau cùng của $n$ (tức là $n \bmod 10$) vào vector (ngoại trừ các chữ số $0$). Sau đó, loại bỏ chữ số đó đi bằng cách chia $n$ cho $10$.

### **Yêu cầu 2**

>[!Tip] Nhận xét
>Đáp an của bài toán là $a^n \bmod 10$.

Để tính $a^n \bmod 10$ một cách nhanh chóng, dùng [**lũy thừa nhị phân**](https://wiki.vnoi.info/algo/algebra/binary_exponentation.md) kết hợp với modulo trong lúc tính.

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

### **Mã nguồn mẫu**

:::info
Độ phức tạp thời gian của cả bài toán là ==tổng độ phức tạp thời gian== của từng yêu cầu.
:::

:::success
:::spoiler Code

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

long long n;
int a;

int Pow(int a, long long n) {
    if (n == 0) {
        return 1;
    }
    
    int tmp = Pow(a, n/2);
    tmp = tmp * tmp;
    if (n % 2 == 1) {
        tmp = tmp * a;
    }
    
    return tmp % 10;
}

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

    //Yêu cầu 1
    long long tmp = n;
    vector<int> digits;
    
    while (tmp > 0) {
        if (tmp % 10 != 0) {
            digits.push_back(tmp % 10);
        }
        tmp /= 10;
    }
    
    for (int i = digits.size()-1; i >= 0; i--) {
        cout << digits[i];
    }
    
    cout << '\n';

    //Yêu cầu 2
    cout << Pow(a, n);

    return 0;
}

:::

## Bài 3:

### Tóm tắt đề bài
Cho hai số nguyên dương $n$, $k$ và dãy số nguyên nguyên dương $A_1, A_2, A_3, \dots, A_n$. Thực hiện các yêu cầu:
- In ra các số $A_i$ có dạng $A_i = 5 \cdot h + 2 \left(h \in N \right)$.
- In ra số lượng số nguyên tố trong dãy.
- In ra khoảng cách lớn nhất giữa hai số chính phương (số lượng phần tử nhiều nhất nằm giữa hai số chính phương) trong dãy. In ra $-1$ nếu không tồn tại hai số chính phương.
- Chia dãy số thành hai phần sao cho: Phần thứ nhất có $k$ phần tử, phần thứ hai có $n-k$ phần tử. In ra độ chênh lệch lớn nhất giữa tổng của hai phần.

**Dữ liệu đảm bảo:** $2 \le k \le n \le 10^5$ và $1 \le A_i \le 10^7$.

### **Yêu cầu 1**

>[!Note]Nhận xét
>$$
>\begin {flalign}
>A_i &= 5h + 2 \\
>\Leftrightarrow 5h &= A_i - 2 \\
>\Leftrightarrow h &= \frac {A_i - 2}{5}
>\end {flalign}
>$$
> Mà $h$ nguyên, do đó $A_i - 2$ chia hết cho $5$, hay ==$\left(A_i - 2\right) \bmod 5 = 0$==.

Như vậy, ta duyệt qua dãy và in ra các số thỏa mãn điều kiện trên.

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

### **Yêu cầu 2**

Vì $A_i \le 10^7$, có thể dùng kĩ thuật [**sàng nguyên tố**](https://wiki.vnoi.info/algo/algebra/prime_sieve.md), sau đó với mỗi số $A_i$ kiểm tra nhanh xem nó có phải số nguyên tố hay không và đếm.

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

### **Yêu cầu 3**

>[!Tip]Kiểm tra số chính phương
>:::success
>==Số chính phương== là bình phương của một số nguyên.
>:::
>Ta có thể kiểm tra một số $x$ có phải số chính phương hay không bằng cách lấy ==bình phương phần nguyên của $\sqrt x$== so sánh với ==$x$==.
>Nghĩa là, $x$ chính phương khi và chỉ khi:
>$$
>\left \lfloor \sqrt x \right \rfloor ^ 2 = x
>$$

Để khoảng cách giữa hai số chính phương được chọn là xa nhất, ta chọn số chính phương ==đầu tiên== và ==cuối cùng== của dãy.

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

### **Yêu cầu 4**

>[!Note]Nhận xét:
>Chênh lệch giữa hai phần là lớn nhất khi một phần đạt tổng lớn nhất có thể và phần còn lại phải nhỏ nhất có thể.
>
>Dễ dàng nhận thấy:
>- Nếu $k \ge n-k$, ta nhóm ==$k$ phần tử lớn nhất== chung với nhau và ==$n-k$ phần tử nhỏ nhất== chung với nhau
>- Nếu $k \lt n-k$, ta nhóm ==$n-k$ phần tử lớn nhất== chung với nhau và ==$k$ phần tử nhỏ nhất== chung với nhau

Có thể tìm nhanh tập các phần tử lớn nhất hoặc nhỏ nhát bằng cách sắp xếp lại dãy số.

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

### **Mã nguồn mẫu**

:::info
Độ phức tạp thời gian của cả bài toán là ==tổng độ phức tạp thời gian== của từng yêu cầu.
:::

:::success
:::spoiler Code

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

const int N = 1e5 + 5;
const int A = 1e7 + 5;
int n, a[N], k, isPrime[A];

bool isSquare(int n) {
    int tmp = sqrt(n);
    
    if (tmp * tmp == n) {
        return 1;
    }
    
    return 0;
}

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

    /// Yêu cầu 1
        for (int i = 1; i <= n; i++) {
            if ((a[i]-2) % 5 == 0) cout << a[i] << ' ';
        }
    
        cout << '\n';

    /// Yêu cầu 2
        isPrime[1] = 1;
        for (int i = 2; i*i <= 1e7; i++) {
            if (isPrime[i] == 0) {
                for (int j = i*i; j <= 1e7; j += i) {
                    isPrime[j] = 1;
                }
            }
        }

        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (isPrime[a[i]] == 0) {
                cnt++;
            }
        }
    
        cout << cnt << '\n';

    /// Yêu cầu 3
        int L = -1, R = -1;
        for (int i = 1; i <= n; i++) {
            if (isSquare(a[i])) {
                if (L == -1) L = i;
                R = i;
            }
        }
    
        if (L == R) {
            cout << -1 << '\n';
        }
        else {
            cout << R - L - 1 << '\n';
        }

    /// Yêu cầu 4
        sort (a+1, a+1+n);
        k = min(k, n-k);
    
        long long S_max = 0, S_min = 0;
        for (int i = 1; i <= n; i++) {
            if (i > k) {
                S_max += a[i];
            }
            else {
                S_min += a[i];
            }
        }
    
        cout << S_max - S_min;

    return 0;
}

:::

## Bài 4:

### Tóm tắt đề bài

Cho số nguyên $n$ và dãy số nguyên $A_1, A_2, A_3,\dots, A_n$.

**Yêu cầu:** Chia dãy $A$ thành hai phần sao cho ==tổng của mỗi phần đều là số nguyên tố== và ==chênh lệch giữa hai phần là nhỏ nhất==. In ra $-1$ nếu không có cách chia.

**Dữ liệu đảm bảo:** $2\le n \le 100$ và $1 \le A_i \le 10^4$.

### Lời giải

Áp dụng ==quy hoạch động cái túi==.

**Định nghĩa:** $F_i$ là khả năng tạo ra tổng bằng $i$ từ các phần tử trong dãy:
- $F_i = 1$, có thể tạo được tổng $i$.
- $F_i = 0$, không thể tạo được tổng $i$.

**Khởi gán:** $F_0 = 1$ (không sử dụng phần tử nào).

**Công thức:** Xét mọi phần tử $A_i$ và mọi tổng $j$ bất kỳ. Nếu $j - A_i \ge 0$ và $F_{j-A_i} = 1$ thì $F_j = 1$.

>[!Important] Lưu ý
>Ta tính $F_j$ dựa vào $F_{j-A_i}$ và $j - A_i \lt j$ nên cần duyệt $j$ giảm dần, để khi lấy $F_{j-A_i}$ ta đảm bảo đó là đáp án chưa được cập nhật bởi $A_i$.

>[!Tip]Nhận xét
>Gọi tổng của cả dãy số là $sum$.
>:::success
>Chênh lệch giữa hai phần là nhỏ nhất khi ==tổng của hai phần gần với $\frac {sum}{2}$== nhất.
>:::
>Trong hai phần, sẽ luôn có một phần với tổng $D \le \frac {sum}{2}$ và phần còn lại là $sum - D$ lớn hơn hoặc bằng $\frac {sum}{2}$.
>
> Không mất tính tổng quát, ta chỉ cần tính $D \le \frac {sum}{2}$. Đáp án tối ưu khi ==D lớn nhất==.

Đáp án hợp lệ khi ==$D$ và $sum - D$ là số nguyên tố==, ta có thể kiểm tra điều này bằng kĩ thuật [**sàng nguyên tố**](https://wiki.vnoi.info/algo/algebra/prime_sieve.md).

**Độ phức tạp thời gian:** $O(n \cdot \sum_{i=1}^n {A_i} + n \log \log n)$
> $n \cdot \sum_{i=1}^n {A_i}$: Quy hoạch động.
> $n \log \log n$: Sàng nguyên tố.

### **Mã nguồn mẫu**

:::success
:::spoiler Code

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

const int N = 102 + 5;
const int S = 1e6 + 5;
int n, isPrime[S], a[N], f[S], sum;

int main(){
    isPrime[1] = 1;
    for (int i = 2; i*i <= 1e6; i++) {
        if (isPrime[i] == 0) {
            for (int j = i*i; j <= 1e6; j += i) {
                isPrime[j] = 1;
            }
        }
    }

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

    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1e6; j >= a[i]; j--) {
            f[j] = max(f[j], f[j - a[i]]);
        }
    }

    int res = -1;
    for (int i = 1; i <= sum/2; i++) {
        if (isPrime[i] == 0 && f[i] == 1 && isPrime[sum-i] == 0 && f[sum-i] == 1) {
            res = i;
        }
    }

    if (res == -1) {
        cout << -1;
    }
    else {
        cout << res << ' ' << sum - res << ' ' << sum - 2*res;
    }
    
    return 0;
}

:::