Đề TS 10 LQĐ Đà Nẵng 2026

Một số nguyên dương \(x\) được gọi là số nguyên tố đẹp nếu thỏa mãn đồng thời 3 điều kiện sau:

• \(x\) là số nguyên tố;
• Lần lượt bỏ đi các chữ số bên phải của số \(x\) thì phần còn lại của nó vẫn là số nguyên tố;
• Thêm vào bên phải của số \(x\) một chữ số bất kì thì số thu được cũng là số nguyên tố.

Ví dụ số \(313\) là số nguyên tố đẹp, vì:

• Số \(313\) là số nguyên tố;
• Bỏ chữ số \(3\) được số \(31\) là số nguyên tố, bỏ tiếp chữ số \(1\) ta còn số \(3\) cũng là số nguyên tố;
• Thêm số \(7\) vào sau số \(313\) ta được số \(3137\) cũng là số nguyên tố.

Yêu cầu: Cho dãy \(a\) gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^6, 1 \le i \le n\)) và \(m\) truy vấn. Mỗi truy vấn có dạng \((u, v)\) với ý nghĩa: đếm số lượng số nguyên tố đẹp trong dãy \(a\) từ vị trí \(u\) tới \(v\).

Input

• Dòng thứ nhất chứa số nguyên dương \(n\) (\(1 \le n \le 10^5\));
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^6, 1 \le i \le n\));
• Dòng thứ ba chứa số nguyên dương \(m\) là số lượng truy vấn (\(1 \le m \le 10^5\));
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v\) (\(1 \le u \le v \le n\)).

Output

• Ghi ra \(m\) dòng, mỗi dòng theo thứ tự của truy vấn ghi ra số lượng số nguyên tố đẹp tìm được.

Example

6
59 12 57 53 23 313
3
1 3
2 5
3 6

1
1
2

Scoring

• Có \(70\%\) số điểm thỏa mãn: \(1 \le a_i \le 10^3, 1 \le n \le 10^3, 1 \le m \le 10^3\).
• Có \(30\%\) số điểm còn lại: Không có ràng buộc gì thêm.

Một nhóm kĩ sư phần mềm Z đang thử nghiệm ứng dụng gợi ý nhắn tin trên điện thoại với một bộ danh mục gồm \(n\) từ vựng, mỗi từ là một xâu chỉ gồm các kí tự latin in thường (từ a đến z). Khi người dùng nhập vào một từ \(W\) (cũng chỉ gồm các kí tự latin in thường), ứng dụng gợi ý sẽ liệt kê tất cả các từ vựng trong danh mục nhận \(W\) làm tiền tố để người dùng có thể nhanh chóng lựa chọn.

Một xâu \(A\) được gọi là tiền tố của xâu \(B\) nếu phần đầu của xâu \(B\) khớp với toàn bộ xâu \(A\), ví dụ: Xâu danang có các tiền tố là d, da, dan, dana, danan và danang.

Yêu cầu: Cho danh mục \(n\) từ vựng và \(m\) câu hỏi, câu hỏi thứ \(i\) có dạng \(k_i\) và từ \(W_i\). Hãy tìm từ vựng thứ \(k\) theo thứ tự từ điển mà ứng dụng sẽ gợi ý khi người dùng nhập vào từ \(W\) và in ra chỉ số của từ vựng đó trong danh mục (chỉ số danh mục được đánh từ \(1\) đến \(n\)).

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n\) và \(m\);
• Mỗi dòng trong \(n\) dòng tiếp theo chứa một từ vựng trong danh mục;
• Dòng thứ \(i\) trong \(m\) dòng tiếp theo chứa số nguyên dương \(k_i\) và từ \(W_i\) thể hiện một câu hỏi (\(|W_i| \le 1000\)).

Output

• Ghi ra \(m\) dòng, dòng thứ \(i\) chứa một số nguyên là câu trả lời cho câu hỏi thứ \(i\), hoặc số nguyên \(-1\) nếu không tồn tại một xâu như vậy.

Example

10 3
dab
ba
ab
daa
aa
aaa
aab
abc
ac
dadba
4 a
2 da
4 da

3
1
-1

Ràng buộc

• Có \(50\%\) số test ứng với \(50\%\) số điểm thoả mãn: \(n \le 3000, m \le 300\) và các từ có độ dài không quá \(50\);
• Có \(50\%\) số test còn lại ứng với \(50\%\) số điểm thoả mãn: \(n \le 3000, m \le 10000\) và tổng độ dài các từ không vượt quá \(10^6\).

Trong lộ trình xây dựng Đà Nẵng trở thành "Thành phố thông minh", thành phố triển khai một hệ thống camera AI để quản lý và tối ưu hóa dòng chảy giao thông tại các tuyến đường huyết mạch như Trần Phú, Bạch Đằng, Lê Duẩn...

