# Đề THT B - BRVT - 2024: 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 2023 - 2024.
>
>**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: Hình chữ nhật (40 điểm)

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

Trong mặt phẳng tọa độ $Oxy$, cho $n$ hình chữ nhật có các cạnh song song với trục tọa độ. Hình chữ nhật thứ $i$ được xác định bởi $4$ giá trị nguyên $a_i, b_i, c_i, d_i$ với $i = 1, 2, \dots , n$.

Trong đó $(a_i, b_i)$ là tọa độ đỉnh bên trái dưới cùng, còn $(c_i, d_i)$ là tọa độ đỉnh bên phải trên cùng của hình chữ nhật.

**Yêu cầu:** Hãy cho biết diện tích của hình chữ nhật lớn nhất mà phần diện tích đó thuộc tất cả $n$ hình chữ nhật đã cho.

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

### Lời giải

Gọi ==$(lx, ly)$== và ==$(rx, ry)$== lần lượt là tọa độ điểm ==trái dưới== và ==phải trên== của hình chữ nhật lớn nhất mà phần diện tích đó thuộc tất cả $n$ hình chữ nhật đã cho.

Dễ thấy:
- $lx = \max(a_1, a_2, \dots, a_n)$
- $ly = \max(b_1, b_2, \dots, b_n)$
- $rx = \max(c_1, c_2, \dots, c_n)$
- $ry = \max(d_1, d_2, \dots, d_n)$

Như vậy, ta duyệt qua $n$ hình chữ nhật đã cho để tính được tọa độ $(lx, ly)$ và $(rx, ry)$.

Khi đó, đáp án (tức là diện tích) là $(rx - lx) \times (ry - ly)$.

:::danger
**Lưu ý:** Trong trường hợp không tìm được hình chữ nhật nào thỏa, tức là $rx \lt lx$ hoặc $ry \lt ly$, thì cần in ra $0$.
:::

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

:::success
:::spoiler Code

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

const int N = 1e4;
long long n, lx = -1e9, ly = -1e9, rx = 1e9, ry = 1e9;

int main() {
    cin >> n;
    while (n--) {
        long long a, b, c, d;
        cin >> a >> b >> c >> d;

        lx = max(lx, a);
        ly = max(ly, b);
        rx = min(rx, c);
        ry = min(ry, d);
    }

    cout << max(0LL, rx - lx) * max(0LL, ry - ly);

    return 0;
}

:::

## Bài 2: Số chính phương (30 điểm)

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

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

**Yêu cầu:** Tìm số chính phương nhỏ nhất chia hết cho $a$ và $b$.

**Dữ liệu đảm bảo:** $a, b \le 10^4$.

**Subtasks:**
- $60\%$ số điểm ứng với $a, b \le 10^2$.
- $40\%$ số điểm không có ràng buộc gì thêm.

### Subtask 1

Ta biết một số ==chắc chắn thỏa mãn yêu cầu bài toán== là:
$$
\operatorname{BCNN}(a, b) ^ 2
$$

Trong trường hợp $a, b \le 10^2$ thì ==$\operatorname{BCNN}(a, b) ^ 2 \le (ab)^2 = 10^8$==.

Chính vì vậy, ta có thể duyệt qua mọi số để tìm đáp án.

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

:::success
:::spoiler Code

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

int a, b;

int main() {
    cin >> a >> b;
    long long lim = 1LL*a*b*a*b;
    for (long long i = 1; i <= lim; i++) {
        long long t = (long long)sqrtl(i);
        if (t*t != i) continue;
        if (i % a == 0 && i % b == 0) {
            cout << i;
            break;
        }
    }

    return 0;
}

:::

### Subtask 2

Kế thừa tư tưởng từ subtask trước, nhưng thay vì duyệt qua mọi số rồi lại phải kiểm tra số đó có phải số chính phương hay không, ta ==chỉ duyệt qua các số chính phương== mà thôi.

Ở đây nếu duyệt $i$ đến $ab$, ta sẽ thu được số chính phương tới $(ab)^2$.

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

:::success
:::spoiler Code

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

int a, b;

