Giao lưu Tin học trẻ Mở rộng Bảng B - Lần 2 - 2023

Thiên nhiên trân quý ban tặng cho chúng ta mạng sống, chúng ta có quyền được sống và quyền tự do làm những điều mình thích. Nhưng gần đây người của hành tinh Sao Hỏa đang tiến về Trái Đất để đánh cắp lõi Trái Đất, rất may Irene đã phát hiện và chuẩn bị kế hoạch phục kích.

Địa hình lúc đó có \(N\) hành tinh không tính Trái Đất, hành tinh thứ \(i\) cách Trái Đất \(x_i\) km về bên trái. Tương ứng với mỗi hành tinh đều có một thiết bị bắn tỉa. Thiết bị bắn tỉa ở hành tinh \(A\) có thể bắn đến hành tinh \(B\) khi và chỉ khi \(x_A \ge x_B\).

Người Sao Hỏa rất thông minh bọn chúng cùng với phi thuyền đang trốn ở một hành tinh trong \(N\) hành tinh để không bị phát hiện. Vì hòa bình và sự sống của Trái Đất, Irene quyết tâm tìm và phá hủy phi thuyền của người Sao Hỏa dù có hy sinh mạng sống của mình.

Biết rằng phi thuyền chỉ có thể phá hủy bằng thiết bị bắn tỉa nhưng Irene không biết mình nên phục kích ở hành tinh nào. Là một lập trình viên, vệ tinh có thể cung cấp khoảng cách của \(N\) hành tinh so với Trái Đất hãy giúp Irene tìm ra nơi phục kích lí tưởng nhất.

Input

• Dòng đầu tiên: Chứa duy nhất một số nguyên dương \(N\) là số lượng hành tinh \((1 \le N \le 10^6)\).

• Dòng tiếp theo: Chứa \(N\) số nguyên dương \(x_i\) là khoảng cách của hành tinh thứ i so với Trái Đất \((1 \le x_i \le 10^9)\).

• Dữ liệu đảm bảo không có hai hành tinh nào đồng thời bắn được nhau.

Output

• Gồm \(1\) số nguyên là khoảng cách của hành tinh được cho là nơi phục kích lí tưởng nhất so với Trái Đất.

Example

5
234 1 4 3 75

234

Ngọc Anh vừa tốt nghiệp một khóa học kiến trúc và ngay lập tức, cô ấy được giao một công việc thiết kế một ngôi nhà. Ngôi nhà đã hoàn thiện, nhưng vốn là một người yêu Toán học nên Ngọc Anh đã cố tình thiết kế cầu thang với các bậc thang có chênh lệch độ cao giữa hai bậc thang khác nhau.

Biết cầu thang có tổng cộng \(n\) bậc thang, bậc thang thứ \(i\) có cao hơn bậc thang thứ \(i-1\) một khoảng \(a_{i}\) đơn vị độ dài. Ngọc Anh đặt ra một câu hỏi: Giả sử bước chân của một người chỉ có thể leo lên bậc thang kế tiếp nếu chênh lệch giữa bậc thang kế tiếp và bậc thang hiện tại không quá \(t\), hỏi người đó có thể leo được tối đa bao nhiêu bậc thang?

Để tính cho cả nhà gia chủ, Ngọc Anh sẽ cần tính bậc thang tối đa có thể leo cho từng người một. Việc này khá tốn thời gian, nên Ngọc Anh đã nhờ Hải "dớ" xử lí hộ Ngọc Anh vấn đề này để Ngọc Anh có thể đi thiết kế những ngôi nhà khác.

Yêu cầu: Với mỗi người, xác định số bậc thang tối đa họ có thể leo?

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n,m\) (\(n,m \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1}, a_{2},..., a_{n}\) (\(a_{i} \le 10^9\)).
• Dòng thứ ba chứa \(m\) số nguyên \(t\) (\(t \le 10^9\)).

Output

