# Đề THT B - BRVT - 2020: 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 2019 - 2020.
>
>**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: Tam giác vuông (40 điểm)

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

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

**Yêu cầu:** Đếm số lượng bộ ba số nguyên dương $a \le b \le c$ thỏa mãn ==$a + b + c = p$== và là ==độ dài ba cạnh của một tam giác vuông==.

**Dữ liệu đảm bảo:** $p \le 10^6$.

### Lời giải

Các bộ $(a, b, c)$ thỏa mãn bài toán là các ==bộ ba Pytago== thỏa $a + b + c = p$.

Theo [**công thức Euclid**](https://www.wikiwand.com/vi/articles/B%E1%BB%99_ba_s%E1%BB%91_Pythagoras), ta có khái niệm ==bộ ba Pytago **nguyên tố**== là bộ $(a, b, c)$ trong đó:
- $a = m^2 - n^2$
- $b = 2mn$
- $c = m^2 + n^2$
> $m, n$ là các số nguyên tố cùng nhau, nghĩa là $\operatorname{UCLN}(m, n) = 1$, và đúng một trong chúng là số chẵn.

Từ một ==bộ ba Pytago **nguyên tố**==, ta có thể tạo ra một ==bộ ba Pytago== bằng cách nhân một số nguyên dương $k$ vào cả $a, b, c$. Tức là $(ka, kb, kc)$.

Như vậy, ta có thể duyệt qua $m$ và $n$ để thử mọi bộ ba Pytago nguyên tố, sau đó lại kiểm tra xem có một bộ ba Pytago nào có thể được tạo ra thỏa mãn $ka + kb + kc = p$ không.

>[!Important] Cách duyệt tối ưu
> Ta duyệt qua mọi $n$ từ $1$ đến $p$, sau đó ta duyệt $m$ từ $n+1$ (vì $m \gt n$) và dừng vòng lặp khi $m^2 + n^2 \gt p$ hoặc $2mn \gt p$.
>
> Vì hai số $m, n$ phải khác tính chẵn lẻ, trong vòng lặp ta luôn cộng $m$ lên $2$.

**Độ phức tạp thời gian:** $O \left( p \sqrt p \right)$.
> Thực tế, độ phức tạp nhỏ hơn nhiều, nhưng khó tính được chính xác.

:::success
:::spoiler Code

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

long long p, res;

int main() {
    cin >> p;

    for (long long n = 1; n <= p; n++)
        for (long long m = n+1; m*m + n*n <= p && 2*m*n <= p; m += 2) {
            if (__gcd(m, n) > 1) continue;

            long long a = m*m - n*n;
            long long b = 2*m*n;
            long long c = m*m + n*n;

            if (a + b + c > p) break;

            if (p % (a + b + c) == 0) res++;
        }

    cout << res;

    return 0;
}

:::

## Bài 2: Sân bay (30 điểm)

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

Có $n$ người, người thứ $i$ ở sân bay trong khoảng thời gian từ $l_i$ đến $r_i$.

**Yêu cầu:** Tìm số người lớn nhất trong sân bay ở cùng một thời điểm.

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

### Lời giải

Gọi $f_i$ là số người trong sân bay tại thời điểm $i$.

Như vậy, nếu người thứ $i$ ở sân bay từ $l_i$ đến $r_i$, ta tăng giá trị của $f_{l_i}, f_{{l_i}+1}, \dots, f_{r_i}$ lên $1$.

>[!Tip] Tối ưu
> Tăng giá trị của $f_{l_i}, f_{{l_i}+1}, \cdots, f_{r_i}$ nhanh bằng [**mảng hiệu**](https://wiki.vnoi.info/algo/data-structures/prefix-sum-and-difference-array.md).

:::danger
Dễ nhận thấy không thể lưu trữ mảng với $10^9$ phần tử.

Nhưng số lượng giá trị $l_i, r_i$ khác nhau chỉ đạt tối đa $2n$. Do đó ta dùng kĩ thuật [**nén số**](https://viblo.asia/p/roi-rac-hoa-nen-so-38X4E9QA4N2).
:::

**Đáp án**: $\max (f_1, f_2, \cdots, f_{10^9})$

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

:::success
:::spoiler Code

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

const int N = 1e4 + 5;
int n, f[2*N], l[N], r[N];
vector <int> vt;

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        vt.push_back(l[i]);
        vt.push_back(r[i]);
    }
    
    ///Nén số
    sort(vt.begin(), vt.end());
    vt.erase(unique(vt.begin(), vt.end()), vt.end());
    for (int i = 1; i <= n; i++){
        l[i] = lower_bound(vt.begin(), vt.end(), l[i]) - vt.begin() + 1;
        r[i] = lower_bound(vt.begin(), vt.end(), r[i]) - vt.begin() + 1;
    }
    
    ///Mảng hiệu
    for (int i = 1; i <= n; i++){
        f[l[i]]++;
        f[r[i] + 1]--;
    }

    int res = 0;
    for (int i = 1; i <= 2*n; i++){
        f[i] = f[i-1] + f[i];
        res = max(res, f[i]);
    }

    cout << res;

    return 0;
}

:::

## Bài 3: Alibaba mua hàng (30 điểm)

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

- Cho $n$ loại tiền có mệnh giá là $a_i$ khác nhau.
- Cho $m$ món hàng với giá tiền của món đồ thứ $i$ là $b_i$
- Một món hàng có thể được mua nếu có thể dùng các đồng tiền trong $n$ loại tiền để tạo ra giá trị ==đúng bằng $b_i$== (mỗi đồng tiền chỉ sử dụng một lần với một món hàng).

**Yêu cầu:** in ra số lượng món hàng có thể mua được.

**Dữ liệu đảm bảo:**
- $n \le 100$;
- $m \le 10000$;
- $a_i \le 100$;
- $b_i \le 10000$.

### Lời giải

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

- **Định nghĩa:** ==$f_{i, j}$== là khả năng tạo ra giá trị $j$ nếu chỉ xét $i$ đồng tiền đầu tiên.
- ==$f_{i, j} = 1$==: Có thể tạo ra giá trị $j$ với $i$ đồng tiền đầu tiên.
- ==$f_{i, j} = 0$==: Không thể tạo ra giá trị $j$ với $i$ đồng tiền đầu tiên.
- **Khởi gán:** ==$f_{0, 0} = 1$== (có thể tạo được giá trị $0$ bằng cách không lấy đồng nào).
- **Công thức:** ==$f_{i, j} = \max (f_{i-1, j}, f_{i-1, j - A_i})$==.
- $f_{i-1, j} = 1$: Không cần đồng xu thứ $i$ đã có thể tạo được tổng $j$.
- $f_{i-1, j - A_i} = 1$: Đã tạo được tổng $j - A_i$ mà không cần dùng đồng xu thứ $i$, do đó nếu dùng thêm đồng xu thứ $i$ ta được tổng $j$.

**Đáp án:** Món hàng thứ i có thể mua được nếu ==$f_{n, b_i} = 1$==.

:::success
:::spoiler Code

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

const int N = 105, M = 1e4 + 5;
int n, f[N][M], m, a[N], b[M];

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

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

    int res = 0;
    for (int i = 1; i <= m; i++) {
        if (f[n][b[i]] == 1) {
            res++;
        }
    }

    cout << res;

    return 0;
}

:::