2025 - Chọn Đội tuyển Học sinh giỏi Quốc gia - Bắc Quảng Trị

Mark là CEO của tập đoàn Space X. Tập đoàn có ~n~ nhân viên, nhân viên thứ ~i~ có mã số là ~a_i~.

Mark sẽ chia toàn bộ nhân viên thành ~2~ nhóm A và B, mỗi nhóm phải có ít nhất một nhân viên.

Mỗi nhóm sẽ chọn một mã màu có giá trị từ ~1~ đến ~10^9~. Mã màu của một nhóm phải không lớn hơn tổng mã số của các thành viên trong nhóm đó.

Hai cách chia được coi là khác nhau nếu:

• Có ít nhất một nhân viên thuộc nhóm khác.
• Hoặc mã màu của một trong hai nhóm khác nhau.

Hãy đếm số cách chia nhóm khác nhau.

Vì đáp án rất lớn, hãy in kết quả modulo ~10^9+7~.

Input

• Dữ liệu được đọc từ file văn bản GROUP.INP.
• Dòng ~1~ chứa số nguyên ~n~ ~(2 \leq n \leq 10^5)~.
• Dòng ~2~ chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(1 \leq a_i \leq 10^9)~.

Output

• Ghi kết quả ra file văn bản GROUP.OUT.
• Một số nguyên duy nhất là số cách chia.

Scoring

• Subtask ~1~ (~40\%~ số điểm): ~n \leq 20~.
• Subtask ~2~ (~40\%~ số điểm): ~n \leq 30, a_i \leq n~.
• Subtask ~3~ (~20\%~ số điểm): Không có ràng buộc thêm.

Example input 1

2
1 2

Example output 1

4

Note 1

Với ~a = [1,2]~:

• Chia: ~A = \{1\},~ màu = ~1~
• ~B = \{2\},~ màu = ~1~ hoặc ~2~ ~\Rightarrow~ ~2~ cách.
• Hoặc:
• ~A = \{2\},~ màu = ~1~ hoặc ~2~
• ~B = \{1\},~ màu = ~1~ ~\Rightarrow~ ~2~ cách.

Tổng cộng ~4~ cách.

Example input 2

2
2 3

Example output 2

12

Note 2

Với ~a = [2,3]~:

• ~A = \{2\}:~ có ~2~ màu.
• ~B = \{3\}:~ có ~3~ màu.

~\Rightarrow~ ~2 \times 3 = 6~ cách.

Đổi hai nhóm cho nhau cũng hợp lệ.

Tổng cộng ~12~ cách.

Mark sản xuất ~n~ loại mảnh ghép, mảnh thứ ~i~ có chiều dài ~a_i~.

Có thể sử dụng không giới hạn số lượng mỗi loại mảnh ghép.

Một thiết bị có chiều dài ~d~ được gọi là lắp ghép được nếu tồn tại cách chọn một số mảnh ghép sao cho tổng chiều dài đúng bằng ~d~.

Cho giới hạn chiều dài ~T~.

Hãy đếm số giá trị ~d~ ~(0 ≤ d ≤ T)~ có thể lắp ghép được.

Input

• Dữ liệu được đọc từ file văn bản LEGO.INP.
• Dòng ~1~ gồm hai số nguyên ~n~, ~T~ ~(1 ≤ n ≤ 2000, 0 ≤ T ≤ 10^{18})~.
• Dòng ~2~ gồm ~n~ số nguyên ~a_i~ ~(1 ≤ a_i ≤ 2000)~.

Output

• Ghi kết quả ra file văn bản LEGO.OUT.
• Một số nguyên duy nhất là số chiều dài có thể lắp ghép.

Scoring

• Subtask ~1~ (~40\%~ số điểm): ~T ≤ 2 × 10^3~.
• Subtask ~2~ (~20\%~ số điểm): ~T ≤ 2 × 10^4~.
• Subtask ~3~ (~20\%~ số điểm): ~T ≤ 2 × 10^6~.
• Subtask ~4~ (~20\%~ số điểm): ~T ≤ 10^{18}~.

Example input 1

2 7
2 5

Example output 1

6

Note 1

Các chiều dài có thể lắp ghép: ~0, 2, 4, 5, 6, 7~.

Có tất cả ~6~ giá trị.

Cho một cây gồm ~n~ đỉnh, đánh số từ ~1~ đến ~n~.

Đỉnh ~i~ có trọng số ~w_i~.

Định nghĩa:

Khi chọn gốc của cây là ~root~,

