# Đề TS10 - BRVT - 2020: 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 2020 - 2021.
>
>**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

Nhập vào một số nguyên dương $n$.

**Yêu cầu**: Tính giá trị các biểu thức:
$$\begin {flalign}\
A &= \frac{1}{6}+\frac{2}{7}+\dots+\frac{2n-1}{2n + 4}
\\
B &= \frac{1}{7}-\frac{2}{7^2}+\dots+\frac{2n+1}{7^{2n + 1}}
\end {flalign}
$$

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

### **Tính biểu thức A**
- Duyệt $i$ từ $1$ đến $2n-1$, mỗi lần cộng vào đáp án $\frac{i}{i+5}$.
- **Độ phức tạp thời gian**: $O(n)$.

### **Tính biểu thức B**
- Duyệt $i$ từ $1$ đến $2n + 1$, mỗi lần cộng vào đáp nếu $i$ lẻ và trừ vào đáp án nếu $i$ chẵn một lượng là $\frac{i}{7^i}$
- Việc tính riêng tử và mẫu của $\frac{i}{7^i}$ là không khả thi do vấn đề về giới hạn lớn.
- Ta biến đổi $\frac{i}{7^i} = i \times \frac{1}{7^i}$. Gọi biến $p$ là giá trị $\frac{1}{7^i}$. Dễ dàng nhận thấy với mỗi lần chay ta chỉ cần gán lại giá trị cho $p = \frac p 7$ tương ứng với việc số mũ của $7$ tăng lên $1$ theo $i$.
- **Độ phức tạp thời gian**: $O(n)$.

>[!Note]
> Tuy $7^i$ là rất lớn, và lưu trữ bằng kiểu số thức sẽ dẫn đến ==sai số nghiêm trọng==, nhưng thực tế ta xét $\frac{1}{7^i}$, do đó sai số chỉ ở những ==hàng thập phân phía sau==. Vì vậy không ảnh hưởng đến kết quả.

:::danger
**Lưu ý**: Lưu đáp án bằng kiểu **số thực**.
:::

### **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 A = 0;
    for (int i = 1; i <= 2 * n - 1; i++) {
        A += (double)i/(i + 5);
    }

    double B = 0, p = 1;
    for (int i = 1; i <= 2 * n + 1; i++) {
        p = (double) p / 7;
        if (i % 2 == 1)
            B += ((double) i * p);
        else 
            B -= ((double) i * p);
    }
    
    cout << fixed << setprecision(5) << A << '\n' << B << '\n';

    return 0;
}

:::

## Bài 2:

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

Cho các số nguyên dương $a$, $b$, $c$, $k$, $x$, $y$.

**Yêu cầu**:
- Tính biểu thức $A = \frac{a \cdot b \cdot c}{k}$.
- Tính biểu thức $B = ((x + 1) \cdot (x + 2) \cdots (x + y)) ~mod~2020$.

**Dữ liệu đảm bảo:** $1 \le a, b, c, k \le 10^{18}$, $1 \le x \le 10^9$ và $1 \le y \le 10^6$.

### **Tính biểu thức A**

Nếu tính thông thường thì biểu thức $A$ sẽ tràn dữ liệu. Do đó cần xử lý số lớn để tính toán.

Ban đầu ta chuyển đổi giá trị $a$ thành một mảng số nguyên $A_i$ với $A_i$ là giá trị tại vị trí $i$ từ phải sang trái của số $a$.
> Ví dụ: $a = 123$ thì $A_1 = 3$.

Sau đó ta tính thông thường, nhân từng phân tử $A_i$ với $B$ từ $i = 1, 2, 3, \dots, n$ với $n$ là độ dài hiện tại của mảng $A_i$. Sau đó ta nhận lần lượt $A_i$ với $C$ tương tư như nhân với $B$.

Cuối cùng, dời $A_i$ lên $5$ vị trí, tức là $A_{i + 5} = A_i$, để khi chia ta lưu được $6$ số thập phân sau dấu phẩy trong $A_i$ với $i \in [0, 5]$.

>[!Tip] Nhận xét về độ dài số
>Độ dài tối đa của mảng $A$ bé hơn 100 vì độ dài giá trị của tích $10^{18} \times 10^{18} \times 10^{18}$ là $57$ sau đó ta thêm $5$ chữ số hàng thập phân thì tối đa độ dài đạt $62$.

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

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

Nếu chạy lần lượt $i$ từ $1$ đến $y$ để tính $(x + i)$ và nhân vào kết quả thì sẽ bị tràn dữ liệu.

