OLP MT&TN 2023 Sơ Loại Chuyên Tin

Một nhóm sinh viên gồm \(n\) người tham gia một chuyến team-building do khoa tổ chức. Khi đến điểm du lịch, đoàn sinh viên được tham gia một số trò chơi vận động. Trong đó có một trò chơi như sau: Các sinh viên xếp thành một hàng ngang. Mỗi khi có tiếng còi, các sinh viên đứng cạnh nhau cần di chuyển xích lại gần sao cho hình thành một số nhóm thỏa mãn:

• Mỗi nhóm gồm các sinh viên đứng cạnh nhau theo thứ tự xếp hàng ban đầu
• Chênh lệch số nam và nữ trong mỗi nhóm không được vượt quá số \(k\) mà ban tổ chức cho.

Sau mỗi tiếng còi các sinh viên cần tạo ra cách ghép nhóm khác với tất cả các lượt trước đó. Do vậy, bạn hãy giúp đoàn sinh viên đếm xem có bao nhiêu cách ghép nhóm khác nhau thỏa mãn các yêu cầu trên.

Biết rằng hai cách ghép nhóm gọi là khác nhau khi hai sinh viên bất kì chung nhóm trong cách ghép này lại không chung nhóm trong cách ghép kia.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) \((1 \leq k \leq n \leq 5000)\) lần lượt là số lượng sinh viên trong đoàn và chênh lệch nam nữ tối đa của mỗi nhóm.
• Dòng tiếp theo chứa một xâu nhị phân độ dài \(n\) với kí tự 1 tượng trưng cho sinh viên nam, và 0 cho sinh viên nữ.

Output

• In ra một số nguyên duy nhất là phần dư của kết quả tìm được khi chia cho \(10^{9} + 7\).

Scoring

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

Example

4 1
1011

5

10 2
1011010001 

472

Hôm nay Hoa quyết định đi chợ mua hoa quả giúp mẹ. Khu chợ tại nơi sinh sống của Hoa bao gồm \(n\) gian hàng được xếp thành một vòng tròn. Các gian hàng được đánh số từ \(1\) đến \(n\) theo chiều kim đồng hồ (gian hàng \(n\) nằm cạnh gian hàng \(1\)). Gian hàng thứ \(i\) (\(1 \leq i \leq n\)) bán một loại quả với giá \(a_i\) đồng. Giả sử rằng mỗi gian hàng có một nguồn cung cấp không giới hạn.

Hoa muốn dùng \(m\) đồng để mua hoa quả. Kế hoạch mua của Hoa là như sau:

• Đầu tiên, Hoa ghé thăm gian hàng \(1\).
• Hoa sẽ mua đúng một quả nếu còn đủ tiền.
• Sau đó, Hoa sẽ di chuyển qua gian hàng bên cạnh theo chiều kim đồng hồ và tiếp tục kế hoạch.

Vì số tiền của Hoa có giới hạn, kế hoạch sẽ dừng lại khi Hoa không còn đủ tiền để mua bất kỳ loại quả nào. Hãy tìm số lượng quả mà Hoa mua được.

Input

• Dòng đầu tiên chứa số nguyên \(n\) và \(m\) \((1 \leq n \leq 10^{5}, 1 \leq m \leq 10^{18})\) lần lượt là số lượng gian hàng và số tiền tối đa mà Hoa có thể dùng.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{9})\) là giá tiền của mỗi loại quả tại mỗi gian hàng.

Ouput

