Kỳ thi ngày 26/08/2026

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Mật mã nguyên tố	100 (p)	1.0s	256M
2	Ma trận robot	100 (p)	1.0s	256M
3	Bảng điểm tự động	100 (p)	1.0s	256M

1. Mật mã nguyên tố

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bài toán kiểm tra kiến thức về hàm và duyệt $for$

Một số nguyên dương $X$ được gọi là "Số Khởi Nguyên" nếu nó thỏa mãn đồng thời hai điều kiện sau:

$X$ là số nguyên tố.
Tổng các chữ số của $X$ cũng là một số nguyên tố.

Cho hai số nguyên dương $L$ và $R$. Hãy viết chương trình đếm xem có bao nhiêu "Số Khởi Nguyên" nằm trong đoạn từ $L$ đến $R$ (tính cả $L$ và $R$).

Học sinh có thể sử dụng hàm kiểm tra số nguyên tố dưới đây để phục vụ cho việc làm bài.

C++

bool nguyento(int n){
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
            return false;
    return true;
}
// Hàm trả về true nếu n là số nguyên tố, ngược lại trả về false.
// Số nguyên tố là số có đúng 2 ước nguyên dương 1 và chính nó.

Input

Một dòng duy nhất chứa hai số nguyên dương $L$ và $R$ ($1 \leq L \leq R \leq 10^5$).

Output

In ra một số nguyên duy nhất là số lượng "Số Khởi Nguyên" tìm được.

Example

Test 1

Input

1 20

Output

Note

Các "Số Khởi Nguyên" trong đoạn từ $1$ đến $20$ là: $2, 3, 5, 7, 11$. (Vì $2, 3, 5, 7$ là số nguyên tố và tổng chữ số lần lượt là $2, 3, 5, 7$ đều là số nguyên tố; số $11$ là số nguyên tố và tổng chữ số là $1 + 1 = 2$ cũng là số nguyên tố).

2. Ma trận robot

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một robot được thả vào một bản đồ hình chữ nhật kích thước $N \times M$. Bản đồ được chia thành các ô vuông, mỗi ô có thể là:

Ký tự .: Ô trống, có thể đi qua.
Ký tự #: Vật cản, không thể đi qua.
Ký tự $: Chứa một khối năng lượng.

Robot xuất phát tại tọa độ $(1, 1)$ (góc trên cùng bên trái) và nhận được một chuỗi lệnh di chuyển $S$ gồm các ký tự U (Lên), D (Xuống), L (Trái), R (Phải).

Giải thích chi tiết hệ tọa độ và cách di chuyển

Bản đồ được biểu diễn dưới dạng mảng 2 chiều. Ô xuất phát $(1, 1)$ nằm ở góc trên cùng bên trái. Ta quy ước tọa độ $(x, y)$ tương ứng với $(h\text{à}ng, c\text{ộ}t)$:

$x$: Chỉ số hàng (tăng dần từ trên xuống dưới).
$y$: Chỉ số cột (tăng dần từ trái sang phải).

Dưới đây là bảng phân tích quy luật thay đổi tọa độ cho từng lệnh di chuyển, giả sử robot đang đứng ở một ô bất kỳ có tọa độ $(x, y)$ và ví dụ cụ thể khi robot đứng ở ô $(3, 3)$:

Lệnh	Hướng di chuyển	Công thức thay đổi tọa độ	Ví dụ từ ô $(3, 3)$
`R`	Sang phải	$(x, y) \rightarrow (x, y + 1)$	$(3, 3) \rightarrow (3, 4)$
`L`	Sang trái	$(x, y) \rightarrow (x, y - 1)$	$(3, 3) \rightarrow (3, 2)$
`D`	Đi xuống	$(x, y) \rightarrow (x + 1, y)$	$(3, 3) \rightarrow (4, 3)$
`U`	Đi lên	$(x, y) \rightarrow (x - 1, y)$	$(3, 3) \rightarrow (2, 3)$

Lưu ý quan trọng: Trước khi cho robot thực hiện bước đi, cần kiểm tra tọa độ mới. Nếu tọa độ mới đi ra ngoài biên của bản đồ (ví dụ: nhỏ hơn $1$ hoặc lớn hơn kích thước $N, M$) hoặc đi vào ô vật cản #, robot sẽ đứng im tại chỗ, giữ nguyên tọa độ cũ và chuyển sang lệnh tiếp theo.