Do đó, áp dụng tính chất chia lấy dư để xử lý tránh bị tràn số:
$$
(a \times b) \bmod c = [(a \bmod c ) \times (b \bmod c )] \bmod c
$$

**Độ phức tạp thời gian:** $O\left( y \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

Nguyễn Minh
#include <bits/stdc++.h>
using namespace std;

long long a, b, c, k, X, Y;
long long A[1000];
long long d[1000];

int main() {
    cin >> a >> b >> c >> k >> X >> Y;
    int B = 1;
    for (int i = 1; i <= Y; i++)
        B = B * ((X + i) % 2020) % 2020;

    int n = 0;
    while (a > 0)
    {
        int p = a % 10;
        a /= 10;
        n++;
        A[n] = p;
    }

    for (int i = 1; i <= 100; i++)
    {
        long long phu = A[i] * b + d[i]; // d[i] = tổng nhớ tại vị trí i.
        d[i] = 0;
        A[i] = phu % 10;
        phu /= 10;
        int j = i;
        while (phu > 0)
        {
            j++;
            int p = phu % 10;
            phu /= 10;
            d[j] += p;
        }
    }

    for (int i = 1; i <= 100; i++)
    {
        long long phu = A[i] * c + d[i];
        A[i] = phu % 10;
        phu /= 10;
        int j = i;
        while (phu > 0)
        {
            j++;
            int p = phu % 10;
            phu /= 10;
            d[j] += p;
        }
    }

    for (int i = 100; i >= 1; i--)
        if (A[i] != 0)
    {
        n = i; //Xác định độ dài hiện tại của mảng A[i]
        break;
    }

    for (int i = n + 5; i > 5; i--)
        {
            A[i] = A[i - 5]; // Dời giá trị lên 5 vị trí
            A[i - 5] = 0;
        }

    long long giatri = 0;
    for (int i = n + 5; i >= 0; i--)
    {
        giatri *= 10;
        giatri += A[i];
        A[i] = 0;
        if (giatri >= k)
        {
            A[i] = giatri / k;
            giatri = giatri % k;
        }
    }

    for (int i = n + 5; i >= 0; i--)
        if (A[i] != 0)
        {
            n = i; // xác định lại độ dài của mảng A[i]
            break;
        }

// Vì làm tròn đến số thập phân thứ 5 nên ta sẽ kiểm tra số thập phân thứ 6
    int q = 0;
    if (A[0] >= 5)
        q = 1;

    for (int i = 1; i <= n; i++)
        {
            A[i] += q;
            q = 0;
            if (A[i] == 10)
                {
                    A[i] = 0;
                    q = 1;
                }

            if (q == 0)
                break;
        }

    if (q == 1)
    {
        n++;
        A[n] = 1;
    }

    for (int i = n; i > 5; i--)
        cout << A[i];
    cout << ".";
    for (int i = 5; i >= 1; i--)
        cout << A[i];
    cout << "\n";

    cout << B;

    return 0;
}

:::

## Bài 3:

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

Cho dãy số nguyên gồm $n$ phần tử $a_1, a_2,\dots a_{n-1}, a_n$.

**Yêu cầu**:
- In ra các phần tử của dãy có dạng $7 \times k$ ($k$ là số nguyên).
- Nếu tồn tại hai số nguyên âm nằm kề nhau in ra chữ số $1$, ngược lại in ra chữ số $0$.
- Tìm độ dài lớn nhất của đoạn con liên tiếp có các phần tử là số nguyên tố (nếu không tồn tại dãy có ít nhất $2$ phần tử in ra $0$).
- Tìm giá trị tuyệt đối nhỏ nhất của tổng hai phần tử bất kỳ.

**Dữ liệu đảm bảo:** $n \le 10^5$ và $|a_i| \le 10^7$.

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

Một số nguyên dương $x$ có dạng $7k$ khi ==$x \bmod 7 = 0$==.

Do đó, ta duyệt qua mọi phần tử và in ra các phần tử 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**

Duyệt qua mọi cặp số kề nhau và kiểm tra xem hai số có thỏa mãn hay không.

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

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

Sử dụng thuật toán [**sàng nguyên tố**](https://wiki.vnoi.info/algo/algebra/prime_sieve.md) để đánh dấu những giá trị nào là số nguyên tố.

Áp dụng ==quy hoạch động== cơ bản:
- **Định nghĩa:** $dp_i$ là độ dài đoạn con liên tiếp có nhiều phần tử nhất kết thúc ở vị trí $i$.
- **Công thức:**
+ Nếu $a_i$ là số nguyên tố, $dp_i = dp_{i - 1} + 1$.
+ Ngược lại, $dp_i = 0$.
- **Kết quả:** $max(dp_i)$.

**Độ phức tạp thời gian:** $O( n \log \log n)$.
> Độ phức tạp của sàng nguyên tố.

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

>[!Tip] Nhận xét
> Ta cần tìm tổng hai số trong dãy có giá trị gần bằng $0$ nhất.

Sắp xếp lại mảng $a$ theo thứ tự không giảm, sau đó áp dụng thuật toán ==hai con trỏ==:
- Con trỏ $i$ bắt đầu từ $1$.
- Con trỏ $j$ bắt đầu từ $n$.
- Tổng đang xét là tổng của $a_i$ và $a_j$.

Nếu tăng $i$ lên thì giá trị của tổng sẽ tăng lên, ngược lại, nếu giảm $j$ xuống thì giá trị của tổng sẽ giảm xuống.

Chính vì tính chất đó, ta có thể di chuyển con trỏ tối ưu để tổng có thể gần bằng $0$ nhất và giá trị tuyệt đối của tổng là bé nhất.

**Độ 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;

int n;
long long a[1000005], dp[100005];
int vis[10000005];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
   
    for (int i = 1; i <= n; i++)
        if (a[i] % 7 == 0)
            cout << a[i] << " ";
    
    cout << "\n";

    bool kt = false;
    for (int i = 2; i <= n; i++)
        if (a[i] < 0 && a[i - 1] < 0)
        {
            kt = true;
            break;
        }
    
    if (kt == true) cout << 1;
    else cout << 0;
    cout << "\n";

    for (int i = 1; i <= n; i++)
        t[i] = 0;

    for (int i = 2; i * i <= 1e7; i++)
        if (vis[i] == 0)
            for (int j = i; j * i <= 1e7; j++)
                vis[j * i] = 1;
    vis[1] = 1;
    vis[0] = 1;

    long long ans = 0;
    for (int i = 1; i <= n; i++)
        if (vis[abs(a[i])] == 0 && a[i] > 0)
            {
                dp[i] = dp[i - 1] + 1;
                ans = max(ans, dp[i]);
            }
    if (ans <= 1)cout << 0;
    else cout << ans;
    cout << "\n";

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

    ans = 1e18;
    int j = n;
    for (int i = 1; i <= n; i++)
    {
        if (i > 1)
            ans = min(ans, abs(a[i] + a[i - 1]));
        if (j > 0)
            ans = min(ans, abs(a[i] + a[j]));
        while (abs(a[j]) > abs(a[i]) && j > i)
        {
            ans = min(ans, abs(a[i] + a[j]));
            j--;
        }
        if (j > 0)
            ans = min(ans, abs(a[i] + a[j]));
    }
    cout << ans;
    return 0;
}

:::

## Bài 4:

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

Cho một dãy $n$ số nguyên dương $a_i$ và một dãy $m$ số nguyên dương $b_i$.

**Yêu cầu**: Tìm số lượng phần tử trong mảng $b_i$ có giá trị bằng tổng của ít nhất $1$ dãy con trong mảng $a_i$.

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

### Lời giải

>[!Tip] Nhận xét
> Bài toán yêu cầu kiểm tra có thể tạo được tổng $b_i$ bằng một tập con của $a$ không.

Áp dụng thuật toán ==quy hoạch động cái túi==

- **Định nghĩa:** $dp_{i,j}$ đánh dấu tổng $j$ có thể tạo được với $i$ số đầu tiên không:
- $dp_{i,j} = 1$ nghĩa là tạo được tổng có giá trị bằng $j$.
- $dp_{i,j} = 0$ là không tạo được.
- **Khởi gián:** $dp_{0, 0} = 1$.
- **Công thức:** $dp_{i,j} = 1$ khi $dp_{i-1, j - a_i} = 1$ hoặc $dp_{i-1, j} = 1$.

Duyệt qua $b_i$, nếu $dp_{n,b_i} = 1$ nghĩa là giá trị $s_b$ thỏa yêu cầu đề bài, ta tăng đáp án.

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

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

:::success
:::spoiler Code

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

const int N = 100, M = 1e4;
int dp[N+1][M+1], n, a[N+1];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 10000; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= a[i] && dp[i - 1][j - a[i]] == 1) {
                dp[i][j] = 1;
            }
        }
    }

    long long ans = 0;
    for (int i = 1; i <= m; i++) {
        if (dp[n][b[i]] == 1) {
            ans++;
        }
    }
    
    cout << ans;
    return 0;
}

:::