# Đề TS10 - BRVT - 2018: 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 2018 - 2019.
>
>**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 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}{4}+\frac{2}{5}+\dots+\frac{2n-1}{2n+2}
\\
B &= (1 + \frac{1}{2}) \times ( 1 + \frac{1}{4}) \cdots (1 +\frac{1}{2^n})
\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+3}$.
- **Độ thức tạp**: $O(n)$

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

>[!Note]
> Tuy $2^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}{2^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ả.

### **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

:::

## Bài 2:

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

Cho ba số nguyên dương $n$, $a$ và $b$.

**Yêu cầu**:
- Tính biểu thức $A =\frac{n \times (n + 1) \times (n + 2) \times (2n - 1)}{6} \bmod 2018$.
- Tìm số nguyên tố **bé nhất** và số nguyên tố **lớn nhất** trong phạm vi từ $a$ đến $b$.

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

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

Ta không thể tính trực tiếp biểu thức $A$ rồi sau đó mới $\bmod$ vì sẽ tràn dữ liệu.

>[!Tip] Tính chất chia dư
> Ta thừa nhận tính chất sau đây với $p = b \times c$:
> $$
> \frac{a}{b}~ mod~c = \frac{a~mod~p}{b}
> $$

Thay vào biểu thức $A$ với $p = 2018 \times 6$ ta được
$$
A =\frac{(n~mod~p)~\times ~((n + 1)~mod~p)~mod~p~\times ((n + 2)~mod~p)~mod~p~ \times~((2n - 1)~mod~p)~mod~p}{6}
$$

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

### Tìm số nguyên tố bé nhất và lớn nhất trong phạm vi

Duyệt qua mọi giá trị trong phạm vi $a$ đến $b$ và kiểm tra xem có số nguyên tố nào không.
- Với số nguyên tố **bé nhất**, ta duyệt từ bé đến lớn và lấy số nguyên tố đầu tiên ta gặp.
- Với số nguyên tố **lớn nhất**, ta duyệt từ lớn về bé và lấy số nguyên tố đầu tiên ta gặp.

Ta kiểm tra số nguyên tố bằng cách duyệt tới căn bậc hai số đó [**như sau**](https://howkteam.vn/course/viet-ham-sap-xep-mang-theo-thu-tu-giam-dan/kiem-tra-n-co-phai-la-so-nguyen-to-hay-khong--1443)

>[!Caution] Vì sao thuật toán trên không chạy quá thời gian?
> Trong các số từ $1$ đến $10^9$, khoảng cách giữa hai số nguyên tố liên kề nhau không đáng kể, cụ thể là bé hơn $282$.

**Độ phức tạp thời gian:** không quá $O\left( 282 \times \sqrt {10^9} \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() {
    cin >> a >> b;
    
    for (int i = a; i <= b; i++) {
        bool check = true;
        if (i == 1) {
            check = false;
        }
        
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                check = false;
                break;
            }
        }
        
        if (check == true) {
            cout << i << " ";
            break;
        }
    }

    for (int i = b; i >= a; i--) {
        bool check = true;
        
        if (i == 1) {
            check = false;
        }
        
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                check = false;
                break;
            }
        }
        
        if (check == true) {
            cout << i;
            break;
        }
    }

    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**:
- Liệt kê tất cả giá trị của phần tử trong dãy có chữ số tận cùng là $6$ hoặc $8$.
- Tính trung bình cộng tất cả phần tử trong dãy có giá trị dương lẻ.
- Tìm độ dài lớn nhất của đoạn con có các phần tử liên tiếp bằng nhau.
- Tìm độ dài của dãy con tăng có nhiều phần tử nhất đều dương.

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

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

Duyệt qua từng giá trị trong dãy, lấy ==chữ số tận cùng== của giá trị bằng cách ==$\bmod 10$==. Nếu chữ số cuối cùng là $6$ hoặc $8$ thì in ra.

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

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

Duy trì một ==biến đếm== và một ==biến tổng==. Duyệt qua từng giá trị trong dãy, kiểm tra xem giá trị đó có ==vừa lẻ và dương== hay không? Nếu thỏa mãn, tăng biến đếm và biến tổng lên.

**Đáp án:** ==Tổng chia cho số lượng (biến đếm)==.

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

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

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

>[!Tip]
>Gọi $t_i$ là ==độ dài lớn nhất== của đoạn con liên tiếp kết thúc tại $i$.
>

