# Đề TS10 - BRVT - 2016: 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 2016 - 2017.
>
>**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:**
- Cho biết $n$ có phải số chẵn không
- Tính các biểu thức sau:
\begin{align}
&A = \prod_{i=3}^{n} \frac{1}{i \cdot(i-1)} \\
&B = \sum_{i=1}^{n} \frac{2 \cdot i-1}{2 \cdot i+1}
\end{align}

### Kiểm tra tính chẵn lẻ
Nếu $n$ chia hết cho $2$ thì $n$ chẵn, ngược lại $n$ lẻ. Sử dụng ==phép toán $\bmod$== để kiểm tra.

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

### Tính biểu thức A
Khởi gán $A = 0$. Duyệt qua mọi $i \in [3,n]$ và cộng ==$\frac{1}{i \cdot (i-1)}$== vào $A$.

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

### Tính biểu thức B
Khởi gán $B = 0$. Duyệt qua mọi $i \in [1,n]$ và cộng ==$\frac{2 \cdot i-1}{2 \cdot i+1}$== vào $B$.

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

:::danger
Lưu ý: Vì bài toán liên quan đến số thực. Vậy nên cần sử dụng kiểu dữ liệu double hoặc long double để đảm bảo độ chính xác.
:::

:::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;
double A, B;

int main() {
    cin >> n;
    for (int i = 3; i <= n; i++) {
        A += (double)1/((i-1)*i);
    }
    for (int i = 1; i <= n; i++) {
        B += (double)(2*i-1)/(2*i+1);
    }
    cout << (n & 1 ? "NO" : "YES") << '\n' << fixed << setprecision(2) << A << '\n' << B;
    return 0;
}

:::

## Bài 2

### Tóm tắt đề bài
Cho $2$ số nguyên dương $a$ và $b$.

**Yêu cầu:**
- Tối giản phân số $\frac{a}{b}$.
- Đếm số lượng số chia hết cho $3$ trong đoạn $[a,b]$.

### Tối giản phân số
Để tối giản $\frac{a}{b}$, ta chia $a$ và $b$ cho $\operatorname{UCLN}(a,b)$.

:::info
C++ cung cấp sẵn hàm `gcd()` để tìm UCLN của hai số.
:::

**Độ phức tạp thời gian:** $O \left( \log \min(a, b) \right)$
> Độ phức tạp của hàm `gcd()` trong C++ STL.

### Đếm số lượng số chia hết cho 3 trong đoạn

>[!Tip]
> Số lượng số ==chia hết cho $x$== từ $1$ đến $n$ là: ==$\lfloor \frac{n}{x} \rfloor$==

Gọi $f(x)$ là số lượng số chia hết cho $3$ trong đoạn $[1,x]$. Khi này, $f(x) = \lfloor \frac{x}{3} \rfloor$.

**Đáp án:** %f(b) - f(a-1)$.

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

:::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 a, b;
    cin >> a >> b;  
    
    int gcd = __gcd(a,b);
    cout << a / gcd << '/' << b / gcd << '\n' << b / 3 - (a - 1) / 3;
    
    return 0;
}

:::

## Bài 3:

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

Cho dãy số nguyên dương gồm $n$ phần tử $a_1, a_2, \dots, a_n$.
- Liệt kê các phần tử có ==dạng $3k+2$==.
- Tìm số có ==giá trị lớn nhất== của dãy.
- Tìm số có ==giá trị nhỏ nhất== của dãy.

### Liệt kê các phần tử có dạng $3k+2$

Một số nguyên dương $x$ có dạng $3k+2$ khi $x \equiv 2 \pmod{3}$ hay $x - 2 \equiv 0 \pmod{3}$.
> Nghĩa là ==$x \bmod 3 = 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)$

### Tìm số có giá trị lớn nhất của dãy.

Gọi $f_{max}$ là giá trị lớn nhất của dãy.
- Khởi gán ==$f_{max} = -\infty$==.
- Duyệt qua mọi $i \in [1,n]$, ==nếu $f_{max} \lt a_i$ thì gán $f_{max} = a_i$==.

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

### Tìm số có giá trị nhỏ nhất của dãy.

Gọi $f_{min}$ là giá trị lớn nhất của dãy.
- Khởi gán ==$f_{min} = \infty$==.
- Duyệt qua mọi $i \in [1,n]$, ==nếu $f_{min} \gt a_i$ thì gán $f_{min} = a_i$==.

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

:::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;
    vector<int> a(n);
    for (auto& x : a) {
        cin >> x;
    }

    for (auto& x : a) {
        if ((x - 2) % 3 == 0) {
            cout << x << ' ';
        }
    }

    cout << '\n' << *max_element(a.begin(),a.end()) << '\n' << *min_element(a.begin(),a.end());
    
    return 0;
}

:::

## Bài 4

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

Cho dãy nguyên dương gồm $n$ phần tử $a_1, a_2, \dots, a_n$.

Gọi $S_1$ là tổng các đồ vật từ $1$ đến $k$ và $S_2$ là tổng các đồ vật từ $k+1$ đến $n$ $(1 \le k \lt n)$.

**Yêu cầu:** Tìm cách chia sao cho ==$S_1 \cdot S_2$ lớn nhất==.

### Lời giải

Áp dụng ==prefix sum (mảng cộng dồn) cơ bản==.

Gọi $f_i = \sum_{j=1}^{i} a_j$ (tổng $i$ số đầu tiên của mảng).

Khi này, ta có:
- Tổng của các phần tử trong ==đoạn $[1,k]$== là ==$S_1 = f_k$==.
- Tổng các phần tử trong ==đoạn $[k+1,n]$== là ==$S_2 = f_n - f_{k}$==.

Duyệt qua mọi $i \in [1,n)$ và tìm vị trí $i$ để $f_i \cdot (f_n - f_i)$ lớn nhất.

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

:::success
:::spoiler Code

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

int main() {
    int n;
    cin >> n;
    vector<long long> f(n+5,0);
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        f[i] = f[i-1] + a;
    }
    
    long long ans = 0;
    array<int,2> f;
    
    for (int i = 1; i < n; i++) {
        long long v = f[i] * (f[n] - f[i]);
        if (ans < v) {
            ans = v;
            f = {f[i], f[n] - f[i]};
        }
    }
    
    cout << f[0] << ' ' << f[1];
    
    return 0;
}

:::