• ~subtree(a)~ là cây con gốc ~a~,
• ~S(root,a)~ là tổng trọng số các đỉnh trong ~subtree(a)~.

Tức là $$ ~S~(root,~a~) = \sum_{\nu \in subtree(~a~)} w_\nu $$

Có ~q~ truy vấn.

Truy vấn loại ~1~:

• ~1~ ~a~ ~b~ In ra giá trị ~S(a,b)~

Truy vấn loại ~2~:

• ~2~ ~a~ ~b~ ~v~ Chọn gốc của cây là ~a~. Với mọi đỉnh thuộc cây con gốc ~b~, cập nhật ~w[u] \text{ ^= } v~ trong đó ^ là phép XOR.

Input

• Dữ liệu được đọc từ file văn bản TREEQUERY.INP.
• Dòng ~1~: số nguyên ~n~ ~(1 \leq n \leq 10^5)~.
• Dòng ~2~: ~n~ số nguyên ~w_i~ ~(0 \leq w_i \leq 10^9)~.
• ~n-1~ dòng tiếp theo: mỗi dòng gồm hai số ~u~ ~v~ mô tả một cạnh.
• Dòng tiếp theo: số nguyên ~q~ ~(1 \leq q \leq 10^5)~.
• ~q~ dòng tiếp theo là các truy vấn:
• Loại ~1~: ~1~ ~a~ ~b~
• Loại ~2~: ~2~ ~a~ ~b~ ~v~

Output

• Ghi kết quả ra file văn bản TREEQUERY.OUT.
• Với mỗi truy vấn loại ~1~, in ra một dòng chứa kết quả.

Scoring

• Subtask ~1~ (~20\%~ số điểm): ~n,q \leq 2000~.
• Subtask ~2~ (~20\%~ số điểm): Không có truy vấn loại ~2~.
• Subtask ~3~ (~20\%~ số điểm): Mỗi đỉnh có nhiều nhất ~2~ đỉnh kề.
• Subtask ~4~ (~20\%~ số điểm): Không có truy vấn với ~a = 1~.
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc thêm.

Example input 1

7
1 2 3 4 5 6 7
1 2
1 3
2 4
2 6
6 5
3 7
3
1 1 2
2 1 2 1
1 1 2

Example output 1

17
19

Note 1

• Mô tả ví dụ nếu có.

Mark là CEO của tập đoàn Space X. Tập đoàn có ~n~ dự án cần hoàn thành, dự án thứ ~i~ có lợi nhuận ~a_i~.

Có ~k~ nhân viên để thực hiện các dự án.

Mỗi nhân viên chỉ được giao một đoạn liên tiếp các dự án (có thể gồm một hoặc nhiều dự án). Mỗi dự án chỉ được giao cho nhiều nhất một nhân viên. Một số dự án có thể không được giao cho bất kỳ nhân viên nào.

Giá trị công việc của một nhân viên bằng tổng lợi nhuận các dự án mà người đó đảm nhiệm. Nếu không nhận dự án nào thì giá trị bằng ~0~.

Hãy phân công các dự án sao cho tổng lợi nhuận của tất cả nhân viên là lớn nhất.

Input

• Dữ liệu được đọc từ file văn bản PLAN.INP.
• Dòng ~1~ chứa hai số nguyên ~n~ và ~k~ ~(1 \leq n \leq 2000)~.
• Dòng ~2~ chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ với ~|a_i| \leq 10^9~.

Output

• Ghi kết quả ra file văn bản PLAN.OUT.
• Một số nguyên là tổng lợi nhuận lớn nhất.

Scoring

• Subtask ~1~ (~33\%~ số điểm): ~1 \leq n \leq 80~.
• Subtask ~2~ (~33\%~ số điểm): ~81 \leq n \leq 300~.
• Subtask ~3~ (~34\%~ số điểm): ~301 \leq n \leq 2000~.

Example input 1

5 1
1 -2 3 -1 4

Example output 1

6

Note 1

• Có một nhân viên nhận các dự án ~3, 4, 5~, tổng lợi nhuận là: ~3 + (-1) + 4 = 6~.

Example input 2

5 2
1 -2 3 -1 4

Example output 2

7

Note 2

Hai nhân viên lần lượt nhận:

• Dự án ~3~.
• Dự án ~5~.

Tổng lợi nhuận: ~3 + 4 = 7~.

Có ~n~ robot có chiều cao đôi một khác nhau.

Cần xếp tất cả robot thành một hàng.