Hệ thống ghi nhận lưu lượng xe tại \(n\) điểm kiểm soát liên tiếp, tạo thành một dãy số nguyên dương \(a_1, a_2, \dots, a_n\). Vào những giờ cao điểm, việc tính toán lưu lượng và phân phối cho các phương tiện giao thông là một trong những nhiệm vụ hết sức cần thiết đối với trung tâm điều hành.

Yêu cầu: Cho \(n\) điểm kiểm soát \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9, 1 \le i \le n\)), điểm thứ \(i\) có lưu lượng \(a_i\) xe. Hãy tính tổng lưu lượng xe lớn nhất của \(n\) điểm kiểm soát trên nhưng phải thoả điều kiện không lấy \(3\) điểm liên tiếp.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 10^6\)) là số điểm kiểm soát.
• Dòng thứ \(2\) chứa \(n\) số nguyên \(a_i\) là lưu lượng xe tại điểm kiểm soát thứ \(i\) (\(1 \le a_i \le 10^9\)).

Output

• Ghi ra một số nguyên là giá trị lớn nhất tìm được.

Example

4
9 3 5 4

18

6
6 10 13 9 8 1

33

Scoring

• Có \(30\%\) số tests ứng với \(30\%\) số điểm thoả mãn: \(1 \le n \le 100; 1 \le a_i \le 10^5\).
• Có \(30\%\) số tests ứng với \(30\%\) số điểm thoả mãn: \(100 < n \le 10^5; 1 \le a_i \le 10^4\).
• Có \(40\%\) số tests ứng với \(40\%\) số điểm thoả mãn: \(10^5 < n \le 10^6; 10^4 < a_i \le 10^9\).

Để chuẩn bị cho đêm hội ánh sáng bên bờ sông Hàn, Ban Tổ chức huy động một đoàn gồm \(n\) du khách quốc tế tham gia diễu hành trên các xe điện du lịch. Ban Tổ chức cần phân chia \(n\) du khách này vào các xe điện khác nhau. Để đảm bảo an toàn và quy định tổ chức, mỗi xe điện phải chở ít nhất một hành khách.

Mỗi xe điện sau khi nhận đủ hành khách sẽ được kích hoạt một hệ thống đèn LED nghệ thuật tự động. Để tạo sự độc đáo và ấn tượng, chu kì tự động đổi màu đèn (tính bằng giây) của mỗi xe được cài đặt bằng đúng số lượng hành khách ngồi trên xe đó. Ví dụ xe chở \(3\) khách thì cứ đúng \(3\) giây hệ thống đèn của xe đó lại tự động đổi màu một lần.

Đêm hội diễu hành sẽ đạt đến khoảnh khắc bùng nổ, mãn nhãn nhất khi tất cả các xe điện đồng loạt đổi màu đèn cùng lúc, tạo nên hiệu ứng ánh sáng khổng lồ lan tỏa dọc khắp tuyến phố đi bộ Bạch Đằng. Ban Tổ chức muốn khoảng thời gian từ lúc đoàn xe xuất phát cho đến lần đầu tiên tất cả các xe cùng kích hoạt đổi màu đèn đồng bộ phải là lâu nhất có thể, nhằm kéo dài sự tò mò và tạo sự phấn khích cho khán giả.

Yêu cầu: Hãy giúp Ban Tổ chức tìm phương án phân chia \(n\) du khách vào các xe điện sao cho khoảng thời gian chờ đến lúc tất cả các xe cùng đổi màu đèn đồng loạt lần đầu tiên là lớn nhất.

Input

• Một dòng duy nhất chứa một số nguyên dương \(n\) là tổng số lượng du khách quốc tế tham gia diễu hành.

Output

• Ghi ra hai dòng:
  • Dòng thứ nhất ghi một số nguyên duy nhất là khoảng thời gian lớn nhất (tính bằng giây) mà khán giả phải chờ để chứng kiến tất cả các xe đổi màu đồng loạt lần đầu tiên.
  • Dòng thứ hai ghi số lượng hành khách trên mỗi xe điện được phân chia, các số cách nhau bởi một khoảng trắng và được in theo thứ tự tăng dần. Nếu có nhiều phương án cho cùng một kết quả tối ưu, hãy in ra phương án sử dụng ít xe điện nhất.

Example

14

84
3 4 7

45

60060
2 3 4 5 7 11 13

Constraints

• Có \(30\%\) số điểm thỏa mãn: \(1 \le n \le 30\);
• Có \(40\%\) số điểm thỏa mãn: \(31 \le n \le 70\);
• Có \(30\%\) số điểm thỏa mãn: \(71 \le n \le 100\).