Duyệt qua từng phần tử $a_i$ trong dãy:
- Nếu $a_i = a_{i - 1}$ thì $t_i = t_{i - 1} + 1$ (đoạn con kết thúc tại $i-1$ có thể mở rộng ra $i$).
- Nếu $a_i \not = a_{i - 1}$ thì $t_i = 1$ (đoạn con một phần tử).

**Đáp án:** $max(t_1, t_2,..t_n)$.

:::danger
**Lưu ý**: Nếu kết quả bằng $1$ ta in ra $0$ vì đoạn con phải có ít nhất $2$ phần tử.
:::

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

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

Áp dụng ==quy hoạch động cơ bản==.

- **Định nghĩa:** $dp_i$ là độ dài dãy con tăng dài nhất kết thúc tại $i$.
- **Khởi gán:** $dp_i = 1$ với $i$ từ $1$ đến $n$ (dãy con một phần tử cũng là dãy con tăng).
- **Công thức:** $dp_i = \max( dp_j + 1)$ với $j \lt i$ và $A_j \lt i$.

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

### **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>
#define ll long long
#define str string
#define ii pair <ll,ll>
#define fi first
#define se second

using namespace std;
const ll N = 1e6;

ll n , sum_q2 , cnt_q2 , cnt_q4 , ans_q4;
ll a[N+5] , f[N+5];
vector <ll> q1 , q4;

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

        if(a[i] > 0 && (a[i] % 10 == 6 || a[i] % 10 == 8)){
            q1.push_back(a[i]);
        }

        if(a[i] > 0 && a[i] % 2 == 1){
            sum_q2 += a[i];
            cnt_q2++;
        }

        if(a[i] % 2 == 0){
            q4.push_back(a[i]);
            cnt_q4++;
        }
    }

    /// Query 1
    for(ll i : q1){
        cout << i << " ";
    }
    cout << "\n";

    /// Query 2
    long double q2 = sum_q2*1.0 / cnt_q2*1.0;
    cout << fixed << setprecision(2) << q2 << "\n";

    /// Query 3
    bool check = 0;
    ll max_len = 1 , cur_len = 1;

    for(ll i = 2; i <= n; i++){
        if(a[i] == a[i-1]){
            cur_len++;
            check = 1;
        }
        else{
            max_len = max(max_len , cur_len);
            cur_len = 1;
        }
    }

    if(!check)  cout << "NO\n";
    else{
        cout << "YES " << max_len << "\n";
    }

    /// Query 4
    
    for(ll i = 0; i < cnt_q4; i++){
        f[i] = 1;
        for(ll j = 0; j < i; j++){
            if(q4[i] > q4[j]){
                f[i] = max(f[i] , f[j] + 1);
            }
        }
        ans_q4 = max(ans_q4 , f[i]);
    }

    cout << ans_q4;

    return 0;
}

:::

## Bài 4:

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

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

**Yêu cầu**: Tìm số lượng tổng khác nhau có thể tạo thành từ một tập con của dãy $a$.

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

### Lời giải

>[!Tip] Nhận xét
>Vì $n,a_i \le 10^2$, tổng tối đa của một tập con của $a$ là $n \times a_i = 10^4$.

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

- **Định nghĩa:** $dp_{i, j}$ là khả năng tạo ra tổng bằng $i$ từ $i$ phần tử đầu tiên:
- Nếu $dp_{i, j} = 1$, có thể tạo được tổng $i$ từ $i$ phần tử đầu tiên.
- Nếu $dp_{i, j} = 0$, không thể tạo được tổng $i$ từ $i$ phần tử đầu tiên.
- **Khởi gán:** $dp_{i,0} = 1$ với mọi $i$ (luôn có thể không chọn phần tử nào).
- **Công thức:**
- $dp_{i, j} = 1$ khi:
- $dp_{i-1, j} = 1$ (đã tạo được tổng $j$ từ trước).
- Hoặc $dp_{i-1, j - A_i} = 1$ (đã tạo được tổng $j - a_i$ từ trước, sau đó thêm phần tử $a_i$ để tạo được tổng $j$).
- $dp_{i, j} = 0$ nếu không thỏa bất kỳ điều kiện nào ở trên.

**Đáp án:** Các số $x$ thỏa $dp_{n, x} = 1$ là các tổng có thể tạo được.

**Độ phức tạp thời gian:** $O(n \times \sum_{i=1}^n {a_i} )$
>$\sum_{i=1}^n {A_i}$ là tổng $a_i$ với $i$ từ $1$ đến $n$.

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

:::success
:::spoiler Code

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

const int N = 100;
int n, A[N+1], sum, dp[N+1][N+1];

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

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

    cout << ans;

    return 0;
}

:::