Một robot được gọi là nhìn thấy từ bên trái nếu mọi robot đứng trước nó đều thấp hơn nó.

Tương tự, một robot được gọi là nhìn thấy từ bên phải nếu mọi robot đứng trước nó theo hướng nhìn từ phải sang đều thấp hơn nó.

Yêu cầu:

• Từ phía Tây (bên trái), nhìn thấy đúng ~p~ robot.
• Từ phía Đông (bên phải), nhìn thấy đúng ~q~ robot.

Hãy đếm số cách sắp xếp thỏa mãn yêu cầu.

Do kết quả rất lớn, in ra modulo ~10^9+7~.

Input

• Dữ liệu được đọc từ file văn bản ROBOT.INP.
• Dòng ~1~ chứa ba số nguyên ~n~, ~p~, ~q~ (~1 ≤ n ≤ 2000~, ~1 ≤ p, q ≤ n~).
• Dòng ~2~ chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~
• (~1 ≤ a_i ≤ 2000~), là chiều cao các robot.
• Các chiều cao đôi một khác nhau.

Output

• Ghi kết quả ra file văn bản ROBOT.OUT.
• Một số nguyên là số cách xếp modulo ~10^9+7~.

Scoring

• Subtask ~1~ (~25\%~ số điểm): ~n ≤ 10~.
• Subtask ~2~ (~25\%~ số điểm): ~n ≤ 500, q = 1~.
• Subtask ~3~ (~25\%~ số điểm): ~n ≤ 500~.
• Subtask ~4~ (~25\%~ số điểm): ~n ≤ 2000~.

Example input 1

3 2 1
1 2 3

Example output 1

1

Note 1

Trong ~3! = 6~ cách xếp, chỉ có duy nhất thứ tự chiều cao ~2, 1, 3~

thỏa mãn điều kiện.

Một nhà máy được xây trên lưới kích thước ~m × n~.

Tại ô ~(i, j)~ có ~a_{ij}~ khối lập phương đơn vị được xếp chồng lên nhau.

Có ~k~ phát bắn laser.

Mỗi phát bắn có dạng: ~dir,~ ~i,~ ~h~

trong đó:

• ~dir~ là một trong bốn hướng: ~W~ (Tây), ~E~ (Đông), ~N~ (Bắc), ~S~ (Nam).
• Nếu ~dir~ là ~W~ hoặc ~E~ thì ~i~ là chỉ số dòng.
• Nếu ~dir~ là ~N~ hoặc ~S~ thì ~i~ là chỉ số cột.
• ~h~ là độ cao của tia laser.

Mỗi tia laser phá hủy ~r~ khối đầu tiên trên đường đi của nó.

Nếu phía trên khối bị phá hủy còn các khối khác thì chúng rơi thẳng xuống.

Sau khi thực hiện toàn bộ ~k~ phát bắn, tập đoàn chọn một vùng vuông kích thước ~p × p~.

Các tia laser được bố trí phù hợp để phá hủy toàn bộ các khối vật liệu còn lại trong vùng đó.

Hãy tìm số lượng khối vật liệu lớn nhất có thể bị phá hủy trong một vùng ~p × p~.

Input

• Dữ liệu được đọc từ file văn bản CLEAN.INP.
• Dòng ~1~ gồm năm số nguyên: ~m~ ~n~ ~r~ ~k~ ~p~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ bao gồm ~n~ số nguyên ~a_{ij}~ ~(1 ≤ a_{ij} ≤ 10^6)~.
• ~k~ dòng tiếp theo mô tả các phát bắn: ~dir~ ~i~ ~h~.

Output

• Ghi kết quả ra file văn bản CLEAN.OUT.
• Một số nguyên duy nhất là đáp án.

Scoring

• Subtask ~1~ (~30\%~ số điểm): ~m × n ≤ 300~.
• Subtask ~2~ (~70\%~ số điểm): Không có ràng buộc thêm.

Example input 1

4 8 2 6 2
1 1 1 1 1 1 1 1
1 2 3 1 1 3 1 1
1 2 1 1 3 1 1 1
1 1 1 1 1 1 1 2
N 2 2
W 2 2
W 2 3
E 2 1
S 4 1
S 7 1

Example output 1

6

Note 1

Sau khi thực hiện toàn bộ các phát bắn, chọn vùng vuông ~2 × 2~ sao cho số khối vật liệu bị phá hủy là lớn nhất.

Trong ví dụ, số khối vật liệu tối đa có thể phá hủy là: ~6~.