# Nguồn đề
- Đề HSG 9 : 2015 - 2016
- Đề HSG 12 : 2016 - 2017
# Lời giải
## Lớp 9
### Bài 1 - Đếm số
#### Tag
Duyệt
#### Lời giải chi tiết
- Tạo một biến kết quả lưu lại số lượng số chẵn trong dãy, sau đó ta duyệt qua các phần tử của dãy, nếu phần tử nào chia dư cho $2$ được $0$ thì ta tăng biến kết quả lên $1$ đơn vị.
#### Độ phức tạp
- $O(N)$
### Bài 2 - Xếp chữ
#### Tag
Đánh dấu phần tử, Duyệt.
#### Lời giải chi tiết
- Ta tạo một mảng đánh dấu có phạm vi là 'A' đến 'Z', sau đó ta duyệt qua lần lượt các ký tự có trong xâu cho trước, với mỗi ký tự ta duyệt qua, ta tăng lên một đơn vị.
- Sau khi tạo xong mảng đánh dấu số lần xuất hiện, ta duyệt các ký tự từ 'A' đến 'Z', nếu ký tự nào có số lần xuất hiện lớn hơn 0 thì ta sẽ in ra.
#### Độ phức tạp
- $O(N)$.
### Bài 3 - Tính tổng
#### Tag
Số nguyên lớn.
#### Lời giải
- Vào thời điểm đề này ra thì tỉnh Quảng Bình chỉ cho sử dụng ngôn ngữ Pascal nên bài này xử lý số nguyên lớn, còn thời điểm hiện nay được phép sử dụng Python nên ta chỉ cần tính như $a+b$ bình thường.
#### Độ phức tạp
$O(N+M)$
## Lớp 12
### Bài 1 - Tần số
#### Tag
Đánh dấu phần tử, duyệt.
#### Lời giải
- Đánh dấu lại số lần xuất hiện các phần tử trong mảng ban đầu, sau đó duyệt giá trị từ $1$ đến $100$, nếu nó xuất hiện trong dãy ban đầu thì ta in ra.
#### Độ phức tạp
- $O(N)$
### Bài 2 - Biển số đẹp
#### Tag
Kiểm tra số nguyên tố, duyệt
#### Lời giải chi tiết
- Nhận thấy rằng, với giới hạn phạm vi như đề bài đã cho, chỉ có $900$ số đối xứng, vậy nên ta sẽ duyệt qua các giá trị từ $u$ đến $v$ sau đó ta sẽ ưu tiên kiểm tra xem nó có phải là một số đối xứng hay không, nếu có thì ta mới kiểm tra số nguyên tố.
#### Độ phức tạp
- $O(900*\sqrt{v})$
### Bài 3 - Số sát sau
#### Tag
Adhoc.
#### Lời giải chi tiết
- Nhận thấy rằng để số $b$ lớn hơn số $a$ thì chỉ cần một chữ số lớn hơn $a$ và phía trước nó bằng nhau, phía sau nó thứ tự thế nào không quan trọng, vậy nên ta sẽ tìm chữ số phải nhất mà sau nó có phần tử lớn hơn nó, hoán đổi giá trị của $2$ phần tử này và sắp xếp tăng dần những thằng phía sau để đảm bảo nó nhỏ nhất.
#### Độ phức tạp
- $O(N\log{N})$
### Bài 4 - Robot
#### Tag
DFS/BFS, Đường đi ngắn nhất
#### Lời giải chi tiết
- Lưu lại vị trí của ô có giá trị là $R$ và $Q$, sau đó sử dụng thuật toán BFS để tìm đường đi ngắn nhất từ $Q$.
#### Độ phức tạp
- $O(N+M)$