# THI THỬ MÔN CHUYÊN - 2025 - SỞ GD-ĐT

>[!Note] Thông tin
>Sau đây là lời giải của Kỳ thi thử môn chuyên TS10 vào trường THPT chuyên Lê Quý Đôn tỉnh Bà Rịa - Vũng Tàu.
>
>**Thời gian:** Ngày 28/04/2025
>
>**Bạn đọc có thể nộp và chấm bài** [TẠI ĐÂY](https://chuyentinbrvt.online/contest/algi_mockhsg9lan2_2025)
>
>:::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: Số chính phương (5 điểm)

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

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

**Yêu cầu:** Tìm số chính phương $x$ sao cho |$n - x$| nhỏ nhất, trong trường hợp có $2$ số chính phương cùng thỏa mãn điều kiện thì cho biết ==số chính phương có giá trị nhỏ nhất==.

**Dữ liệu đảm bảo:** $1 \le n \le 10^9$.

**Subtasks:**
- $60\%$ số điểm tương ứng với $1 \le n \le 10^6$.
- $40\%$ số điểm không có ràng buộc gì thêm.

### Subtask 1

Duyệt số $i$ tăng dần từ $1$, kiểm tra số $i$ có phải là số chính phương hay không và lấy đáp án.

**Lưu ý:** Ta chỉ duyệt đến ==số chính phương đầu tiên lớn hơn $n$==, các số sau đó không có ý nghĩa.

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

### Subtask 2

>[!Tip]
> Số $x$ là số chính phương khi và chỉ khi $x = k^2$ với $k \in N$.

Dễ thấy, đáp án của bài toán chỉ có thể là một trong hai số sau đây:
- Số chính phương $l$ ==lớn nhất bé hơn hoặc bằng $n$==.
- Số chính phương $r$ ==nhỏ nhất lớn hơn hoặc bằng $n$==.

Ta có: $l \le n$ với $k \in N$. Do đó $\sqrt l \le \sqrt n$, mà $\sqrt l \in N$ (vì $l$ là số chính phương) nên:
$$
\begin{flalign}
\sqrt l = \left \lfloor \sqrt n \right \rfloor\\
\Rightarrow l = \left \lfloor \sqrt n \right \rfloor ^ 2
\end{flalign}
$$

Tương tự, ta có:
$$
r = \left \lceil \sqrt n \right \rceil ^ 2
$$

**Đáp án:**
- $l$, nếu $n - l \le r - n$.
- $r$, nếu $n - l \gt r - n$.

**Độ phức tạp thời gian:** $O \left( \log n \right)$.
> Độ phức tạp trên là độ phức tạp của lệnh `sqrt()` của C++.

:::success
:::spoiler Code

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

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

    int l = (int)sqrt(n);
    int r = l + 1;

    if (n - l*l <= r*r - n) cout << l*l;
    else cout << r*r;

    return 0;
}

:::

## Bài 2: Số may mắn (5 điểm)

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

Một số nguyên dương được gọi là ==số may mắn== nếu tổng các chữ số chia hết cho $9$.
>Ví dụ: $9, 18$ và $2007$ là các ==số may mắn==.

**Yêu cầu:** Cho số nguyên dương $n$, tính tổng tất cả các ==số may mắn== từ $1$ đến $n$.

**Dữ liệu đảm bảo:** $1 \le n \le 10^9$.

**Subtasks:**
- $50\%$ tests tương ứng $n \le 10^6$.
- $50\%$ tests tương ứng $10^6 < n \le 10^9$.

### Lời giải:

### Subtask 1

Duyệt qua mọi số từ $1$ đến $n$, tính tổng các chữ số và kiểm tra có chia hết cho $9$ không, nếu có thì cộng thêm vào kết quả.

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

### Subtask 2

>[!Tip] Nhận xét
> Các số có tổng chữ số chia hết cho 9 cũng chia hết cho 9.
>
> Không mất tính tổng quát, giả sử số $n$ có dạng $\overline{abcd}$ và $(a + b + c + d) \bmod 9 = 0$.
> Ta có:
> $$
> \begin{flalign}
> n &= 1000a + 100b + 10c + d \\
> &= 999a + a + 99b + b + 9c + c + d \\
> &= (999a + 99b + 9c) + (a + b + c + d)
> \end{flalign}
> $$
> Dễ thấy, $(999a + 99b + 9c) \bmod 9 = 0$, mà $(a + b + c + d) \bmod 9 = 0$ (đề cho). Như vậy, $n$ chia hết cho $9$.

Bài toán trở thành ==tính tổng các số chia hết cho 9 từ $1$ đến $n$==.

Có thể thấy, các số chia hết cho $9$ từ $1$ đến $n$ có dạng:
$$
9, 9 \times 2, 9 \times 3, \dots, 9 \times (k-1), 9 \times k \; (9 \times k \le n)
$$

Ta có: $k = \left \lfloor \frac n 9 \right \rfloor$. Như vậy, đáp án của bài là:
$$
\begin{flalign}
9 + 9 \times 2 + 9 \times 3 + \dots + 9 \times (k-1) + 9 \times k \\
= 9 \times (1 + 2 + 3 + \dots + k) \\
= 9 \times \frac{k \times (k+1)}2
\end{flalign}
$$
> Hoặc áp dụng [công thức tính tổng cấp số cộng](https://vietjack.com/tai-lieu-mon-toan/cac-cong-thuc-ve-cap-so-cong-ctqt11.jsp) nếu bạn nhớ.

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

:::success
:::spoiler Code

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

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

    n /= 9;
    cout << 9*n*(n+1)/2;
    
    return 0;
}

