# Đề TS10 - BRVT - 2017: 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 2017 - 2018.
>
>**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

Nhập vào số nguyên dương $N$.

**Yêu cầu:** Tính kết quả các biểu thức sau:
- $A = \frac{1}{2} + \frac{2}{2^2} + \frac{3}{2^3} + \dots + \frac{N}{2^N}$
- $B = \frac{1 \times 2}{3 \times 4} + \frac{3 \times 4}{5 \times 6} + \frac{5 \times 6}{7 \times 8} + \dots + \frac{(2N - 3)(2N - 2)}{(2N - 1)2N}$

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

### **Tính A**

Cho biến $i$ chạy vòng lặp từ $1$ đến $n$, cộng ==$\frac{i}{2^i}$== vào kết quả.

>[!Caution] Lưu ý
> Để tránh số quá lớn, ta nên lấy $i$ và chia liên tục cho $2$ thay vì tính $2^i$

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

### **Tính B**

Cho biến $i$ chạy vòng lặp từ $2$ đến $n$, cộng ==$\frac{(2i - 3)\times(2i -2)}{2i}$== vào kết quả.

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

### **Mã nguồn mẫu**

:::info
Độ phức tạp thời gian của cả bài toán là ==tổng độ phức tạp thời gian== của từng yêu cầu.
:::

:::success
:::spoiler Code

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

int main() {
	int n;
	double A = 0, B = 0;

	cin >> n;
	for (int i = 1; i <= n; i++) {
		double ret = i;
		for (int j = 1; j <= i; j++) {
			ret /= 2;
        }

		A += ret;

		if (i >= 2) {
            B += (double)(2*i - 3)*(2*i - 2) / (2*i - 1) / (2*i);
        }
	}

	cout << fixed << setprecision(3) << A << "\n" << B;

	return 0;
}

:::

## Bài 2:

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

Nhập vào $3$ số nguyên dương $a, b$ và $N$.

**Yêu cầu:**
- Tìm các **số nguyên tố** nằm trong đoạn $[a, b]$.
- Tìm **chữ số chẵn lớn nhất** của $N$.

**Dữ liệu đảm bảo:** $2 \le a < b \le 2 \times 10^5$ và $1 \le N \le 10^{18}$

### **Yêu cầu 1**

Duyệt qua các số từ $a$ đến $b$, kiểm tra tính nguyên tố của mỗi số bằng cách ==duyệt đến căn bậc hai== của số đó để tìm ước.

**Độ phức tạp thời gian:** $O \left( \sqrt a + \sqrt {a+1} + \dots + \sqrt b \right) = O\left( \sum_{i = a}^b \sqrt i \right)$.

### **Yêu cầu 2**

Duyệt qua các chữ số của $n$ để tìm ==chữ số chẵn lớn nhất==. Có thể thực hiện bằng cách không ngừng lấy chữ số tận cùng của $n$ là $n \bmod 10$, sau đó ta ==chia $n$ cho $10$== để xóa chữ số đó đi và tìm chữ số tiếp theo.

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

### **Mã nguồn mẫu**

:::info
Độ phức tạp thời gian của cả bài toán là ==tổng độ phức tạp thời gian== của từng yêu cầu.
:::

:::success
:::spoiler Code

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

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

	return 1;
}

int main() {
	int a, b;
    long long n;
	cin >> a >> b >> n;

	for (int i = a; i <= b; i++) {
		if (isPrime(i)) {
			cout << i << " ";
        }
    }

	int res = -1;
	do {
        if ((n % 10) % 2 == 0) {
            res = max(res, n % 10);
        }
    } while (n /= 10);

	cout << "\n" << res;

	return 0;
}

:::

## Bài 3:

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

Cho dãy số nguyên gồm $N$ phần tử $a_1, a_2, \dots, a_N$ và số nguyên $X$.

**Yêu cầu:**
- Liệt kê các phần tử **dương** có dạng ==$5 \times k$ (với $k$ là số nguyên bất kỳ)== theo thứ tự ban đầu của dãy.
- Tìm **tích lớn nhất** của hai phần tử bất kỳ trong dãy (không trùng nhau).
- Sắp xếp dãy **tăng dần** và thực hiện chèn thêm một phần tử có giá trị $X$ vào dãy sao cho vẫn giữ nguyên tính chất **tăng dần** của dãy số.

**Dữ liệu đảm bảo:**
- $2 \le N \le 10^5$.
- $|a_i| \le 10^6$.
- $|X| \le 2 \times 10^6$

### **Yêu cầu 1**

>[!Tip] Nhận xét
>$$
>A_i = 5k \Leftrightarrow 5k = A_i \Leftrightarrow k = \frac {A_i}{5}
>$$
> Mà $k$ nguyên, do đó $A_i$ chia hết cho $5$, hay ==$A_i \bmod 5 = 0$==.

