HSG THPT - TP. Hải Phòng 2026

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 9

Cho xâu kí tự chỉ gồm các chữ cái Latin viết thường ~'a' \ldots 'z'~ và chữ số ~'0' \ldots '9'~. Biết rằng xâu đảo ngược của một xâu là chuỗi các kí tự của xâu gốc nhưng viết theo thứ tự ngược lại từ phải qua trái, ví dụ xâu đảo ngược của xâu ′abcd′ là ′dcba′.

Tính tổng các chữ số có trong xâu kí tự và in ra xâu đảo ngược của xâu đã cho nhưng không bao gồm các kí tự chữ số.

Dữ liệu vào

Dòng 1: Chứa một xâu kí tự có độ dài không quá ~10^5~.

Kết quả

Dòng 1: Tổng các chữ số có trong xâu kí tự. Dòng 2: Xâu đảo ngược của xâu đã cho không bao gồm các kí tự chữ số. Nếu không tồn tại xâu đảo ngược thì ghi ra −1.

Ví dụ

Input 1

12340

Output 1

10
-1

Input 2

a12b3c

Output 2

6
cba

Ràng buộc

  • Subtask 1 (50% số điểm): Xâu chỉ có kí tự chữ số ~'0' \ldots '9'~.
  • Subtask 2 (50% số điểm): Không có ràng buộc nào thêm.

Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).


Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 24

Số ~P~ được gọi là nguyên tố đặc biệt nếu ~P~ là số nguyên tố và tổng các chữ số của nó cũng là số nguyên tố. Ví dụ: 2, 3, 23, 29 là các số nguyên tố đặc biệt.

Cho dãy ~A~ có ~n~ số nguyên dương ~\{a_1, a_2, \ldots, a_n\}~. Đếm số lượng số nguyên tố đặc biệt trong dãy ~A~.

Dữ liệu vào

Gồm hai dòng:

  • Dòng 1: Chứa số nguyên dương ~n (n \le 10^6)~.
  • Dòng 2: Chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n (a_i \le 10^6)~.

Kết quả

Một dòng duy nhất là số lượng các số nguyên tố đặc biệt.

Ví dụ

Input 1

6
2 3 19 23 29 17

Output 1

4

Các số 2, 3, 23, 29 thoả mãn; 19 có tổng chữ số 10 không nguyên tố; 17 có tổng chữ số 8 không nguyên tố.

Ràng buộc

  • Subtask 1 (30% số điểm): ~n \le 10^2~.
  • Subtask 2 (40% số điểm): ~n \le 10^4~.
  • Subtask 3 (30% số điểm): Không có ràng buộc nào thêm.

Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).


Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 26

Cho số nguyên dương ~S~ và ma trận ~A~ có ~m~ hàng, ~n~ cột. Ô giao giữa hàng ~i (i = 1 \ldots m)~ và cột ~j (j = 1 \ldots n)~ có số nguyên dương ~a_{ij} (a_{ij} \le 10^9)~.

Tìm tổng lớn nhất của 2 phần tử ở 2 vị trí khác nhau trong ma trận ~A~ sao cho tổng này không lớn hơn số nguyên dương ~S~. Nếu không tìm được 2 phần tử theo yêu cầu thì in ra −1.

Dữ liệu vào

Gồm các dòng:

  • Dòng 1: Chứa 3 số nguyên dương ~m, n, S (m, n \le 10^3; S \le 2 \times 10^9)~.
  • ~m~ dòng tiếp theo, mỗi dòng có ~n~ số nguyên dương không vượt quá ~10^9~.

Kết quả

Một dòng duy nhất là tổng lớn nhất tìm được theo yêu cầu. Nếu không tìm được thì in ra −1.

Ví dụ

Input 1

1 4 17
1 9 7 11

Output 1

16

Input 2

2 4 7
1 2 2 3
3 3 7 2

Output 2

6

Input 3

3 4 10
6 7 8 9
5 6 7 8
9 8 8 7

Output 3

-1

