Sau khi sát nhập, tỉnh Thái Nguyên đã có thêm rất nhiều địa điểm tham quan du lịch đẹp và nổi tiếng, để chuẩn bị cho chuyến đi du lịch đến các địa điểm nổi tiếng đó bằng ô tô điện cỡ nhỏ, gia đình bạn Bon đang nghiên cứu bản đồ các trạm sạc. Dọc theo tuyến đường đi, hệ thống dẫn đường hiển thị N trạm sạc. Trạm thứ i cách điểm xuất phát một khoảng cách là Ai (km).

Để lên kề hoạch dừng nghỉ hợp lý với dung lượng pin của xe, phần mềm hỗ trợ cần thống kê các cặp trạm sạc có tổng khoảng cách tính từ điểm xuất phát đúng bằng một mức giới hạn S (km) đã được cài đặt trước. Hãy lập trình giúp gia đình Bon đếm số lượng cặp trạm sạc (i, j) với 1 ≤ i ≤ j ≤ N sao cho Ai + Aj = S.

Dữ liệu: đọc từ bàn phím (thiết bị vào chuẩn), gồm:

• Dòng đầu tiên chứa hai số nguyên dương N và S tương ứng với số lượng trạm sạc và mức giới hạn S.

• Dòng thứ hai chứa N số nguyên dương A1,A2, ...,AN. Các số cách nhau một khoảng trắng là khoảng cách từ điểm xuất phát tới trạm sạc thứ i.

Kết quả: ghi ra màn hình (thiết bị ra chuẩn), một số nguyên duy nhất là số lượng căp trạm sạc thỏa mãn yêu cầu.

Ví dụ:

Input:

5 8
2 5 6 3 2

Output:

3

Giải thích:

Có 3 cặp chỉ số thỏa mãn tổng bằng 8 là:

• Vị trí 1 và 3: 2 + 6= 8

• Vị trí 2 và 4: 5 + 3 = 8

• Vị trí 3 và 5: 6 + 2 = 8

Ràng buộc:

• Subtask 1 (0.4 điểm): 40% số test thỏa mã N ≤ 10^3;S,Ai ≤ 10^5

• Subtask 2 (0.4 điểm): 40% số test thỏa mãn N ≤ 10^5 ; S, Ai ≤ 10^6

• Subtask 3 (0.2 điểm): 20% số test thỏa mãn N ≤ 10^6; S, Ai ≤ 10^9

Trong quá trình nghiên cứu một dự án khoa học kĩ thuật, một nhóm học sinh trường THPT Chuyên Thái Nguyên đã tạo ra một hệ thông trí tuệ nhân tạo (AI) mới hỗ trợ học sinh trong quá trình giải bài tập Tin học rất hiệu quả và được rất nhiều bạn học sinh mong muốn sử dụng. Nhưng để mở khóa quyền sử dụng hệ thống đó, người dùng cần phải có mật khẩu truy cập.

Màn hình đăng nhập hệ thống sẽ hiển thị một chuỗi ký tự S bao gồm các chữ cái in thường và các chữ số lộn xộn. Nhóm tác giả đã đưa ra gợi ý: "Mật khẩu chính là số nguyên tố lớn nhất được tạo thành từ các cụm chữ số liên tiếp nằm trong chuỗi S. Các số được tách ra phải được giữ nguyên, không được tách rời hay đáo lộn các chữ sô bên trong nó".

Yêu cầu: Bạn hãy viết chương trình trích xuất các số tự nhiên từ chuỗi ký tự S (bỏ qua các số 0 vô nghĩa ở đầu). Tìm và in ra số nguyên tố có giá trị lớn nhất trong các số vừa trích xuất. Nếu không tìm thấy số nguyên tố nào, in ra -1.

Dữ liệu: Đọc từ bàn phím (thiết bị vào chuẩn), một dòng duy nhất chứa chuỗi ký tự S.