• In ra một số nguyên duy nhất là số lượng quả mà Hoa mua được.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n = 2\).
• Subtask \(2\) (\(30\%\) số điểm): \(a_{1} \leq a_{2} \leq \ldots \leq a_{n}\).
• Subtask \(3\) (\(30\%\) số điểm): \(m \leq \min(a_{1}, a_{2}, \ldots, a_{n}) \times 10^{6}\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 38
5 2 5

10

5 21
2 4 100 2 6

6

Mới đây, công ty nơi Quân đang làm mở chi nhánh mới ở thành phố X và cử Quân chuyển đến làm ở đây. Do đó, Quân cần tìm địa điểm để thuê nhà.

Thành phố X gồm có \(n\) tòa nhà đánh số từ \(1\) tới \(n\) và được nối với nhau bởi \(n-1\) con đường hai chiều. Mỗi con đường hai chiều sẽ nối giữa hai tòa nhà nào đấy với nhau. Những con đường sẽ đảm bảo giao thông trong thành phố luôn diễn ra thông suốt, hay nói cách khác, luôn tồn tại đường đi thông qua một hay một số con đường để đi từ tòa nhà này sang tòa nhà khác.

Trong số \(n\) tòa nhà này, có \(k\) tòa nhà có quán cafe. Là một người nghiện caffeine, Quân muốn tòa nhà mình ở phải gần quán cafe nào đó nhất có thể. Tuy nhiên, Quân cũng hiểu rằng vận động cơ thể là vô cùng cần thiết nên Quân sẽ không mua cà phê ở ngay chính tòa nhà mình đang ở mà muốn đi bộ sang một tòa nhà khác. Hãy giúp Quân tìm xem, với mỗi lựa chọn tòa nhà để ở, tòa nhà nào gần nhất khác tòa nhà đang ở và có quán cafe nhé.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) \((2 \leq k \leq n \leq 5 \cdot 10^{5})\) lần lượt là số lượng toà nhà và số lượng toà nhà phù hợp để thuê căn hộ.
• Trong \(n - 1\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(u_{i}\), \(v_{i}\) và \(w_{i}\) \((1 \leq u_{i}, v_{i} \leq n, 1 \leq w_{i} \leq 10^{9})\) nghĩa là có con đường độ dài \(w_{i}\) nối từ tòa nhà \(u_{i}\) tới tòa nhà \(v_{i}\).
• Dòng tiếp theo chứa \(k\) số nguyên \(a_{1}, a_{2}, \ldots a_{k}\) \((1 \leq a_{1} < a_{2} < \ldots < a_{k} \leq n)\) là danh sách các tòa nhà có quán cafe.

Output

• Gồm một dòng duy nhất chứa \(n\) số nguyên, số thứ \(i\) là khoảng cách ngắn nhất từ tòa nhà \(i\) tới tòa nhà nào đấy khác có quán cafe.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 200\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^{5}\) và \(k \leq 50\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \leq 10^{5}\).
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 2
1 2 2
1 3 1
2 4 3
2 5 4
3 5

1 3 7 6 7

Tèo và Tí đang chơi một trò chơi với các lá bài. Có \(n\) lá bài được xếp theo thứ tự từ trái qua phải, lá bài thứ \(i\) (\(1 \leq i \leq n\)) có giá trị \(a_i\).

Đầu tiên, Tèo chọn một đoạn con gồm các lá bài từ vị trí \(l\) đến vị trí \(r\) \((1 \leq l \leq r \leq n)\). Sau đó, Tí loại bỏ một lá bài \(j\) từ đoạn con \((l \leq j \leq r)\). Điểm số của trò chơi là tổng giá trị của các lá bài còn lại trong đoạn con. Trong trường hợp Tèo chọn một đoạn con chỉ có một phần tử thì điểm số sau khi Tí loại bỏ một lá bài là \(0\).

Tèo muốn làm điểm số lớn nhất có thể còn Tí sẽ chọn lá bài để điểm số nhỏ nhất có thể. Tèo nên chọn đoạn con nào?

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 10^{5})\) là số lượng lá bài.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((|a_{i}| \leq 10^{9})\) là giá trị trên mỗi lá bài.

Output

• In ra một số nguyên duy nhất là điểm số của trò chơi.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10^{2}\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^{3}\).
• Subtask \(3\) (\(30\%\) số điểm): \(|a_{i}| \leq 10^{2}\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
5 -2 10 -1 4

6

3
-7 6 -9

0