Thi thử đợt 1 tuyển sinh lớp 10 Chuyên PTNK 2026

Trên dãy núi có \(n\) trạm dừng chân. Đoàn thám hiểm xuất phát từ trạm \(1\) và muốn vượt qua tất cả \(n\) trạm lần lượt từ \(1\) đến \(n\). Trạm thứ \(i\) có độ cao \(h_i\).

Do địa hình hiểm trở và nhiệt độ thấp nên nếu chênh lệch độ cao giữa \(2\) trạm liên tiếp vượt quá \(D\) thì đoàn bắt buộc phải sử dụng thiết bị hỗ trợ để di chuyển. Để tiết kiệm năng lượng cho chuyến đi nên đoàn thám hiểm hạn chế sử dụng thiết bị hỗ trợ.

Yêu cầu: Tìm số lần tối thiểu phải sử dụng thiết bị hỗ trợ để di chuyển lần lượt từ trạm \(1\) đến trạm \(n\).

Input

• Dòng 1: chứa 2 số nguyên \(n\) và \(D\) (\(n \le 10^5; D \le 10^9\)).
• Dòng 2: chứa \(n\) số nguyên \(h_1, h_2, \dots, h_n\) (\(1 \le h_i \le 10^9\)).

Output

• Một số nguyên duy nhất là số lần tối thiểu phải sử dụng thiết bị hỗ trợ.

Example

5 10
10 25 30 45 50

2

3 100
10 20 30

0

1 5
10

0

Số nguyên dương \(X\) được gọi là "Nguyên tố cặp" nếu:

1. \(X\) là một số nguyên tố.
2. Tồn tại ít nhất một vị trí chia \(X\) thành 2 phần khác rỗng, mỗi phần đều tạo thành một số nguyên tố.

Ví dụ:

• \(317\) là nguyên tố cặp vì có thể chia thành \(3\) và \(17\), hoặc \(31\) và \(7\).
• \(307\) là nguyên tố cặp vì có thể chia thành \(3\) và \(07 \to\) tương đương \(3\) và \(7\).
• \(29\) không phải nguyên tố cặp vì chia thành \(2\) và \(9\) (\(9\) không phải số nguyên tố).
• \(103\) không phải nguyên tố cặp vì chia thành \((1, 03)\) và \((10, 3)\) đều không phải cặp nguyên tố.

Yêu cầu: Cho hai số nguyên dương \(L, R\). Hãy đếm số lượng số nguyên tố cặp trong đoạn \([L, R]\).

Input

• Dòng đầu chứa số nguyên \(T\) (\(1 \le T \le 10^5\)) là số lượng test.
• Mỗi dòng trong \(T\) dòng tiếp theo chứa 2 số \(L, R\) (\(1 \le L \le R \le 10^7\)).

Output

• Gồm \(T\) dòng, mỗi dòng ghi kết quả của bộ test tương ứng được cho trong dữ liệu vào.

Example

3
10 60
310 320
1 10

3
3
0

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(T \le 100; 1 \le L \le R \le 1000\).
• Subtask \(2\) (\(25\%\) số điểm): \(T \le 100; 1 \le L \le R \le 10^6\).
• Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Một robot di chuyển trong một bảng lưới ô vuông kích thước \(m \times n\). Ô ở dòng \(i\) và cột \(j\) kí hiệu \((i, j)\). Khi di chuyển đến ô \((i, j)\), năng lượng của robot được tăng thêm \(a_{ij}\) đơn vị. Robot xuất phát từ ô \((1, 1)\) và di chuyển đến ô \((m, n)\). Tại mỗi bước, robot chỉ được phép di chuyển sang ô chung cạnh bên phải hoặc ô chung cạnh bên dưới. Để kích hoạt cổng thoát tại ô \((m, n)\) và hoàn thành lộ trình, tổng năng lượng mà robot thu thập được trên toàn bộ lộ trình là lớn nhất và chia hết cho \(k\).

Yêu cầu

Tìm tổng năng lượng lớn nhất mà robot nhận được trên lộ trình thỏa yêu cầu.

Input

• Dòng đầu tiên chứa 3 số nguyên dương \(m, n, k\) (\(1 \le m, n \le 500\); \(1 \le k \le 200\)).
• Dòng thứ \(i\) trong \(m\) dòng tiếp theo chứa \(n\) số nguyên, số thứ \(j\) là \(a_{ij}\) (\(1 \le a_{ij} \le 10^6\)).

Output

• Một số nguyên là tổng năng lượng lớn nhất chia hết cho \(k\). Nếu không tồn tại lộ trình thỏa yêu cầu thì in ra \(-1\).

Example

5 7 11
2 5 3 1 8 4 6
7 1 9 2 5 3 1
4 6 2 8 1 7 5
9 3 5 1 4 2 8
1 7 4 6 2 9 3

44

5 7 30
2 5 3 1 8 4 6
7 1 9 2 5 3 1
4 6 2 8 1 7 5
9 3 5 1 4 2 8
1 7 4 6 2 9 3

-1

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(m, n, k \le 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(m, n \le 500; k = 1\).
• Subtask \(3\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Trong khu rừng già, chú khỉ KONG đang thực hiện một hành trình trên một đường thẳng từ thời điểm \(0\) đến thời điểm \(T\). KONG có hai chế độ di chuyển:

• Chế độ \(1\) (Leo trèo): tốc độ \(a\) mét/giây.
• Chế độ \(2\) (Đu dây): tốc độ \(b\) mét/giây.

KONG bắt đầu hành trình (thời điểm \(t = 0\)) với Chế độ 1. Trong hành trình, KONG nhận được \(n\) mệnh lệnh thay đổi chế độ. Mệnh lệnh thứ \(i\) cho biết: tại thời điểm \(t_i\), KONG chuyển sang chế độ \(m_i\) và duy trì chế độ đó cho đến khi nhận được mệnh lệnh tiếp theo hoặc đến hết thời điểm \(T\).

Yêu cầu: Cho \(Q\) truy vấn, mỗi truy vấn gồm \(2\) số nguyên \(L, R\) yêu cầu tính tổng quãng đường (đơn vị mét) mà KONG đã di chuyển từ giây thứ \(L\) đến giây thứ \(R\) (gồm cả giây \(L\) và giây \(R\)).

Input

• Dòng đầu tiên chứa \(5\) số nguyên dương \(n, T, Q, a, b\) (\(1 \le n, Q \le 10^5\); \(1 \le T \le 10^9\); \(1 \le a, b \le 10^6\)).
• Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa \(2\) số nguyên \(t_i\) và \(m_i\) (\(0 \le t_i \le T\); \(m_i \in \{1, 2\}\)). Các \(t_i\) được cho theo thứ tự tăng dần.
• \(Q\) dòng tiếp theo, mỗi dòng chứa \(2\) số nguyên \(L, R\) (\(0 \le L < R \le T\)).

Output

• Gồm \(Q\) dòng, mỗi dòng chứa một số nguyên duy nhất là quãng đường tương ứng với truy vấn.

Example

3 10 2 3 7
1 2
4 1
7 2
0 6
3 10

30
37

Scoring

• \(25\%\) số test: \(a = b\).
• \(25\%\) số test: \(n, Q \le 1000\).
• \(50\%\) số test: không có ràng buộc gì thêm.