Kết quả: Ghi ra màn hình (thiết bị ra chuẩn), một số nguyên duy nhất là kết quả bài toán.

Ví dụ:

Input:

phone12x07y15pro23

Output:

23

Giải thích: Các số tự nhiên tách được là: 12, 7, 15, 23. Trong đó 7 và 23 là số nguyên tố. Số lớn nhất là 23.

Ràng buộc:

• Subtask 1 (0.6 điểm): 30% số test có chiều dài chuỗi 5 ≤ 10^3; số tách ra có giá trị < 10.

• Subtask 2 (0.6 điểm): 30% số test có chiều dài chuỗi 5 ≤ 10^5; số tách ra có giá trị ≤ 10^6

• Subtask 3 (0.8 điểm): 40% số test có chiều dài chuỗi S ≤ 10^6; số tách ra có giá trị ≤ 10^7

Đêm giao thừa Tết Nguyên đán vừa qua, Quảng trường Võ Nguyên Giáp tại trung tâm tỉnh Thái Nguyên đã diễn ra sự kiện Countdown chào đón năm mới vô cùng hoành tráng. Dọc theo tuyến phố đi bộ dẫn vào khu vực sân khấu chính, có N nhóm người dân đang tập trung chờ đón khoảnh khắc chuyển giao năm mới. Nhóm thứ i đang đứng ở vị trí có tọa độ X, (tính bằng mét so với cổng chào).

Để hỗ trợ người dân dễ dàng truy cập mạng, livestream khoảnh khắc giao thừa và gửi những lời chúc tốt đẹp nhất cho người thân, Ban tổ chức quyết định triển khai K trạm phát Wifi di động cường độ cao dọc theo tuyến phố. Mỗi trạm phát khi được kích hoạt có thể phủ sóng mạng ổn định cho một đoạn đường dài tối đa D mét. Một nhóm người dân có thể nằm trong vùng phủ sóng của nhiều trạm, nhưng chỉ cần nhận được tín hiệu từ ít nhất một trạm là đã có thể kết nối mạng thành công.

Yêu cầu: Hãy tính toán cách đặt K trạm phát Wifi sao cho tổng số lượng nhóm người dân được kết nối mạng là lớn nhất.

Dữ liệu: đọc từ bàn phím (thiết bị vào chuẩn), gồm:

• Dòng đầu tiên chứa ba số nguyên dương N, K, D (Số lượng nhóm người dân, số trạm phát Wifi, khoảng cách phủ sóng của mỗi trạm).

• Dòng thứ hai chứa N số nguyên dương X1,X2, .., XN là tọa độ của các nhóm người dân. Các tọa độ này có thể chưa được sắp xếp.

Kết quả: ghi ra màn hình (thiết bị ra chuẩn), một số nguyên duy nhất là số lượng nhóm người dân nhiều nhất được kết nối mạng.

Ví dụ:

Input:

5 2 3
1 5 2 7 4

Output:

5

Tọa độ sắp xếp lại: 1, 2, 4, 5, 7. Vùng phủ sóng D = 3.

• Trạm 1 đặt để phủ sóng từ tọa độ 1 đến 4: Cung cấp mạng cho 3 nhóm ở vị trí {1,2,4).

• Trạm 2 đặt để phủ sóng từ toa độ 4 đến 7: Cung cấp mạng cho 2 nhóm ở vị trí {5, 7}.

Tổng cộng có trọn vẹn 5 nhóm người dân đều có Wifi đón giao thừa.

Ràng buộc:

• Subtask 1 (0.6 điểm): 30% số test thỏa mãn N ≤ 100; K = 1.

• Subtask 2 (0.6 điểm): 30% số test thỏa mãn N ≤ 10^5; K = 1.

• Subtask 3 (0.8 điểm): 40% số test thỏa mãn N ≤ 1000; K ≤ 50; Xi, D ≤ 10^9.