# Đề THTB Đà Nẵng 2022

## Bài 2

### Subtask 1: $x \le 10^6$

Ta có thể thử từng giá trị của $y$ bằng vòng lặp `for`. Với mỗi $y$, có được $x+y$ và lấy tổng này kiểm tra xem có "siêu đối xứng" không?

Thuật toán:
1. Chạy for y (để thử)
2. Tính tổng
3. Kiểm tra tổng có phải "siêu đối xứng" không?

Mã giả:

for (y từ 1 tới 10^7) {
    biết x, biết y
    tổng = x+y
    kiem_tra(tổng)
}

Cách kiểm tra
1. Chuyển thành String
2. Chia 10, chia dư 10, ....

Tổng $x+y$ sẽ luôn nhỏ hơn $1111111$ (bảy cs) nên sẽ không bị TLE. Viết hàm kiểm tra số siêu đối xứng.

### Subtask 3: $x \le 10^{16}$

123456
...
123457
210987
...
222222

Thuật toán:
1. Chạy for tất cả những số siêu đối xứng (gọi là $z$), số nào có thể là tổng
a. Số SĐX là một chữ số lặp lại nhiều lần
b. Chọn độ dài, chọn chữ số (bằng vòng lặp for)
3. Check $(z > x) \Rightarrow y = z - x$

for (độ dài từ 1 tới 17) {
    for (chữ số từ 1 tới 9) {
        Tạo ra z là tổng? (for)
        z > x
        y = z - x
    }
}

### Subtask 4?: $x \le 10^{N}$

`135, 222, 867`

1236748712367581236
< 
11111111111111111111

1236748712367581236
< 
2222222222222222222

105
< 
111

33345
< 
111

987
990

## Bài 3

### Subtask 1.

Có những số $a \le x$ nào mà $a$ là SNT và $b = x-a$ cũng là SNT?
Không biết --> Chạy for tất cả giá trị có thể của $a$

1. Chạy for a
2. b = x - a
3. Kiểm tra a là SNT?
4. Kiểm tra b là SNT?

Hàm kiểm tra SNT: Xem Lesson "Số học"

Nếu hàm kiểm tra $n$ là SNT chạy trong ĐPT $O(n)$

### Subtask 2.

Nếu hàm kiểm tra $n$ là SNT chạy trong ĐPT $O(\sqrt{n})$

### Subtask 3

Tối ưu kiểm tra SNT bằng kĩ thuật "Sàng nguyên tố". Sàng Eratosthenes

## Bài 4
Subtask 1: Đệ quy quay lui (backtracking)

Subtask 2: Quy hoạch động cơ bản + Big Num

## Bài 5:

Bài toán đếm thứ tự từ điển.
Lần lượt xây dựng các chữ số $\overline{p****}$. Với prefix là $p$, có bao nhiêu số nhận $p$ làm prefix?
Lần lượt điền các chữ số từ $0,1,2,\dots,9$ vào vị trí dấu * kế tiếp để mở rộng prefix. Mở rộng tới khi đã tìm thấy số thứ $N$

QHĐ chữ số? Không cần thiết vì chỉ là $5^k$