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

Cho hai số nguyên \(x\) và \(n\), hãy tính lũy thừa \(x^n\).

Input

• Là hai số nguyên \(x\) và \(n\) cách nhau một khoảng trắng (\(1 \le x \le 1000, 1 \le n \le 10^{18}\))

Output

• Là 4 số cuối của lũy thừa \(x^n\) (\(x^n \mod\ 10^4\))

Example

2 3

8

3 2

9

Bạn được cho một mảng gồm \(n\) số. Có bao nhiêu cách chọn tập hợp con các số có tổng \(x\)?

Input

Dòng đầu tiên là hai số \(n\) và \(x\) : kích thước mảng và tổng bắt buộc.

Dòng thứ hai chứa \(n\) số nguyên \(t_1,t_2,…, t_n\): các số trong mảng.

Output

In ra số cách bạn có thể tạo ra tổng \(x\).

Constraints

• \(1 \le n \le 40\)
• \(1 \le x \le 10^9\)
• \(1 \le t_i \le 10^9\)

Example

Input

4 5
1 2 3 2

Output

3

Bạn có \(34\) đồng xu có giá trị như sau:

\(xu(1)\) có giá trị \(2\)

\(xu(2)\) có giá trị \(3\)

\(xu(3)\) có giá trị \(5\)

\(for \ n = 4\) to \(34 \rightarrow\) \(xu(n)\) có giá trị \((xu(n-1) + xu(n-2) + xu(n-3))\)

Bạn hãy dùng nhiều đồng xu nhất để mua một món hàng có giá là \(X.\)

Input

• Dòng đầu tiên là số test (không quá 1000).

• Mỗi dòng tiếp theo chứa một số nguyên \(X (1 \le X \le 2000000000)\).

Output

• Với mỗi test, in ra “Case #” + số hiệu test + “: ” + số lượng lớn nhất đồng xu cần dùng.

• Nếu không có cách nào để đạt giá trị \(X\) thì in ra \(-1\).

Example

4
1
5
8
9

Case #1: -1
Case #2: 2
Case #3: 2
Case #4: -1

Cho \(N\) người \((2 \le N \le 32)\), mỗi người có một số \(a_i (1 \le a_i \le 10^9\)) được gọi là độ tin cậy.

Cần phân chia \(n\) người này vào 2 nhóm sao cho:

• Mỗi người thuộc đúng một nhóm
• Chênh lệch tổng độ tin cậy của 2 nhóm là bé nhất

Input

• Dòng đầu chứa số nguyên \(N\).

• Dòng tiếp theo chứa \(N\) số : số thứ \(i\) là độ tin cậy của người thứ \(i\).

Output

• Ghi ra hai số \(u\) và \(v\) với \(u\) là độ chênh lệch nhỏ nhất và \(v\) là số cách phân chia.

Scoring

• Subtask \(1\) (\(80\%\) số điểm): \(N \le 24\).
• Subtask \(2\) (\(20\%\) số điểm): không có điều kiện gì thêm

Example

5
1 5 6 7 8

1 3

Cân thằng bằng đã từng rất phổ biến trong xã hội loài người, vì tính đơn giản của nó. Cấu tạo của cân gồm hai đĩa \(A, B\) được đặt ở hai đầu của một đòn bẩy.

Có \(n\) quả cân, quả thứ \(i\) có khối lượng \(m_i\). Để cân một vật, người ta đặt nó vào đĩa \(A\), sau đó thêm một vài quả cân vào các đĩa sao cho cân thăng bằng. Lúc này, cân nặng của vật là tổng khối lượng các quả cân trên đĩa \(B\) trừ đi tổng khối lượng các quả cân trên đĩa \(A\), vì cân chỉ thăng bằng khi tổng khối lượng trên đĩa \(A\) bằng tổng khối lượng trên đĩa \(B\).

Tuần trước, con chim vừa chở người em đi lấy vàng về, người em tiến hành cân lại số vàng mình nhận được. Để thuận tiện, anh ấy sẽ để nguyên túi vàng và cân một lần thay vì phải tách số vàng ra. Sau khi cân, anh ấy biết chính xác rằng túi vàng nặng \(M\).

Sau đó, vì tò mò và đam mê thuật toán, anh ấy thắc mắc là liệu có bao nhiêu cách cân khác nhau? Cụ thể hơn, bạn được cho một vật có khối lượng \(M\), bạn đặt nó vào đĩa \(A\) sau đó thêm một số quả cân vào các đĩa sao cho cân thăng bằng. Cần đếm số cách khác nhau để thêm các quả cân như trên. Hai cách được coi là khác nhau nếu tồn tại \(i\), \(1 ≤ i ≤ n\), sao cho hoặc là trong cách này thì sử dụng quả cân thứ \(i\) còn trong cách kia thì không, hoặc là cả hai cách đều sử dụng quả cân thứ \(i\) nhưng đặt vào hai đĩa khác nhau.

Input

• Dòng đầu chứa: \(n, M\)
• Dòng tiếp theo chứa dãy \(m\)

Output

• Một số nguyên duy nhất là kết quả bài toán

Constraints

• \(n ≤ 20\), \(1 ≤ m_i\) , \(M\) ≤ \(10^6\) ;

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n ≤ 10\)

Example

6 10
1 2 3 4 5 6 

17