Như vậy, ta duyệt qua dãy và in ra các số thỏa mãn điều kiện trên.

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

### **Yêu cầu 2**

>[!Tip] Nhận xét
> Dễ nhận thấy, ==hai số lớn nhất== của dãy sẽ tạo ra tích lớn nhất.
> :::danger
> **Lưu ý:** ==Hai số bé nhất (cùng âm)==, khi nhân vào sẽ tạo ra tích dương, và có thể lớn hơn tích của hai số lớn nhất.
> :::

Sắp xếp dãy tăng dần, ta có:
- Hai số lớn nhất là $A_N$ và $A_{N-1}$.
- Hai số nhỏ nhất là $A_1$ và $A_2$.

**Đáp án:** ==$\max(A_N \times A_{N-1}, A_1 \times A_{2})$==.

**Độ phức tạp thời gian:** $O(n \log n)$ do thao tác sắp xếp mảng.

### **Yêu cầu 3**

Để giữ nguyên tính chất tăng dần của dãy, ta cần chèn $x$ vào giữa hai vị trí ==$i$ và $i+1$== sao cho ==$A_i \le x \le A_{i+1}$==.

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

### **Yêu cầu 4**

>[!Note]Nhận xét:
>Chênh lệch giữa hai phần là lớn nhất khi một phần đạt tổng lớn nhất có thể và phần còn lại phải nhỏ nhất có thể.
>Dễ dàng nhận thấy,
>- Nếu $k \ge n-k$, ta nhóm ==$k$ phần tử lớn nhất== chung với nhau và ==$n-k$ phần tử nhỏ nhất== chung với nhau
>- Nếu $k \lt n-k$, ta nhóm ==$n-k$ phần tử lớn nhất== chung với nhau và ==$k$ phần tử nhỏ nhất== chung với nhau

Có thể tìm nhanh tập các phần tử lớn nhất hoặc nhỏ nhát bằng cách sắp xếp lại dãy số. Để dễ thao tác, ta ==không thực sự chèn số vào==, mà ta sẽ duyệt qua dãy và in ra các số, nếu đúng vị trí của $x$ ta sẽ in ra $x$.

>[!Caution] Lưu ý
> Trường hợp $x$ lớn hơn tất cả các số trong dãy, ta phải thêm $x$ vào cuối.

**Độ phức tạp thời gian:** $O(n)$ vì dãy đã được sắp xếp sẵn ở yêu cầu trước.

### **Mã nguồn mẫu**

:::info
Độ phức tạp thời gian của cả bài toán là ==tổng độ phức tạp thời gian== của từng yêu cầu.
:::

:::success
:::spoiler Code

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

const int N = 1e5;
int n, X, A[N+1];

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

	cin >> X;

	for (int i = 1; i <= n; i++) {
		if (A[i] > 0 && A[i] % 5 == 0) {
			cout << A[i] << " ";
        }
    }

	sort(A+1, A+1+n);
	cout << "\n" << max(1LL * A[1] * A[2], 1LL * A[n-1] * A[n]) << "\n";

	bool used = 0;
	for (int i = 1; i <= n; i++) {
		if (X <= A[i] && !used) {
			used = 1;
			cout << X << " ";
		}

		cout << A[i] << " ";
	}

	if (!used) {
        cout << X << " ";
    }

	return 0;
}

:::

## Bài 4:

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

Có $N$ cây xanh xếp thành một hàng thẳng, lần lượt cách cổng trường THPT chuyên Lê Quý Đôn $a_1, a_2, \dots, a_N$. Bóng của chúng cũng thẳng hàng và bóng của cây thứ $i$ có chiều dài là $d_i$.

**Yêu cầu:** Tính tổng chiều dài của các bóng cây phủ trên đường.
> Lưu ý: Nếu có vùng bị phủ bóng bởi nhiều hơn một cây, chỉ xem vùng đó là một.

**Dữ liệu đảm bảo:** $1 \le N \le 10^5$, $0 < a_i \le 10^6$ và $0 < d_i \le 10^3$.

### Lời giải

>[!Tip] Mô hình hóa bài toán
> Dễ thấy, cây thứ $i$ cho ta vùng bóng ==$[a_i, a_i + d_i - 1]$==.
> Với mỗi vùng tương ứng của từng cây, ta cộng tất cả phần tử trong khoảng lên $1$.

Để cộng nhanh từng đoạn, ta áp dụng [**mảng hiệu**](https://wiki.vnoi.info/algo/data-structures/prefix-sum-and-difference-array.md).

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

### **Mã nguồn mẫu**

:::success
:::spoiler Code

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

const int N = 5e6;
int n, F[N+1];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		for (int j = x; j <= x+y-1; j++)
		    F[j]++;
	}

	int res = 0;
	for (int i = 1; i <= N; i++)
		if (F[i]) res++;

	cout << res;

	return 0;
}

:::