# Đề TS10 - BRVT - 2023: 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 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_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

Một quyển sách gồm $N$ trang. Trong đó trang $1$ luôn nằm phía bên phải của trang bìa đầu, trang $N$ luôn nằm ở mặt bên trái của trang bìa cuối của quyển sách.

Sau khi lật trang $1$ sẽ đến trang $2, 3$, rồi đến $4, 5$, ... Ngược lại, nếu lật từ trang $N$, ta sẽ đến trang $N-1, N-2$, rồi $N-3, N-4$, ...

**Yêu cầu:** Cho $P$, tìm số bước ít nhất để lật đến trang $P$.

**Dữ liệu đảm bảo:** $N \le 10^{18}$ và $1 \lt P \lt N$.

**Ràng buộc:**
- $75\%$ số điểm tương ứng với $1 \lt P \lt N \le 10^9$;
- $25\%$ số điểm tương ứng với $10^9 \lt P \lt N \le 10^{18}$.

### Subtask 1

Mô phỏng lại quá trình lật sách, ==duyệt vòng lặp== để lật từ trang $1$ đến trang $P$, và từ trang $N$ đến trang $P$, kết quả là số lần lật ít hơn trong hai cách lật.

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

:::success
:::spoiler Code

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

long long n, p, kq1, kq2;

void lm(){
    long long i;
    for (i = 2; i <= p; i += 2) {
        kq1++;
    }
    
    if (p == n) {
        cout << 0;
        return;
    }
    
    for (i = n - 1; i >= p; i -= 2)
        kq2++;
    
    cout << min(kq1, kq2);
}

int main() {
    cin >> n >> p;
    if (p == 1) cout << 0;
    else lm();
    
    return 0;
}

:::

### Subtask 2

>[!Tip] Nhận xét
> Trừ trang $1$ và trang $n$, dễ thấy các trang có tính chất xuất hiện ==theo cặp==:
> $$
> (2, 3), (4, 5), (6, 7), (8, 9), \dots
> $$
> Nghĩa là, số bước lật đến trang $3, 5, 7, 9, \dots$ cũng bằng số bước lật đến trang $2, 4, 6, 8, \dots$

Để dễ xử lí, sau khi nhập vào $p$, nếu $p$ chẵn, ta trừ đi $1$ để được $p$ chẵn.

**Đáp án:** ==$\min \left( \frac{p}{2}, \frac{n-p}{2} \right)$==

**Độ 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, p;
    
	cin >> n >> p;
	if (p % 2 != 0) {
        p--;
    }

    cout << min(p / 2, (n-p) / 2);
    
    return 0;
}

:::

## Bài 2

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

Cho hai số $a$ và $b$ ở ==hệ nhị phân==.

**Yêu cầu:** Đếm số lượng ==số chính phương== trong đoạn $[a, b]$.

**Dữ liệu đảm bảo:** $1 < a < b \le 10^{18}$.

**Ràng buộc:**
- $75\%$ số điểm tương ứng với $1 \lt a \lt b\le10^9$.
- $25\%$ số điểm tương ứng với $1 \lt a \lt b\le10^{18}$.

### Nhị phân và thập phân

>[!Important]
> Để xử lý được bài toán này, bắt buộc cần phải biến đổi $a$ và $b$ từ hệ nhị phân sang hệ thập phân.
> > VD: $1110_2 = 14_{10}$

Trước tiên, cần nắm được ==mối quan hệ giữa số nhị phân và số thập phân==:
$$
x_{n-1} x_{n-2} \dots x_1 x_0 = x_0 \times 2^0 + x_1 \times 2^1 + \dots + x_{n-2} \times 2^{n-2} + x_{n-1} \times 2^{n-1}
$$

Trong đó, vế trái là ==số nhị phân== bất kỳ, và vế phải là ==biểu diễn thập phân== tương ứng của số nhị phân đã cho.
>VD: $1110_2 = 0 \times 2^0 + 1 \times 2^1 + 1 \times 2^2 + 1 \times 2^3 = 14_{10}$

:::danger
**Lưu ý:** Trong hệ nhị phân, các chữ số được đánh số từ $0$, và từ phải qua trái.
:::

Để tính nhanh $2^0, 2^1, \dots, 2^{n-1}$, ta duyệt theo thứ tự các chữ số của số nhị phân, đồng thời duy trì một biến giá trị $2^i$. Sau khi duyệt qua một số, ta nhân thêm $2$ vào giá trị này.

:::success
:::spoiler Code

int binToDec(string s) {
    int ret = 0;
    long long k = 1;
    for (int i = s.length() - 1; i >= 0; i--) {
        ret += k * (s[i] - '0');
        k *= 2;
    }
    
    return ret;
}

