# Lời giải Tuyển sinh 10 trường THPT chuyên Khoa học Tự nhiên - Môn Tin học

Chấm bài tại đây: [ClueOJ](https://oj.clue.edu.vn/contest/khtn_ts10_25).

## Bài 1. Điểm

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

Cho $n$ đội, đội thứ $i$ có chỉ số sức bền $m_i$ và sức mạnh $v_i$. Tổng sức $t_i$ của đội $i$ là $m_i$ + $v_i$. Hãy tìm chênh lệch giữa đội có tổng sức lớn nhất và đội có tổng sức bé nhất.

### Lời giải

Ta tính ra mảng $t_i$ là tổng sức của đội thứ $i$. Ta sắp xếp mảng lại.

Kết quả sau khi sắp xếp mảng tăng dần sẽ là $t_n - t_1$.

Ta cũng có thể lặp hai lần để tìm đội có tổng sức lớn nhất và bé nhất, sau đó lấy hiệu.

Độ phức tạp: $O$ ($n \times log$ $n$) hoặc $O$ ($n$).

## Bài 2. Số dư

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

Cho số nguyên dương $n$. Hãy tính số dư của $2^{3^n}$ khi chia cho $5$.

### Lời giải

Ta thấy:
- $2^0$ chia $5$ dư $1$.
- $2^1$ chia $5$ dư $2$.
- $2^2$ chia $5$ dư $4$.
- $2^3$ chia $5$ dư $3$.
- $2^4$ chia $5$ dư $1$.
- ...

Vì vậy ta cần quan tâm tới số dư khi chia $3^n$ cho $4$.

- Với $n$ chẵn, $3^n$ sẽ là số chính phương, mà số chính phương lẻ chia $4$ luôn dư $1$. Vì vậy, $2^{3^n}$ chia $5$ dư $2$.
- Ngược lại, với $n$ lẻ, $3^n$ chia $4$ dư $1 \times 3 = 3$. Vì vậy, $2^{3^n}$ chia $5$ dư $3$.

Độ phức tạp: $O$ ($1$).

## Bài 3. Khoảng cách ngắn nhất

### Tóm tắt đề bài
Cho mảng $a$ gồm $n$ phần tử. Hãy tìm khoảng cách ngắn nhất giữa mọi cặp phần tử bằng nhau trong mảng. Nói cách khác, hãy tìm $min$ $(|i - j|)$ với mọi $1 \le i < j \le n$ và $a_i = a_j$.

### Subtask 1. $n \le 10^3$

Sử dụng hai vòng lặp, nếu $a_i = a_j$ thì cập nhật kết quả với $|i - j|$.

Độ phức tạp: $O$ ($n^2$).

### Subtask 2. $n \le 10^5$

Nhận xét: Với mọi $a_j$ ta cần quan tâm tới $a_i = a_j$ và với $i$ lớn nhất có thể.

Vì vậy, trong quá trình duyệt, ta sẽ lưu vị trí sau cùng ta gặp phần tử có giá trị là $x$ nào đó. Điều này có thể thực hiện với $map$. Hoặc cũng có thể nén số lại do ta chỉ quan tâm tính lớn bé của các phần tử, sau đó sử dụng mảng đánh dấu.

Độ phức tạp: $O$ ($n \times log$ $n$).

## Bài 4. Hình chữ nhật

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

Cho $n$ hình chữ nhật, mỗi hình có chiều dài là $d_i$ và chiều rộng là $r_i$.

Hình chữ nhật $A$ được định nghĩa là lớn hơn hình chữ nhật $B$ khi:
- Hoặc diện tích hình chữ nhật $A$ lớn hơn.
- Hoặc nếu diện tích bằng nhau, chiều dài hình chữ nhật $A$ lớn hơn chiều dài hình chữ nhật $B$.

Hãy tìm độ dài của dãy giảm dài nhất (không cần liên tiếp) của các hình chữ nhật.

### Subtask 1. $n \le 10^3$

Gọi $dp[i]$ là dãy hình chữ nhật giảm dài nhất, khi xét tới hình chữ nhật thứ $i$ và ta có chọn hình chữ nhật thứ $i$.

Ta có công thức truy hồi:
- $dp[i] = 1$ (cơ sở, dãy một hình chữ nhật luôn thỏa mãn).
- $dp[i] = max (dp[i], dp[j] + 1)$ nếu thỏa mãn một trong các điều sau:
- $area[j] > area[i]$ với $area[x]$ là diện tích hình chữ nhật thứ $x$.
- $d[j] > d[i]$.

Kết quả sẽ là $max$ của mảng $dp$.

Độ phức tạp: $O$ ($n^2$).

### Subtask 2. $n \le 10^5$.

Ta sẽ đánh chỉ số các hình chữ nhật theo cách thỏa mãn: gọi $a[i]$ là chỉ số của hình chữ nhật thứ $i$, nếu hình chữ nhật thứ $i$ lớn hơn hình chữ nhật thứ $j$, thì $a[i] < a[j]$.

Nếu đánh số được theo cách này, bài toán sẽ là bài [Dãy con tăng dài nhất](https://blog.vietcodes.com/algo/lis).

Ta sẽ sắp xếp lại các hình chữ nhật theo đề bài. Sau đó, chỉ số của hình chữ nhật thứ $i$ sẽ chính là vị trí của hình chữ nhật đó trong dãy đã sắp xếp. Cần cẩn thận tránh trường hợp có hai hình chữ nhật bằng nhau.

Độ phức tạp: $O$ ($n \times log$ $n$).