Tuyển sinh lớp 10 Chuyên thành phố Hải Phòng 2026 - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Bài 1: (TS10 Hải Phòng 2026)	2 (p)	1.0s	1G
2	Bài 2: (TS10 Hải Phòng 2026)	2 (p)	1.0s	1G
3	Bài 3: (TS10 Hải Phòng 2026)	2 (p)	1.0s	1G
4	Bài 4: (TS10 Hải Phòng 2026)	2 (p)	1.0s	1G
5	Bài 5: (TS10 Hải Phòng 2026)	2 (p)	1.0s	1G

1. Bài 1: (TS10 Hải Phòng 2026)

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

Có \(4\) địa điểm nằm trên một đường thẳng đánh số lần lượt là \(1, 2, 3, 4\) từ trái qua phải. Từ địa điểm số \(1\) có \(x\) con đường khác nhau đến địa điểm số \(2\). Từ địa điểm số \(2\) có \(y\) con đường khác nhau đến địa điểm số \(3\). Từ địa điểm số \(3\) có \(z\) con đường khác nhau đến địa điểm số \(4\). Tất cả các con đường đều là hai chiều.

Yêu cầu

Bạn hãy trả lời lần lượt \(q\) câu hỏi. Mỗi câu hỏi được cho bởi cặp số nguyên \(a, b\) thể hiện yêu cầu đếm xem có bao nhiêu cách đi khác nhau bắt đầu từ địa điểm \(a\) và kết thúc tại địa điểm \(b\) sao cho mọi địa điểm đi qua không quá \(1\) lần. Hai cách đi được gọi là khác nhau nếu như có một con đường xuất hiện trong cách đi này nhưng lại không xuất hiện trong cách đi còn lại.

Input

Dòng đầu tiên chứa \(3\) số nguyên dương \(x, y, z\) (\(1 \le x, y, z \le 1000\)).
Dòng thứ hai chứa số nguyên dương \(q\) (\(q \le 100\)) là số lượng câu hỏi.
Tiếp theo là \(q\) dòng, dòng thứ \(i\) (\(1 \le i \le q\)) chứa hai số nguyên \(a_i, b_i\) (\(1 \le a_i, b_i \le 4\)) thể hiện câu hỏi thứ \(i\) là đếm số cách đi khác nhau từ \(a_i\) đến \(b_i\).

Output

Gồm \(q\) dòng, dòng thứ \(i\) (\(1 \le i \le q\)) ghi một số nguyên là kết quả của câu hỏi thứ \(i\).

Example

Test 1

Input

Output

6
1

Note

Trong câu hỏi thứ nhất có \(1\) con đường từ địa điểm \(1\) đến địa điểm \(2\), có \(2\) con đường từ địa điểm \(2\) đến địa điểm \(3\), có \(3\) con đường từ địa điểm \(3\) đến địa điểm \(4\) do vậy số cách đi từ địa điểm \(1\) đến địa điểm \(4\) là \(1 \cdot 2 \cdot 3 = 6\).
Trong câu hỏi thứ hai chỉ có một cách đi duy nhất từ địa điểm \(2\) đến địa điểm \(2\) là không sử dụng bất kỳ con đường nào cả.

2. Bài 2: (TS10 Hải Phòng 2026)

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

Cho xâu ký tự \(S\) độ dài không quá \(10^6\) chỉ chứa các ký tự số, ký tự tiếng Anh in thường. Dãy ký tự \(S\) thoả mãn có ít nhất một ký tự số. Có thể thấy trong xâu \(S\) sẽ xuất hiện các số nguyên khác nhau. Ví dụ: xâu \(S =\) "a22b00de1" xuất hiện ba số nguyên \(22, 0, 1\).

Yêu cầu: Hãy tính tổng tất cả các số nguyên xuất hiện trong xâu \(S\).

Input

Một dòng duy nhất chứa xâu ký tự \(S\). Dữ liệu luôn đảm bảo có ít nhất một ký tự số.

Output

