USACO 2016 - Tháng 2 - Hạng Đồng

Farmer John nhận được một đơn đặt hàng đúng \(M\) đơn vị sữa (\(1 \leq M \leq 1\,000\)) 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ó ba chiếc xô đựng sữa với dung tích nguyên lần lượt là \(X\), \(Y\) và \(M\) (\(1 \leq X < Y < M\)). Ban đầu, cả ba chiếc xô đều rỗng. Với ba chiếc xô này, ông có thể thực hiện hai loại thao tác sau bao nhiêu lần tùy ý:

• Đổ đầy đến miệng chiếc xô nhỏ nhất (dung tích \(X\)) bằng \(X\) đơn vị sữa rồi rót vào chiếc xô dung tích \(M\), miễn là việc này không làm chiếc xô dung tích \(M\) bị tràn.
• Đổ đầy đến miệng chiếc xô cỡ vừa (dung tích \(Y\)) bằng \(Y\) đơn vị sữa rồi rót vào chiếc xô dung tích \(M\), miễn là việc này không làm chiếc xô dung tích \(M\) bị tràn.

Mặc dù FJ biết rằng có thể ông không thể đổ đầy hoàn toàn chiếc xô dung tích \(M\), hãy giúp ông xác định lượng sữa lớn nhất có thể cho vào chiếc xô này.

Dữ liệu vào

Dòng duy nhất chứa \(X\), \(Y\) và \(M\), cách nhau bởi dấu cách.

Dữ liệu ra

In lượng sữa lớn nhất mà FJ có thể cho vào chiếc xô dung tích \(M\).

Ví dụ

17 25 77

76

Nguồn

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

Tác giả: Brian Dean.

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 1\,000\)). 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 muốn đúng \(r_i\) con bò ở lại trong mỗi phòng \(i\) (\(1 \leq r_i \leq 100\)). Để lùa bò vào chuồng một cách trật tự, ông dự định mở khóa cửa ngoài của đúng một phòng, cho phép đàn bò đi vào qua cửa đó. Sau đó, mỗi con bò đi theo chiều kim đồng hồ qua các phòng cho đến khi đến một vị trí thích hợp. Farmer John muốn mở khóa cửa ngoài sao cho tổng quãng đường mà đàn bò phải đi là nhỏ nhất. Hãy xác định tổng quãng đường nhỏ nhất mà đàn bò phải đi nếu ông chọn cửa tốt nhất để mở khóa. Quãng đường một con bò đi được tính bằng số cửa bên trong mà nó đi qua.

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 \(r_1 \ldots r_n\).

Dữ liệu ra

In tổng quãng đường nhỏ nhất mà đàn bò phải đi.

Ví dụ

5
4
7
8
6
4

48

Nguồn

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

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 100\); các \(x_i\) và \(y_i\) là những số nguyên dương lẻ không vượt quá \(B\)). 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 hai số nguyên \(N\) và \(B\). 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.

Phân nhóm

• Trong năm trường hợp kiểm thử đầu tiên, \(B \leq 100\).
• Trong tất cả các trường hợp kiểm thử, \(B \leq 1\,000\,000\).

Ví dụ

7 10
7 3
5 5
9 7
3 1
7 7
5 3
9 1

2

Nguồn

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

Tác giả: Brian Dean.