USACO 2016 - Tháng 2 - Hạng Bạc

Là một người yêu thích kiến trúc đương đại, Farmer John đã xây một chuồng mới có dạng một đường tròn hoàn hảo. Bên trong, chuồng gồm một vòng tròn có \(n\) phòng, được đánh số theo chiều kim đồng hồ từ \(1 \ldots n\) quanh chu vi chuồng (\(3 \leq n \leq 1000\)). Mỗi phòng đều có cửa thông sang hai phòng bên cạnh và một cửa mở ra bên ngoài chuồng.

Farmer John sở hữu \(n\) con bò và muốn đúng một con bò ở lại trong mỗi phòng của chuồng. Tuy nhiên, vì hơi bối rối, đàn bò xếp hàng lộn xộn trước các cửa, và có thể có nhiều con bò xếp hàng trước cùng một cửa. Chính xác \(c_i\) con bò xếp hàng bên ngoài cửa vào phòng \(i\), do đó \(\sum c_i=n\).

Để lùa bò sao cho mỗi phòng có một con, Farmer John muốn áp dụng cách sau: mỗi con bò đi vào qua cửa nơi nó xếp hàng ban đầu, rồi đi theo chiều kim đồng hồ qua các phòng cho đến khi đến một vị trí thích hợp. Biết rằng một con bò đi qua \(d\) cửa sẽ tiêu tốn \(d^2\) đơn vị năng lượng, hãy xác định lượng năng lượng nhỏ nhất cần thiết để phân bổ đàn bò sao cho mỗi phòng có một con.

Dữ liệu vào

Dòng đầu tiên chứa \(n\). Mỗi dòng trong \(n\) dòng còn lại lần lượt chứa \(c_1 \ldots c_n\).

Dữ liệu ra

In lượng năng lượng nhỏ nhất mà đàn bò tiêu tốn.

Ví dụ

10
1
0
0
2
0
0
1
2
2
2

33

Nguồn

USACO 2016 February Contest, Silver - Circular Barn: https://usaco.org/index.php?page=viewproblem2&cpid=618

Tác giả: Brian Dean.

\(N\) con bò của Farmer John đang đứng tại các vị trí phân biệt \((x_1,y_1) \ldots (x_n,y_n)\) trên trang trại hai chiều của ông (\(1 \leq N \leq 1000\); các \(x_i\) và \(y_i\) là những số nguyên dương lẻ không vượt quá \(1\,000\,000\)). FJ muốn chia cánh đồng bằng cách dựng một hàng rào dài theo hướng bắc–nam (trên thực tế có thể xem là dài vô hạn) với phương trình \(x=a\). \(a\) là một số nguyên chẵn, nhờ đó ông chắc chắn không dựng hàng rào xuyên qua vị trí của bất kỳ con bò nào. Ông cũng muốn dựng một hàng rào dài theo hướng đông–tây (trên thực tế có thể xem là dài vô hạn) với phương trình \(y=b\), trong đó \(b\) là một số nguyên chẵn. Hai hàng rào cắt nhau tại điểm \((a,b)\) và cùng chia cánh đồng thành bốn vùng.

FJ muốn chọn \(a\) và \(b\) sao cho số bò trong bốn vùng tạo thành tương đối "cân bằng", không có vùng nào chứa quá nhiều bò. Gọi \(M\) là số bò lớn nhất trong một trong bốn vùng, FJ muốn làm cho \(M\) nhỏ nhất có thể. Hãy giúp ông xác định giá trị nhỏ nhất có thể của \(M\).

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa tọa độ \(x\) và \(y\) của một con bò.

Dữ liệu ra

In giá trị nhỏ nhất có thể của \(M\) mà FJ đạt được khi đặt các hàng rào một cách tối ưu.

Ví dụ

7
7 3
5 5
7 13
3 1
11 7
5 3
9 1

2

Nguồn

USACO 2016 February Contest, Silver - Load Balancing: https://usaco.org/index.php?page=viewproblem2&cpid=619

Tác giả: Brian Dean.

Farmer John nhận được một đơn đặt hàng đúng \(M\) đơn vị sữa (\(1 \leq M \leq 200\)) và cần giao ngay. Không may, chiếc máy vắt sữa hiện đại của ông vừa bị hỏng, và ông chỉ có hai chiếc xô đựng sữa với dung tích nguyên là \(X\) và \(Y\) (\(1 \leq X,Y \leq 100\)) để đong sữa. Ban đầu, cả hai chiếc xô đều rỗng. Với hai chiếc xô này, ông có thể thực hiện tối đa \(K\) thao tác thuộc các loại sau (\(1 \leq K \leq 100\)):

• Đổ đầy hoàn toàn một trong hai chiếc xô.
• Đổ hết sữa khỏi một trong hai chiếc xô.
• Rót sữa từ một chiếc xô sang chiếc còn lại, dừng lại khi chiếc xô thứ nhất rỗng hoặc chiếc xô thứ hai đầy (tùy điều nào xảy ra trước).

Mặc dù FJ biết rằng có thể tổng lượng sữa trong hai chiếc xô cuối cùng không đúng bằng \(M\), hãy giúp ông tính sai số nhỏ nhất giữa \(M\) và tổng lượng sữa trong hai chiếc xô. Nói cách khác, hãy tính giá trị nhỏ nhất của \(|M-M'|\) sao cho FJ có thể tạo ra tổng cộng \(M'\) đơn vị sữa trong hai chiếc xô.

Dữ liệu vào

Dòng duy nhất chứa \(X\), \(Y\), \(K\) và \(M\).

Dữ liệu ra

In khoảng cách nhỏ nhất từ \(M\) đến một lượng sữa mà FJ có thể tạo ra.

Ví dụ

14 50 2 32

18

(0, 0) = 0 đơn vị
(14, 0) = 14 đơn vị
(0, 50) = 50 đơn vị
(0, 14) = 14 đơn vị
(14, 36) = 50 đơn vị
(14, 50) = 64 đơn vị

Nguồn

USACO 2016 February Contest, Silver - Milk Pails: https://usaco.org/index.php?page=viewproblem2&cpid=620

Tác giả: Brian Dean.