:::

## Bài 3: Đếm cặp chỉ số (5 điểm)

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

Cho dãy gồm $n$ số nguyên dương $a_1, a_2, \dots, a_n$.

**Yêu cầu:** Hỏi có tất cả bao nhiêu **cặp chỉ số** ($i, j$) khác nhau thỏa mãn tất cả các điều kiện dưới đây:
- $1 \le i \le j \le n$.
- $a_i + a_j$ là một số lẻ chia hết cho $3$.

**Dữ liệu đảm bảo:**
- $1 \le n \le 10^6$.
- $1 \le a_i \le 10^9$.

**Subtasks:**
- $50\%$ số điểm tương ứng với $1 \le n \le 10^4$.
- $50\%$ số điểm không có ràng buộc gì thêm.

### Subtask 1

Duyệt hai vòng lặp để ==xét mọi cặp chỉ số== và đếm số cặp thỏa mãn bài toán.

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

### Subtask 2

Xét trường hợp ta cố định $A_i$, khi đó cần đếm số lượng $j$ thỏa:
- $j \le i$.
- $(A_j + A_i) \bmod 3 = 0$, hay $A_j \bmod 3 + A_i \bmod 3 = 0$.
- $A_j + A_i$ lẻ, hay ==đúng một trong hai== số là lẻ.

Điều này có thể thực hiện bằng cách sử dụng mảng đếm như sau:
- Lưu $\text{even}_i$ là ==số lượng số lẻ chia cho $3$ dư $i$== $(0 \le i \lt 3)$.
- Lưu $\text{odd}_i$ là ==số lượng số chẵn chia cho $3$ dư $i$== $(0 \le i \lt 3)$.

Như vậy, ta duyệt qua mảng $A$ và thực hiện:
- Nếu $A_i$ lẻ, có thể ghép với các số $A_j$ chẵn mà $A_j \bmod 3 + A_i \bmod 3 = 0$.
- Nếu $A_i$ chẵn, có thể ghép với các số $A_j$ lẻ mà $A_j \bmod 3 + A_i \bmod 3 = 0$.

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

:::success
:::spoiler Code

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

const int N = 1e6;
int n, res, odd[3], even[3];

int main() {
    cin >> n;
    while (n--) {
        int x;
        cin >> x;

        if (x & 1) {
            res += even[(3 - x % 3) % 3];
            odd[x % 3]++;
        } else {
            res += odd[(3 - x % 3) % 3];
            even[x % 3]++;
        }
    }

    cout << res;

    return 0;
}

:::

## Bài 4: Chọn số (5 điểm)

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

Cho bảng số nguyên có $2$ hàng và $n$ cột. Ô giao hàng $i$ và cột $j$ gọi là ô $(i, j)$ chứa số nguyên $a_{i,j}$ và **bộ quy tắc** chọn các số trên bảng như sau:
- Mỗi cột bắt buộc chọn đúng **một số duy nhất**.
- Trên cùng một hàng chọn không quá $2$ số liên tiếp nhau.

**Yêu cầu:** Cho biết **tổng giá trị lớn nhất của tất cả các số được chọn** có trong bảng thỏa mãn **bộ quy tắc**.

**Dữ liệu đảm bảo:**
- $1 \le n \le 10^6$.
- $|a_{i, j}| \le 10^6$.

**Subtasks:**
- $30\%$ số điểm tương ứng với $1 \le n \le 20$.
- $70\%$ số điểm không có ràng buộc gì thêm.

### Subtask 1

Áp dụng giải thuật ==quay lui== để thử ==mọi cách== xếp bảng thỏa mãn quy tắc, sau đó lấy tổng giá trị lớn nhất.

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

### Subtask 2

- **Định nghĩa:**
- ==$dp_{1, j}$== là tổng lớn nhất tạo được xét $j$ cột đầu tiên và lấy ô $(1, j)$.
- ==$dp_{2, j}$== là tổng lớn nhất tạo được xét $j$ cột đầu tiên và lấy ô $(2, j)$.
- **Khởi gán:**
- ==$dp_{1, 1}$== $= a_{1, 1}$.
- ==$dp_{2, 1}$== $= a_{2, 1}$.
- **Công thức:**
- $dp_{1, j}$ bằng giá trị lớn nhất trong $4$ giá trị sau đây:
- $dp_{2, j-1} + a_{1, j}$ (cột $j-1$ lấy ô ở hàng 2, cột $j$ lấy ô ở hàng 1)
- $dp_{2, j-2} + a_{1, j} + a_{1, j-1}$ (cột $j-1$ lấy ô ở hàng 1, cột $j$ lấy ô ở hàng 1)
- Tương tự với $dp_{2, j}$.
- **Kết quả:** ==$dp_K$==.

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

:::success
:::spoiler Code

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

const int N = 1e6;
int n, A[2][N+1], dp[2][N+1];

int main() {
    cin >> n;
    for (int i = 0; i <= 1; i++)
        for (int j = 1; j <= n; j++)
            cin >> A[i][j];

    dp[0][1] = A[0][1];
    dp[1][1] = A[1][1];
    for (int j = 2; j <= n; j++) {
        dp[0][j] = max(dp[1][j-1] + A[0][j], dp[1][j-2] + A[0][j] + A[0][j-1]);
        dp[1][j] = max(dp[0][j-1] + A[1][j], dp[0][j-2] + A[1][j] + A[1][j-1]);
    } 

    cout << max(dp[0][n], dp[1][n]);

    return 0;
}

:::