Mỗi khi robot di chuyển vào một ô có năng lượng $, nó sẽ thu thập năng lượng đó và ô đó trở thành ô trống .. Nếu lệnh yêu cầu đi ra ngoài bản đồ hoặc đi vào vật cản #, robot sẽ đứng im tại chỗ và bỏ qua lệnh đó.

Hãy tính tổng số năng lượng robot thu thập được sau khi thực hiện hết chuỗi lệnh. Đảm bảo ô $(1, 1)$ luôn là ô ..

Input

Dòng 1: Hai số nguyên $N$ và $M$ ($1 \le N, M \le 100$).
$N$ dòng tiếp theo: Mỗi dòng là một xâu ký tự độ dài $M$ mô tả bản đồ.
Dòng cuối cùng: Xâu ký tự $S$ mô tả chuỗi lệnh (độ dài xâu $S$ không vượt quá $10^5$).

Output

In ra số lượng năng lượng thiết bị thu thập được.

Example

Test 1

Input

3 4
.$.$
#.#.
...$
RRR

Output

Note

Robot đi sang phải 3 lần. Các tọa độ đi qua: $(1, 1) \to (1, 2)$ (thu $1$) $\to (1, 3) \to (1, 4)$ (thu $1$). Tổng cộng $2$.

3. Bảng điểm tự động

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong một trò chơi, điểm số của người chơi liên tục được gửi về máy chủ. Bạn cần dùng cấu trúc dữ liệu phù hợp để quản lý các mức điểm này. Máy chủ sẽ nhận được $Q$ yêu cầu, mỗi yêu cầu thuộc một trong 3 loại:

1 X: Thêm một điểm số $X$ vào hệ thống.
2: In ra điểm số cao nhất hiện tại trong hệ thống.
3: Xóa đi một điểm số cao nhất hiện tại khỏi hệ thống (nếu có nhiều người cùng đạt điểm cao nhất, chỉ xóa 1 lần).

Nếu hệ thống đang trống mà gặp truy vấn loại 2, hãy in ra -1. Nếu hệ thống đang trống mà gặp truy vấn loại 3, hãy bỏ qua.

Input

Dòng 1: Số nguyên dương $Q$ ($1 \leq Q \leq 10^5$) là số lượng yêu cầu.
$Q$ dòng tiếp theo: Mỗi dòng bắt đầu bằng số $1$, $2$ hoặc $3$ thể hiện loại yêu cầu. Nếu là loại 1, sẽ có thêm số nguyên dương $X$ ($1 \leq X \leq 10^9$).

Output

Với mỗi truy vấn loại 2, in ra điểm số cao nhất trên một dòng.

Example

Test 1

Input

Output

20
20

Note

Sau 3 lệnh đầu, tập hợp là {10, 20, 20}.
Lệnh 4: In ra điểm cao nhất là $20$.
Lệnh 5: Xóa một điểm $20$. Tập hợp còn {10, 20}.
Lệnh 6: In ra điểm cao nhất là $20$.

Test 2

Input

Output

-1
50
-1

Note

Lệnh 1: Hệ thống đang trống, lệnh 2 yêu cầu in điểm cao nhất nên in ra -1.
Lệnh 2: Hệ thống rỗng, lệnh 3 yêu cầu xóa bị bỏ qua.
Lệnh 3: Thêm $50$ vào hệ thống. Tập hợp là {50}.
Lệnh 4: In ra điểm cao nhất hiện tại là $50$.
Lệnh 5: Xóa điểm $50$. Tập hợp trở lại trạng thái rỗng.
Lệnh 6: Hệ thống đang trống, lệnh 2 in ra -1.

Lệnh	Hướng di chuyển	Công thức thay đổi tọa độ	Ví dụ từ ô \((3, 3)\)
`R`	Sang phải	\((x, y) \rightarrow (x, y + 1)\)	\((3, 3) \rightarrow (3, 4)\)
`L`	Sang trái	\((x, y) \rightarrow (x, y - 1)\)	\((3, 3) \rightarrow (3, 2)\)
`D`	Đi xuống	\((x, y) \rightarrow (x + 1, y)\)	\((3, 3) \rightarrow (4, 3)\)
`U`	Đi lên	\((x, y) \rightarrow (x - 1, y)\)	\((3, 3) \rightarrow (2, 3)\)

Bộ đề bài

1. Mật mã nguyên tố

Bài toán kiểm tra kiến thức về hàm và duyệt \(for\)

Input

Output

Example

2. Ma trận robot

Giải thích chi tiết hệ tọa độ và cách di chuyển

Input

Output

Example

3. Bảng điểm tự động

Input

Output

Example