# Đề THT B - BRVT - 2022: Editorial

>[!Note] Thông tin
>Sau đây là lời giải của Kỳ thi Tin học trẻ bảng B 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_thtb_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ích nguyên tố (40 điểm)

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

Cho số nguyên dương $n$.

**Yêu cầu:** Tìm hai số nguyên tố ==khác nhau== thỏa mãn tích của chúng là ==lớn nhất== và tích đó không được vượt quá $n$.

### Lời giải

>[!Tip]Tính chất 1
>Với mọi số nguyên dương $n$ luôn tồn tại hai số nguyên dương $a, b$ thỏa $n = a \times b$.
>
> Không mất tính tổng quát, giả sử ==$a \le b$==. Khi đó ta có:
> - $a \le \sqrt n$.
> - $b \ge \sqrt n$.

>[!Tip]Tính chất 2
> Xét trong khoảng $10^9$ trở lại, cứ không quá $200$ số nguyên liên tiếp, chắc chắn sẽ tồn tại một số nguyên tố.

Duyệt số nguyên tố $a$ từ $1$ đến $n$ và tìm số nguyên tố $b$ lớn nhất có thể thỏa mãn đề bài.

Ta biết: $a \times b \le n$, tức là $b \le \frac{n}{a}$. Như vậy, có thể duyệt $b$ giảm dần từ $\frac{n}{a}$ đến $\frac{n}{a} - 200$, nếu $b$ là số nguyên tố thì lấy kết quả và chuyển tới số $a$ tiếp theo.

**Độ phức tạp thời gian**: $O\left(\sqrt n \times 200 \times \sqrt n \right)$.
> Tuy nhiên, độ phức tạp thực tế thâp hơn nhiều, do các trường hợp ta tìm được $b$ sớm, và khi kiểm tra tính nguyên tố ta cũng có không cần duyệt hết căn của số đó.

:::success
:::spoiler Code

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

int n;
bool isPrime[32000];

bool Prime(int x) {
    for (int i = 2; i*i <= x; i++)
        if (x % i == 0) return false;
    return true;
}

int main(){
    cin >> n;

    for (int i = 2; i*i <= n; i++) {
        isPrime[i] = true;
    }

    for (int i = 2; i*i*i*i <= n; i++) {
        if (isPrime[i] == true) {
            for (int j = i*i; j*j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    int MaxVal = 0, a, b;
    for (int i = 2; i*i <= n; i++) {
        if (isPrime[i] == true) {
            int lim = n / i;
            for (int j = lim; j >= 1; j--) {
                if (Prime(j)) {
                    if (i * j < MaxVal || i == j) break;
                    MaxVal = i * j;
                    a = i;
                    b = j;
                }
            }
        }
    }

    cout << a << ' ' << b;

    return 0;
}

:::

## Bài 2: Giao lưu (30 điểm)

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

Tại mỗi thời điểm, dữ liệu cho số $0$ tương ứng với có $1$ học sinh đi ra khỏi trường, và số $1$ nếu có $1$ học sinh đi vào trường.

**Yêu cầu:** Tính số học sinh ở trong trường nhiều nhất tại $1$ thời điểm.

### Lời giải

Gọi $cur$ là số học sinh đang có trong trường.

Ta duyệt qua từng thời điểm:
- Nếu có học sinh ra khỏi trường (số $0$) $\rightarrow$ $cur = cur - 1$.
- Nếu có học sinh đi vào trường (số $1$) $\rightarrow$ $cur = cur + 1$.

**Đáp án:** Giá trị lớn nhất của $cur$ tại mọi thời điểm.

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

:::success
:::spoiler Code

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

int main(){
    int n; 
    cin >> n;
    
    int cur = 0, res = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        
        if (x == 0) cur--;
        else cur++;
        
        res = max(res, cur);
    }
    
    cout << res;

    return 0;
}

:::

## Bài 3: Đội tuyển Tin học (30 điểm)

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

Có $n$ học sinh, cho biết thời gian luyện tập của học sinh thứ $i$ là từ $l_i$ đến $r_i$.

Thời gian luyện tập hiệu quả là thời gian mà chỉ có duy nhất một học sinh đang luyện tập.

**Yêu cầu:** Hãy chọn ra 1 số học sinh từ $n$ học sinh trên sao cho tổng thời gian luyện tập hiệu quả là lớn nhất.

### Lời giải:

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

>[!Important] Thứ tự quy hoạch động
>Để có thứ tự quy hoạch động, ta cần sắp xếp các học sinh lại theo thứ tự tăng dần của thời gian kết thúc giờ luyện tập ($r_i$ tăng dần).

- **Định nghĩa:** ==$f_i$== là thời gian luyện tập hiệu quả nhiều nhất nếu chọn một số học sinh trong $i-1$ học sinh trước đó và chắc chắn chọn học sinh $i$.
- **Khởi gán:** ==$f_i = r_i - l_i$== (trường hợp chỉ lấy học sinh $i$).
- **Công thức:** (nếu lấy học sinh thứ $i$ xếp vào ngay sau học sinh $j$)
$$
f_i = \max \left(f_i, f_j - \max(0, r_j - l_i) + r_i - \max(r_j, l_i) \right)
$$
> **Trong đó**:
> - $r_j - l_i$ là khoảng thời gian học không hiệu quả.
> - $r_i - \max(r_j, l_i)$ là khoảng thời gian học tập hiệu quả của học sinh $i$.

**Đáp án:** $\max(f_i) \; \forall \; i$.

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

:::success
:::spoiler Code

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

const int N = 1e4 + 5;
int n, f[N];

struct students {
    int L, R;
} a[N];

bool cmp(const students &a, const students &b) {
    return a.R < b.R;
}

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

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

    int res = 0;
    for (int i = 1; i <= n; i++) {
        f[i] = a[i].R - a[i].L;
        for (int j = 1; j < i; j++) {
            f[i] = max(f[i], f[j] - max(0, a[j].R - a[i].L) + a[i].R - max(a[j].R, a[i].L));
        }
        
        res = max(res, f[i]);
    }

    cout << res;

    return 0;
}

:::