int main() {
    cin >> a >> b;
    long long lim = 1LL*a*b*a*b;
    for (int i = 1; 1LL*i*i <= lim; i++) {
        long long t = 1LL*i*i;
        if (t % a == 0 && t % b == 0) {
            cout << t;
            break;
        }
    }

    return 0;
}

:::

## Bài 3: Phần thưởng (30 điểm)

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

Có $m$ phần quà cần chia cho $n$ học sinh theo quy tắc: Em đứng trước sẽ được nhận số gói quà không ít hơn số gói quà của em đứng ở phía sau nhận (có thể có em không nhận phần quà nào).

Gọi $t_1, t_2, \dots, t_n$ lần lượt là tổng số gói quà em thứ $1, 2, \dots, n$ nhận được (tương ứng với thứ hạng từ cao xuống thấp) thì $t_1 \ge t_2 \ge \dots \ge t_n \ge 0$ và $t_1 + t_2 + \dots + t_n = m$.

**Yêu cầu:** Hãy cho biết có bao nhiêu cách phát quà khác nhau.

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

### Lời giải

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

- **Định nghĩa:** ==$dp_{i, j, k}$== là số cách phát hết $j$ gói quà cho $i$ học sinh đầu tiên và học sinh thứ $i$ nhận $k$ gói quà.
- **Khởi gán:** ==$dp_{1, j, j} = 1$==, có duy nhất một cách phát hết $j$ gói quà cho một học sinh là cho học sinh đó nhận hết.
- **Công thức:** ==$dp_{i, j, k} = dp_{i-1, j-k, k} + dp_{i-1, j-k, k+1} + \dots + dp_{i-1, j-k, j-k}$==, thực hiện phát $k$ gói quà cho bạn thứ $i$ và tổng gói quà đã chia là $j$:
- ==$dp_{i-1, j-k, k}$==: số cách phát $j-k$ gói quà cho $i-1$ bạn, bạn $i-1$ được $k$ gói.
- ==$dp_{i-1, j-k, k+1}$==: số cách phát $j-k$ gói quà cho $i-1$ bạn, bạn $i-1$ được $k+1$ gói.
- ...
- **Đáp án:** ==$dp_{n, m, 0} + dp_{n, m, 1} + \dots + dp_{n, m, m}$==.

>[!Caution] Vấn đề
> Thuật toán trên đang quá giới hạn về cả ==thời gian== và ==bộ nhớ==.

Vì nhận thấy các trạng thái ở $dp_i$ chỉ phụ thuộc vào $dp_{i-1}$, ta không cần phải lưu toàn bộ mảng quy hoạch động.

Đồng thời, ta có thể tính trước các trạng thái tác động đến $dp_i$ bằng mảng cộng dồn hậu tố (suffix sum).

Từ đó, ta chỉ cần lưu một mảng $dp$ và một mảng $suff$, mỗi mảng có $m^2$ phần tử.

>[!Tip] Về độ phức tạp thời gian
> Về lý thuyết, độ phức tạp thời gian là $nm^2$.
>
> Tuy nhiên, ta có thể cắt giảm số thao tác (nhất là ở vòng lặp) bằng cách chỉ duyệt $k$ đến $\frac j i$. Nếu chạy thử để đếm số thao tác lặp, có thể thấy chương trình vẫn chạy trong thời gian giới hạn dù với bộ dữ liệu tối đa.

:::success
:::spoiler Code

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

const int N = 1e3;
const long long M = 123456789;
long long m, n, dp[N+1][N+1], suff[N+1][N+1];

int main() {
    cin >> m >> n;

    for (int j = 0; j <= m; j++) {
        for (int k = j; k >= 0; k--) {
            suff[j][k] = 1;
        }
    }

    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= m && k*i <= j; k++) {
                dp[j][k] = suff[j-k][k];
            }
        }

        for (int j = 0; j <= m; j++) {
            suff[j][j/i+1] = 0;
            for (int k = j/i; k >= 0; k--) {
                suff[j][k] = (suff[j][k+1] + dp[j][k]) % M;
            }
        }
    }

    cout << suff[m][0];

    return 0;
}

:::