:::

### Subtask 1

Duyệt ==vòng lặp từ $a$ đến $b$== các số chính phương tối đa đến $b$, và kiểm tra xem số đó có lớn hơn hoặc bằng $a$ hay không. Nghĩa là duyệt $i$ từ $1$, số chính phương tương ứng là $i \times i$, đến khi $i \times i > b$ thì dừng, trong lúc đó kiểm tra số $i \times i$ để thêm vào đáp án.

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

:::success
:::spoiler Code

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

string s1, s2;
long long a, b;

void string_to_num() {
    long long k = 1;
    for (int i = s1.length() - 1; i >= 0; i--) {
        a += k*(s1[i]-'0');
        k *= 2;
    }

    k = 1;
    for (int i = s2.length() - 1; i >= 0; i--) {
        b += k*(s2[i]-'0');
        k *= 2; 
    }
}

int main() {
    cin >> s1 >> s2;
    string_to_num();
    
    long long res = 0;
    for (long long i = 1; i*i <= b; i++)
        if (i*i >= a)
            res++;
    
    cout << res;
    
    
}

:::

### Subtask 2

>[!Tip]
> Ký hiệu số chính phương là ==$k^2$== với ==$k \in N$==.

Theo bài toán, ta có: ==$a \le k^2 \le b$==
$$
\begin{flalign}
&\Leftrightarrow \sqrt a \le k \le \sqrt b \\
&\Leftrightarrow \left\lceil \sqrt a \,\right\rceil \le k \le \left\lfloor \sqrt b \,\right\rfloor
\end{flalign}
$$

Như vậy, đáp án của bài toán là:
$$
\left\lfloor \sqrt b \,\right\rfloor - \left\lceil \sqrt a \,\right\rceil + 1
$$

>[!Caution] Lưu ý
> Cần sử dụng hàm `sqrtl` thay cho hàm `sqrt` để đảm bảo độ chính xác. Hoặc tốt hơn nữa, là kiểm tra lại bằng câu lệnh `if` sau khi sử dụng hàm để tính căn bậc hai.

**Độ phức tạp thời gian:** $O \left( \log a + \log b \right)$.
> Hàm `sqrt` hay `sqrtl` có chi phí thời gian là $\log$.
>
:::success
:::spoiler Code

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

string s1, s2;
long long a, b;

void string_to_num() {
    long long k = 1;
    for (int i = s1.length() - 1; i >= 0; i--) {
        a += k*(s1[i]-'0');
        k *= 2;
    }

    k = 1;
    for (int i = s2.length() - 1; i >= 0; i--) {
        b += k*(s2[i]-'0');
        k *= 2; 
    }
}

int main() {
	cin >> s1 >> s2;
	string_to_num();
    cout << floor(sqrtl(b)) - ceil(sqrtl(a)) + 1;
	return 0;
}

:::

## Bài 3

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

Có $N$ học sinh tham gia trò chơi được xếp hàng thành một đường thẳng và được đánh số thứ tự từ $1$ đến $N$. Biết không được xếp $3$ bạn nam cùng đứng kế nhau.

**Yêu cầu:** Hãy cho biết có bao nhiêu cách xếp hàng thỏa mãn điều kiện trên.

**Dữ liệu đảm bảo:** $N \le 64$.

**Ràng buộc:**
- $25\%$ số test tương ứng với $1<N\le20$.
- $75\%$ số test tương ứng với $20<N\le64$.

### Subtask 1

==Quay lui== để duyệt các ==cách chọn== hợp lệ và cộng vào đáp án.

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

:::success
:::spoiler Code

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

long long n, kq;

void backTrack(long long i, long long tmp){
    if (i == n + 1) {
        kq++;
        return;
    }
    
    if (tmp < 2) {
        backTrack(i + 1, tmp + 1);
    }
        
    backTrack(i + 1, 0);
}

int main() {
    cin >> n;
    backTrack(1, 0);
    cout << kq;
    return 0;
}

:::

### Subtask 2

Áp dụng ==quy hoạch động cơ bản==. Để dễ thao tác, ta coi học sinh nam là `1` và học sinh nữ là `0`

- **Định nghĩa:** $dp_i$ là số cách xếp $i$ học sinh thỏa yêu cầu đề bài.
- **Khởi gán:**
- $dp_1 = 2$ (`1` / `0`)
- $dp_2 = 4$ (`11` / `00` / `10` / `01`)
- $dp_3 = 7$ (`110` / `000` / `100` / `010` / `001` / `101` / `011`)
- **Công thức:** $dp_i = dp_{i-1} + dp_{i-2} + dp_{i-3}$, trong đó:
- $dp_{i-1}$: Có thể ghép `0` vào một dãy đã hợp lệ mà chắc chắn vẫn hợp lệ.
- $dp_{i-2}$: Có thể ghép `01` vào một dãy đã hợp lệ mà chắc chắn vẫn hợp lệ.
- $dp_{i-3}$: Có thể ghép `011` vào một dãy đã hợp lệ mà chắc chắn vẫn hợp lệ.

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

