Tuyển sinh lớp 10 Chuyên tỉnh Hưng Yên 2026

Một công ty sản xuất nội thất có \(n\) đội, đội thứ \(i\) đang cần các đoạn gỗ độ dài \(a_i\) để lắp ghép. Công ty sẽ đặt hàng các thanh gỗ dài cùng kích thước để có thể phù hợp với tất cả các đội.

Thanh gỗ dài phù hợp với đội \(i\) nếu có thể cắt thanh gỗ dài đó thành các đoạn có độ dài bằng \(a_i\) để sử dụng mà không thừa bất cứ khúc nào. Để dễ dàng vận chuyển, giám đốc công ty muốn độ dài thanh gỗ đặt hàng về là ngắn nhất có thể.

Yêu cầu: Cho biết \(n\) và các giá trị \(a_1, a_2, \dots, a_n\). Hãy tính độ dài ngắn nhất của thanh gỗ phù hợp với tất cả các đội được công ty đặt hàng về.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(2 \le n \le 6\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(a_i \le 1000\) với mọi \(i = 1, 2, \dots, n\)).

Output

• Một số nguyên duy nhất là độ dài thanh gỗ ngắn nhất tìm được.

Example

2
5 6

30

3
2 10 4

20

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n = 2\) và \(a_i \le 2\).
• Subtask \(2\) (\(40\%\) số điểm): \(n \le 3\).
• Subtask \(3\) (\(20\%\) số điểm): Không có ràng buộc bổ sung.

Tam rất thích các số nguyên dương chia hết cho \(3\) hoặc có tận cùng bằng \(3\). Vinh là bạn thân của Tam, Vinh thích tính toán và đã đưa ra \(q\) câu hỏi. Với câu hỏi thứ \(i\) là hai số nguyên \(L_i, R_i\) (\(1 \le i \le q, 1 \le L_i \le R_i \le 10^6\)). Vinh muốn biết có bao nhiêu số mà Tam thích trong đoạn \([L_i, R_i]\).

Input

• Dòng đầu tiên chứa số nguyên dương \(q\).
• \(q\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le q\)) chứa hai số nguyên dương \(L_i, R_i\) tương ứng câu hỏi thứ \(i\) mà Vinh đưa ra cho Tam.

Output

• Ghi ra \(q\) dòng, dòng thứ \(i\) là số lượng số mà Tam thích trong đoạn \([L_i, R_i]\).

Constraints

• \(1 \le L_i \le R_i \le 10^6\)
• Subtask \(1\) (\(20\%\) số điểm): \(q = 1\).
• Subtask \(2\) (\(20\%\) số điểm): \(1 < q \le 10\).
• Subtask \(3\) (\(60\%\) số điểm): \(10 < q \le 10^5\).

Example

1
4 15

5

3
2 12
8 14
16 17

4
3
0

Một khu du lịch sinh thái tổ chức chuỗi sự kiện trải nghiệm kéo dài \(n\) ngày. Mỗi ngày ở khu du lịch sẽ có một hoạt động đặc sắc mang lại sự hài lòng lớn cho du khách. Theo kế hoạch, Ban quản lý dự kiến tổ chức đúng \(n\) hoạt động, mỗi hoạt động diễn ra trong đúng \(1\) ngày và không có ngày nào có \(2\) hoạt động cùng diễn ra. Theo tính toán, hoạt động thứ \(i\) có độ hấp dẫn là \(a_i\) (\(1 \le i \le n\)).

Gồm \(m\) đoàn khách đã đăng kí, đoàn thứ \(j\) (\(1 \le j \le m\)) từ ngày \(L_j\) đến hết ngày \(R_j\). Để các đoàn khách có trải nghiệm tốt nhất, Ban quản lý quyết định sắp xếp lại thứ tự các hoạt động để có tổng hiệu quả hài lòng của tất cả các đoàn đăng kí là lớn nhất. Biết hiệu quả hài lòng của mỗi đoàn khách là tổng độ hấp dẫn của các hoạt động diễn ra trong thời gian đoàn khách đó lưu trú.

Yêu cầu: Hãy xác định tổng hiệu quả hài lòng lớn nhất có thể đạt được.

Input

• Dòng đầu tiên chứa \(2\) số nguyên \(n\) và \(m\) (\(1 \le n, m \le 3 \cdot 10^5\)).
• Dòng thứ \(2\) chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^6, \forall i = 1, 2, \dots, n\)).
• Dòng thứ \(j\) trong \(m\) dòng tiếp theo chứa \(2\) số nguyên \(L_j, R_j\) (\(1 \le L_j \le R_j \le n, \forall j = 1, 2, \dots, m\)).

Output

• Ghi ra một số nguyên là tổng hiệu quả hài lòng lớn nhất có thể đạt được.