• Với mỗi người, in ra trên một dòng là số bậc thang tối đa họ có thể leo.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(m \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(a_{1} \le a_{2} \le a_{3} \le ... \le a_{n}\).
• Subtask \(3\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

Example

5 2
1 2 2 4 5
2 4

3
4

Cho mảng \(A\) gồm \(N\) số nguyên dương.

Yêu cầu: Hãy in ra tổng tất cả các cặp \((A_i \times A_j)\) với mọi cặp \((i,j)\) thỏa mãn \(1\le i<j\le N\) , chia lấy dư cho \(({10}^9+7)\). Hay nói cách khác: tổng tất cả các cặp tích của mảng.

Input

• Dòng đầu tiên nhập số nguyên dương \(N\) \((2\le N\le2\times{10}^5)\).
• Dòng còn lại nhập \(N\) số tiếp theo – là các phần tử của mảng \((1\le A_i\le{10}^9)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài sau khi chia lấy dư cho \(({10}^9+7)\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): Có \(N\le{10}^3\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
1 2 3

11

Cho hai mảng \(A\) và \(B\) cùng có \(N\) phần tử , mảng \(A\) gồm \(a_1,a_2,a_3,\ldots,a_N\) và mảng \(B\) gồm \(b_1,b_2,b_3,\ldots,b_N\).

Yêu cầu: Hãy tính \(\left(a_1^{b_1}+a_2^{b_2}+a_3^{b_3}+\ldots+a_N^{b_N}\right)\ mod\ {10}^9\).

Input

• Dòng một là số nguyên dương \(N\) duy nhất \((1 \le N\le{10}^5)\).
• Dòng thứ hai là \(N\) phần tử của mảng \(A\), mỗi số cách nhau một khoảng trắng \((1 \le {a}_i\le{10}^5)\).
• Dòng thứ ba là \(N\) phần tử của mảng \(B\), mỗi số cách nhau một khoảng trắng \((1 \le {b}_i\le{10}^5)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(25\%\) số điểm) : Có \(N = 1\) và \(a_i,b_i \le 8\).
• Subtask \(2\) (\(25\%\) số điểm) : Có \(b_i \le 100\).
• Subtask \(3\) (\(25\%\) số điểm) : Có \(a_1=a_2=...=a_N\).
• Subtask \(4\) (\(25\%\) số điểm) : Không có ràng buộc gì thêm.

Example

3
1 2 3
4 5 6

762

Sau kì thi tin học trẻ, shiba đã đặt mua \(N\) gói kẹo nhằm tự thưởng cho mình, và cũng để chia sẻ với _minhduc. Số kẹo lần lượt trong mỗi gói là \(a_1,a_2,a_3,\ldots,a_n\). shiba muốn chia các gói kẹo này thành hai phần, một phần đưa cho _minhduc, một phần để mình ăn. Để cho _minhduc khỏi ganh tị, shiba muốn tìm cách chia mà chênh lệch tổng số kẹo của hai người là nhỏ nhất. Vì các gói kẹo có hương vị khác nhau, shiba không muốn bóc các gói kẹo để tránh chúng bị trộn lẫn..

Yêu cầu: Hãy giúp shiba tìm cách chia các gói kẹo sao cho chênh lệch tổng số kẹo của hai người là nhỏ nhất có thể.

Input

• Dòng đầu tiên nhập số nguyên dương \(N\) – số gói kẹo \((2\le N\le{10}^4)\).
• Dòng thứ hai nhập \(N\) phần tử - số kẹo mỗi gói \((0 \le {a}_i\le{10}^9)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): Có \(N \le 20\).
• Subtask \(2\) (\(25\%\) số điểm): Có \(N \le 1000\), tổng số kẹo trong tất cả các gói không vượt quá \(3 \times {10}^4\).
• Subtask \(3\) (\(25\%\) số điểm): Có \(N \le 40\).
• Subtask \(4\) (\(25\%\) số điểm): Có \(N \le 10^4\), tổng số kẹo trong tất cả các gói không vượt quá \(12 \times {10}^5\).

Example

5
19 17 13 9 7

1