Đề 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)
2. 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\ast \ast \ast \ast }$. 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$