Example

3 2
70 30 10
1 2
2 3

180

3 3
10 70 30
1 3
1 2
1 1

280

Scoring

• Subtask \(1\) (\(0.3\) điểm): \(m = 1; n \le 3 \cdot 10^5; a_1 \le a_2 \le \dots \le a_n\).
• Subtask \(2\) (\(0.4\) điểm): \(m \le 100; n \le 3 \cdot 10^5; L_j = 1, \forall j = 1, 2, \dots, m\).
• Subtask \(3\) (\(0.5\) điểm): \(m \le 100; n \le 3 \cdot 10^5\).
• Subtask \(4\) (\(0.8\) điểm): Không có ràng buộc bổ sung.

Số Fibonacci được định nghĩa là: \(F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}\) với mọi \(n > 1\).

Cho xâu \(S\) có độ dài không vượt quá \(10^6\) gồm các kí tự chữ cái và kí tự chữ số. Các số trong xâu \(S\) là một dãy các kí tự chữ số liên tiếp được phân tách bởi các kí tự chữ cái.

Sau khi thực hiện lấy ra các số trong \(S\), ta thu được một dãy số \(A\) gồm \(m\) số nguyên dương \(a_1, a_2, \dots, a_m\). Ví dụ, xâu \(S =\) ab123cd67e15g67, ta có dãy số \(A = [123, 67, 15, 67]\). Chú ý rằng các số \(1, 12, 2, 23, 3, 6, 7, 1, 5\) không được tính là tồn tại trong dãy \(A\).

Yêu cầu: Cho biết tất cả các phần tử trong dãy \(A\) luôn có giá trị không vượt quá \(10^{18}\). Hãy đếm số lượng phần tử trong dãy \(A\) là số Fibonacci.

Input

• Một dòng duy nhất chứa xâu \(S\) có độ dài không vượt quá \(10^6\).

Output

• Một số nguyên duy nhất là số lượng phần tử trong dãy \(A\) là số Fibonacci.

Example

ab14def2cd1ag6bc2h13

4

Scoring

• Subtask \(1\) (\(0.5\) điểm): Các số trong dãy \(A\) đều có \(1\) chữ số.
• Subtask \(2\) (\(0.4\) điểm): Các số trong dãy \(A\) có \(1\) hoặc \(2\) chữ số.
• Subtask \(3\) (\(1.1\) điểm): Không có ràng buộc bổ sung.

Một dãy phố nằm trên một trục đường thẳng có \(n\) ngôi nhà và \(m\) trạm tín hiệu dùng để phát thông tin nội bộ cho cả dãy phố. Ngôi nhà thứ \(i\) (\(1 \le i \le n\)) ở vị trí \(a_i\) và trạm tín hiệu thứ \(j\) (\(1 \le j \le m\)) đặt ở vị trí \(b_j\).

Một trạm có cường độ tín hiệu là \(x\) (\(x > 0\)) sẽ phát tín hiệu đến tất cả các ngôi nhà có khoảng cách đến trạm đó không quá \(x\). Tức là trạm thứ \(j\) có thể cung cấp thông tin cho ngôi nhà thứ \(i\) nếu \(|a_i - b_j| \le x\). Tất cả các trạm đều được thiết lập cùng một cường độ tín hiệu. Vì cường độ tín hiệu càng lớn thì chi phí vận hành càng cao nên đơn vị quản lý muốn điều chỉnh cường độ tín hiệu nhỏ nhất có thể mà vẫn đảm bảo tất cả các ngôi nhà đều nhận được tín hiệu.

Yêu cầu: Hãy giúp đơn vị quản lý tìm cường độ tín hiệu \(x\) nhỏ nhất cho các trạm.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, m\) (\(1 \le n, m \le 10^5\)).
• Dòng thứ hai chứa dãy số tự nhiên \(a_1, a_2, \dots, a_n\) (\(a_1 < a_2 < a_3 < \dots < a_n \le 10^9\)).
• Dòng thứ ba chứa dãy số tự nhiên \(b_1, b_2, \dots, b_m\) (\(b_1 < b_2 < b_3 < \dots < b_m \le 10^9\)).
• Dữ liệu đảm bảo \(a_i \neq b_j\) với mọi \(1 \le i \le n, 1 \le j \le m\).

Output

• Đưa ra một số nguyên dương \(x\) nhỏ nhất tìm được.

Example

5 3
1 5 10 14 17
4 11 15

3

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(m = 1; n \le 100\).
• Subtask \(2\) (\(70\%\) số điểm): \(m, n \le 100; a_n \le 1000; b_m \le 1000\).
• Subtask \(3\) (\(90\%\) số điểm): Không có ràng buộc bổ sung.