Ràng buộc

  • Subtask 1 (20% số điểm): ~m = 1~.
  • Subtask 2 (30% số điểm): ~m, n \le 10^2~.
  • Subtask 3 (50% số điểm): Không có ràng buộc nào thêm.

Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).


Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 24

Cho xâu kí tự ~S~ có ~n~ kí tự chữ cái Latin viết in hoa ~'A' \ldots 'Z'~. Có ~q~ lệnh xóa kí tự, mỗi lệnh xóa thuộc một trong 2 loại sau đây:

• Loại 0: Xóa 1 kí tự đầu tiên (tính từ trái qua phải) có thứ tự từ điển nhỏ nhất của xâu còn lại.

• Loại 1: Xóa 1 kí tự đầu tiên (tính từ trái qua phải) có thứ tự từ điển lớn nhất của xâu còn lại.

Tìm xâu kí tự còn lại sau khi thực hiện tuần tự ~q~ lệnh xóa.

Dữ liệu vào

Gồm ba dòng:

  • Dòng 1: Chứa 2 số nguyên dương ~n, q (n \le 2 \times 10^5; q \le 10^5)~.
  • Dòng 2: Chứa xâu kí tự ~S~ chỉ có kí tự chữ cái Latin viết in hoa ~'A' \ldots 'Z'~.
  • Dòng 3: Chứa ~q~ số, mỗi số là 0 hoặc 1 tương ứng thể hiện loại lệnh xóa.

Kết quả

Một dòng duy nhất là xâu kí tự còn lại sau khi thực hiện tuần tự ~q~ lệnh xóa.

Ví dụ

Input 1

10 4
ADBAACDABC
0 1 1 0

Output 1

BACABC

Lần 1 (loại 0): ADBAACDABC → DBAACDABC (xóa ~A~ đầu tiên - nhỏ nhất). Lần 2 (loại 1): DBAACDABC → BAACDABC (xóa ~D~ đầu tiên - lớn nhất). Lần 3 (loại 1): BAACDABC → BAACABC (xóa ~D -~ lớn nhất). Lần 4 (loại 0): BAACABC → BACABC (xóa ~A~ đầu tiên - nhỏ nhất).

Ràng buộc

  • Subtask 1 (10% số điểm): ~q = 1~.
  • Subtask 2 (40% số điểm): ~n \le 10^4; q \le 10^3~.
  • Subtask 3 (50% số điểm): Không có ràng buộc nào thêm.

Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).


Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 51

Cho mảng ~A~ có ~n~ số nguyên dương ~\{a_1, a_2, \ldots, a_n\}~.

Với mỗi số nguyên dương ~a_i~, tìm số nguyên dương ~a_j (j > i)~ với ~j~ nhỏ nhất thỏa mãn ~a_j~ có nhiều ước hơn ~a_i~; nếu không có số ~a_j~ thỏa mãn thì kết quả tìm kiếm là −1.

Dữ liệu vào

Gồm hai dòng (dữ liệu đảm bảo ~max\{a_i\} - min\{a_i\} \le 10^6~):

  • Dòng 1: Chứa số nguyên dương ~n (n \le 2 \times 10^5)~.
  • Dòng 2: Chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n (a_i \le 10^6)~.

Kết quả

Một dòng có ~n~ số nguyên theo thứ tự là kết quả tìm kiếm theo yêu cầu.

Ví dụ

Input 1

6
6 18 7 10 9 8

Output 1

18 -1 10 -1 8 -1

Số ước tương ứng của các số là 4, 6, 2, 4, 3, 4. Với ~a_1 = 6 (4~ ước), số đầu tiên bên phải có nhiều ước hơn là 18 (6 ước). Với ~a_2 = 18~ không có số nào bên phải nhiều ước hơn 6 nên kết quả −1. Tương tự cho các phần tử còn lại.

Ràng buộc

  • Subtask 1 (20% số điểm): ~n \le 10^3~ và ~a_i \le 10^4~.
  • Subtask 2 (50% số điểm): ~n > 10^3~ và ~a_i \le 10^6~.
  • Subtask 3 (30% số điểm): Không có ràng buộc nào thêm.

Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).