In ra tổng các số nguyên xuất hiện trong xâu \(S\). Do con số này có thể rất lớn nên chỉ cần lấy phần dư của nó khi chia cho \(10^9 + 7\).

Example

Test 1

Input

a22bc00de1

Output

Note

Trong xâu ký tự có \(3\) số nguyên lần lượt là \(22, 0, 1\). Do vậy kết quả là \(22 + 0 + 1 = 23\).

Ràng buộc

Có \(50\%\) số tests ứng với \(50\%\) số điểm của bài không có hai ký tự số liên tiếp.
\(30\%\) số tests tiếp theo ứng với \(30\%\) số điểm của bài có không quá \(9\) ký tự số liên tiếp.
\(20\%\) số tests còn lại không có ràng buộc bổ sung.

3. Bài 3: (TS10 Hải Phòng 2026)

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

Dãy số \(a_1, a_2, \dots, a_n\) được lập theo quy tắc sau:

\(a_1 = x, a_2 = y\)
\(a_k = (a_{k-1} + a_{k-2}) \pmod M\) với mọi \(k = 3, 4, \dots, n\)

Ở đây phép toán \(p \pmod q\) là phép lấy phần dư khi chia \(p\) cho \(q\) (phép % trong ngôn ngữ C++ và Python).

Cho số nguyên dương \(S\). Hãy tìm dãy con \(a_i, a_{i+1}, \dots, a_j\) có số lượng phần tử nhỏ nhất sao cho: \(a_i + a_{i+1} + \dots + a_j \geq S\).

Input

Một dòng duy nhất chứa 5 số nguyên \(n, x, y, M, S\) (\(2 \leq n \leq 2 \cdot 10^5\); \(1 < M \leq 10^4\); \(0 \leq x, y < M\); \(1 \leq S \leq 10^{15}\)) cách nhau bằng khoảng trống.

Output

Một số nguyên duy nhất là số lượng phần tử của dãy con tìm được. Nếu không tồn tại dãy con thoả mãn thì in \(-1\).

Example

Test 1

Input

10 1 1 7 19

Output

Note

Dãy số được tạo ra là \([1, 1, 2, 3, 5, 1, 6, 0, 6, 6]\). Dãy con ngắn nhất có tổng lớn hơn hoặc bằng \(19\) là \([1, 6, 0, 6, 6]\).

Constraints

Có \(40\%\) số tests ứng với \(40\%\) số điểm của bài có \(n \leq 300\);
\(30\%\) số tests tiếp theo ứng với \(30\%\) số điểm của bài có \(n \leq 5000\);
\(30\%\) số tests còn lại không có ràng buộc bổ sung.

4. Bài 4: (TS10 Hải Phòng 2026)

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

Hành trình khám phá du lịch của các bạn lớp 9A lần lượt đi qua \(n\) địa điểm đánh số \(1, 2, \dots, n\). Sau khi hoàn thành chuyến du lịch, lớp trưởng Dũng lấy phiếu thăm dò ý kiến cả lớp và đưa ra tổng kết: Địa điểm thứ \(i\) (\(1 \le i \le n\)) có mức độ hấp dẫn là \(a_i\) và độ khó khi di chuyển đến vị trí này là \(b_i\). Là học sinh giỏi toán nên Dũng rất thích các số nguyên tố. Vì vậy Dũng định nghĩa đoạn hành trình từ điểm \(i\) đến điểm \(j\) (\(i \le j \le n\)) là đoạn hành trình đẹp nếu như \(b_i = b_j\) và \(b_i\) là số nguyên tố. Mức độ thú vị của một đoạn hành trình đẹp là tổng mức độ thú vị của các địa điểm đi qua.

Yêu cầu: Hãy tìm mức độ thú vị lớn nhất của một đoạn hành trình đẹp.

Input

Dòng đầu tiên chứa số nguyên dương \(n\) (\(n \le 2 \cdot 10^5\)).
Tiếp theo là \(n\) dòng, dòng thứ \(i\) (\(1 \le i \le n\)) chứa hai số nguyên \(a_i, b_i\) lần lượt là mức độ thú vị và độ khó khi di chuyển đến địa điểm \(i\) (\(|a_i| \le 10^9; 1 \le b_i \le 10^5\)).