:::success
:::spoiler Code

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

long long n, kq, dp[100];

int main() {
    cin >> n;
    
    dp[1] = 2;
    dp[2] = 4;
    dp[3] = 7;
    
    for (int i = 4; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }
    
    cout << dp[n];
    
    return 0;
}

:::

## Bài 4

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

Hoàng có một chiếc thẻ nhớ ngoài dung lượng ==$K$ (Gigabyte - GB)== để lưu ảnh. Cho biết thông về số lượng các loại bức ảnh, mỗi loại sẽ có dung lượng $a_i$ và tính thẩm mỹ $b_i$. Biết rằng một loại ảnh có thể ==không được chọn== hoặc ==chọn với số lượng không hạn chế==.
> **Ghi chú:** 1GB = 1024MB

**Yêu cầu:** Cho biết tổng giá trị lớn nhất của tính thẩm mỹ thu được khi chọn các ảnh mà vẫn đảm bảo không vượt quá dung lượng?

**Dữ liệu đảm bảo:** $2\le N \le 1000$, $1\le K \le 4$, $1\lt a_i \le 1024$ và $1\lt b_i \le 10^9$.

**Ràng buộc:**
- $50\%$ số điểm tương ứng với $2\le N\le500$, $K\le2$, $a_i\le1024$, $b_i\le32000$.
- $50\%$ số điểm tương ứng với $2\le N\le1000$, $K\le4$, $a_i\le1024$, $b_i\le10^9$.

### Subtask 1

Áp dụng ==quy hoạch động cái túi== theo cách cơ bản.

- **Định nghĩa:** $dp_{i,j}$ là tính thẩm mỹ lớn nhất khi chọn từ $i$ loại ảnh đầu tiên và tổng dung lượng bằng $j$.
- **Khởi gán:** $dp_{0,0} = 0$ (khi không chọn ảnh nào thì tổng thẩm mỹ bằng $0$).
- **Công thức:** Lấy kết quả tốt nhất trong hai trường hợp:
- $dp_{i, j} = dp_{i-1, j}$ (không lấy loại ảnh thứ $i$, giữ độ thẩm mỹ đạt được với $i-1$ loại)
- $dp_{i, j} = \max ( dp_{i-1, j - x \times A_i + x \times B_i} )$ với $x$ là số lượng ảnh loại $i$ ta lấy.

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

:::success
:::spoiler Code

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

const int N = 1e3, K = 4*1024;
int n, k;
long long F[N+1][K+1], A[N+1], B[N+1];

int main() {
	cin >> n >> k;
    k *= 1024;
    
	for (int i = 1; i <= n; i++) {
        cin >> A[i] >> B[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            F[i][j] = F[i-1][j];
            if (j - A[i] >= 0) {
                for (int x = 1; x * A[i] <= j; x++) {
                    F[i][j] = max(F[i][j], F[i-1][j - x*A[i]] + x*B[i]);
                }
            }
        }
    }

    cout << F[n][k];

	return 0;
}

:::

### Subtask 2

>[!Tip] Nhận xét
> Ở bài toán **cái túi** cụ thể này, ta không cần quan tâm đến ràng buộc về phần tử (ta có thể bỏ các đồ vật không giới hạn).
> :::success
> Do đó, có thể **bỏ chiều $i$** trong công thức quy hoạch động ban đầu.
> :::

Áp dụng ==quy hoạch động cái túi== biến thể.

- **Định nghĩa:** $dp_{j}$ là tính thẩm mỹ lớn nhất khi chọn ảnh để tổng dung lượng bằng $j$.
- **Khởi gán:** $dp_{0} = 0$ (khi không chọn ảnh nào thì tổng thẩm mỹ bằng $0$).
- **Công thức:** $dp_j = \max(dp_{j - A_i} + B_i) \; \forall \; A_i \le j$ (lấy thêm ảnh thứ $i$).

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

:::success
:::spoiler Code

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

const int N = 1e3, K = 4*1024;
int n, k;
long long F[K+1], A[N+1], B[N+1];

int main() {
    cin >> n >> k;
    k *= 1024;

    for (int i = 1; i <= n; i++) {
        cin >> A[i] >> B[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            if (j - A[i] >= 0) {
                F[j] = max(F[j], F[j - A[i]] + B[i]);
            }
        }
    }

    cout << F[k];

    return 0;
}

:::