APIO 2010

Bạn là chỉ huy của một đội quân gồm \(n\) người lính, được đánh số từ \(1\) đến \(n\). Để chuẩn bị cho trận đánh sắp tới, bạn muốn chia toàn bộ đội quân thành các đơn vị biệt kích. Nhằm tăng cường đoàn kết và tinh thần chiến đấu, mỗi đơn vị phải gồm một dãy liên tiếp các người lính, có dạng \((i,i+1,\ldots,i+k)\). Mỗi người lính thuộc đúng một đơn vị.

Người lính thứ \(i\) có sức chiến đấu \(x_i\). Sức chiến đấu ban đầu của một đơn vị là tổng sức chiến đấu của các thành viên:

Sau nhiều năm giành chiến thắng, bạn nhận thấy sức chiến đấu của một đơn vị cần được điều chỉnh theo công thức sau, trong đó \(a,b,c\) là các hệ số đã biết và \(a<0\):

Hãy chia đội quân thành các đơn vị sao cho tổng sức chiến đấu sau điều chỉnh của tất cả các đơn vị là lớn nhất.

Dữ liệu vào

Dữ liệu gồm ba dòng:

• Dòng đầu chứa số nguyên dương \(n\), số người lính.
• Dòng thứ hai chứa ba số nguyên \(a,b,c\), các hệ số của công thức điều chỉnh.
• Dòng cuối chứa \(n\) số nguyên \(x_1,x_2,\ldots,x_n\) cách nhau bởi dấu cách, lần lượt là sức chiến đấu của các người lính từ \(1\) đến \(n\).

Dữ liệu ra

In một dòng chứa một số nguyên: tổng sức chiến đấu sau điều chỉnh lớn nhất có thể đạt được.

Ràng buộc

• \(1\le n\le 1\,000\,000\).
• \(-5\le a\le -1\).
• \(|b|\le 10\,000\,000\), \(|c|\le 10\,000\,000\).
• \(1\le x_i\le 100\) với mọi \(1\le i\le n\).

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm của nhóm khi đúng toàn bộ test trong nhóm. Điểm trong bảng là phần điểm cộng thêm trên LQDOJ; nhóm sau bao gồm lại các test thỏa điều kiện của nhóm trước.

Ví dụ

4
-1 10 -20
2 2 3 4

9

Nguồn

APIO 2010 — Commando, đề tiếng Anh phiên bản 1.2.

Một thành phố có \(N\) ngôi làng được đánh số \(1,2,\ldots,N\) và \(N-1\) con đường nối giữa các làng. Mỗi con đường nối đúng hai làng và có độ dài \(1\). Từ một làng bất kỳ, có thể đi đến mọi làng khác theo các con đường này.

Để bảo đảm an toàn cho người dân, mỗi ngày đội tuần tra của cảnh sát phải đi qua tất cả các con đường. Đồn cảnh sát nằm ở làng \(1\), nên đội tuần tra phải xuất phát từ làng \(1\) và cuối ngày quay lại làng \(1\).

Thành phố dự định xây thêm đúng \(K\) đường tắt để giảm tổng quãng đường tuần tra. Mỗi đường tắt có độ dài \(1\) và có thể nối hai làng bất kỳ. Hai đường tắt có thể chung đầu mút; một đường tắt thậm chí có thể nối một làng với chính nó.

Do kinh phí hạn chế, \(K\) chỉ có thể bằng \(1\) hoặc \(2\). Để bảo đảm các đường tắt được sử dụng, đội tuần tra bắt buộc phải đi qua mỗi đường tắt đúng một lần mỗi ngày. Các con đường ban đầu vẫn phải được đi qua ít nhất một lần.

Hãy xác định tổng quãng đường tuần tra nhỏ nhất có thể đạt được sau khi chọn vị trí xây \(K\) đường tắt.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N,K\) với \(1\le K\le 2\).

Mỗi dòng trong \(N-1\) dòng tiếp theo chứa hai số nguyên \(A,B\) với \(1\le A,B\le N\), cho biết có một con đường nối làng \(A\) với làng \(B\).

Dữ liệu ra

In một dòng chứa một số nguyên: tổng quãng đường nhỏ nhất mà đội tuần tra phải đi mỗi ngày sau khi xây \(K\) đường tắt.

Ràng buộc

• \(3\le N\le 100\,000\).
• \(1\le K\le 2\).
• \(N-1\) con đường ban đầu nối tất cả các làng thành một mạng liên thông.

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm của nhóm khi đúng toàn bộ test trong nhóm. Điểm trong bảng là phần điểm cộng thêm trên LQDOJ; các nhóm có điều kiện bao hàm nhau sẽ dùng lại những test tương ứng.

Ví dụ

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

11

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

10

5 2
1 2
2 3
3 4
4 5

6

Nguồn

APIO 2010 — Patrol, đề tiếng Anh phiên bản 1.2.

Một công ty viễn thông đang xây dựng mạng GSM tại Bắc Kinh. Trong thành phố có \(n\) ngôi nhà cần được phủ sóng. Do ngân sách hạn chế, công ty chỉ có thể lắp đặt một ăng-ten.

Để đơn giản hóa việc chọn vị trí, công ty sẽ chọn ba trong số \(n\) ngôi nhà, dựng đường tròn đi qua chúng và đặt ăng-ten tại tâm đường tròn đó. Phạm vi phủ sóng bao gồm tất cả các ngôi nhà nằm bên trong hoặc trên đường tròn.

Công ty dự định chọn ngẫu nhiên ba ngôi nhà, với mọi bộ ba có khả năng được chọn như nhau. Hãy tính số ngôi nhà được phủ sóng trung bình trên tất cả các cách chọn.

Vị trí các ngôi nhà được cho bằng tọa độ nguyên trong hệ tọa độ hai chiều. Không có ba ngôi nhà nào thẳng hàng và không có bốn ngôi nhà nào cùng nằm trên một đường tròn.

Dữ liệu vào

Dòng đầu chứa số nguyên dương \(n\), số ngôi nhà. Tiếp theo là \(n\) dòng mô tả vị trí các ngôi nhà. Với mỗi \(i\) từ \(1\) đến \(n\), dòng thứ \(i+1\) chứa hai số nguyên \(x_i,y_i\) cách nhau bởi dấu cách, là tọa độ ngôi nhà thứ \(i\).

Dữ liệu ra

In một số thực: số ngôi nhà được phủ sóng trung bình. Sai số tuyệt đối của kết quả không được vượt quá \(0.01\).

Ràng buộc

• \(3\le n\le 1\,500\).
• \(x_i,y_i\) là các số nguyên và \(-1\,000\,000\le x_i,y_i\le 1\,000\,000\) với mọi \(1\le i\le n\).
• Không có ba ngôi nhà nào thẳng hàng.
• Không có bốn ngôi nhà nào cùng nằm trên một đường tròn.

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm của nhóm khi đúng toàn bộ test trong nhóm. Điểm trong bảng là phần điểm cộng thêm trên LQDOJ; nhóm sau bao gồm lại các test thỏa điều kiện của nhóm trước.

Ví dụ

4
0 2
4 4
0 0
2 0

3.500

    Các kết quả $3.5$, $3.50$, $3.500$, … đều đúng. Các kết quả $3.51$, $3.49$, $3.499999$, … cũng được chấp nhận.

Nguồn

APIO 2010 — Signaling, đề tiếng Anh phiên bản 1.2.