Hai số liên tiếp nhau trên cùng một dòng cách nhau bằng khoảng trống.

Output

Một số nguyên duy nhất là mức độ thú vị lớn nhất của một đoạn hành trình đẹp. Nếu không tồn tại đoạn hành trình đẹp nào ghi KHONG.

Example

Test 1

Input

Output

Note

Đoạn đẹp là \([1, 1]\) có độ thú vị là \(2\); đoạn đẹp \([1, 2]\) có độ thú vị là \(2 + (-3) = -1\); đoạn đẹp \([1, 7]\) có độ thú vị là \(2 + (-3) + 0 + 4 + 10 + 0 + 1 = 14\); đoạn đẹp \([2, 2]\) có độ thú vị là \(-3\); đoạn đẹp \([2, 7]\) có độ thú vị là \((-3) + 0 + 4 + 10 + 0 + 1 = 12\); đoạn đẹp \([4, 4]\) có độ thú vị là \(4\); đoạn đẹp \([4, 5]\) có độ thú vị là \(4 + 10 = 14\); đoạn đẹp \([5, 5]\) có độ thú vị là \(10\); đoạn đẹp \([7, 7]\) có độ thú vị là \(1\). Do vậy giá trị lớn nhất tìm được là \(14\).

Scoring

40% số tests ứng với 40% số điểm của bài có \(n \le 1000\).
30% số tests tiếp theo ứng với 30% số điểm của bài có \(b_i = 3\) với mọi \(i = 1, 2, \dots, n\).
30% số tests còn lại không có ràng buộc bổ sung.

5. Bài 5: (TS10 Hải Phòng 2026)

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

Dọc theo một con đường Quốc lộ có \(n\) địa điểm dân cư. Để đơn giản ta có thể coi các địa điểm này như là các điểm trên trục tọa độ \(Ox\) với các hoành độ lần lượt là \(x_1, x_2, \dots, x_n\).

Công ty viễn thông ABC có kế hoạch lắp \(k\) trạm BTS tại các vị trí trên đường (mỗi vị trí có thể xem như là một điểm trên trục tọa độ) với "bán kính phủ sóng" đều bằng số nguyên dương \(R\). Nếu một trạm BTS được đặt tại vị trí có hoành độ \(x\) thì nó có thể phủ sóng cho tất cả các điểm dân cư có vị trí nằm trong đoạn \([x - R, x + R]\).

Yêu cầu: Tìm giá trị \(R\) nhỏ nhất để có thể bố trí cách lắp đặt \(k\) trạm BTS sao cho mỗi điểm dân cư đều nằm trong vùng phủ sóng của ít nhất một trạm.

Input

Dòng đầu tiên chứa hai số nguyên dương \(n, k\) (\(1 \le k \le n \le 10^5\)).
Dòng thứ hai chứa \(n\) số nguyên \(x_1, x_2, \dots, x_n\) (\(|x_i| \le 10^9; x_i \neq x_j\)).
Hai số liên tiếp trên cùng một dòng cách nhau bằng khoảng trống.

Output

Một số nguyên dương duy nhất là giá trị nhỏ nhất của \(R\) tìm được.

Example

Test 1

Input

4 2
1 3 8 12

Output

Note

Với bán kính phủ sóng \(R = 2\) một phương án đặt \(2\) trạm BTS hợp lệ là đặt tại các điểm có hoành độ \(3, 10\). Ngoài ra không có cách nào đặt \(2\) trạm BTS có bán kính phủ sóng \(R = 1\) phủ sóng toàn bộ \(4\) điểm dân cư.

Scoring

Có \(25\%\) số tests ứng với \(25\%\) số điểm của bài có \(k = 1\).
\(25\%\) số tests tiếp theo ứng với \(25\%\) số điểm của bài có \(k = 2\).
\(25\%\) số tests tiếp theo ứng với \(25\%\) số điểm của bài có \(n \le 300\).
\(25\%\) số tests còn lại không có ràng buộc bổ sung.