USACO 2016 - Tháng 2 - Hạng Vàng

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 100\,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 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, Gold - Circular Barn: https://usaco.org/index.php?page=viewproblem2&cpid=621

Tác giả: Brian Dean.

Sau sự cố gần nhất liên quan đến chuồng tròn của Farmer John, người ta hẳn sẽ nghĩ rằng ông đã rút ra bài học về kiến trúc phi truyền thống. Tuy nhiên, ông cho rằng mình vẫn có thể khiến chuồng tròn (trong bài trước) hoạt động tốt bằng cách cho phép nhiều con bò vào mỗi phòng. Nhắc lại, 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 100\)). 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 phòng \(i\) (\(1 \leq r_i \leq 1\,000\,000\)). Để lùa bò vào chuồng một cách trật tự, ông dự định mở khóa \(k\) cửa ngoài (\(1 \leq k \leq 7\)), chỉ cho phép đàn bò đi vào qua các 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 những cửa ngoài sao cho tổng quãng đường đàn bò phải đi sau khi vào chuồng là nhỏ nhất. Ban đầu, đàn bò có thể xếp hàng theo bất kỳ cách nào bên ngoài \(k\) cửa đã mở khóa; việc này không được tính vào tổng quãng đường đang xé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 \(k\) cửa tốt nhất để mở khóa.

Dữ liệu vào

Dòng đầu tiên chứa \(n\) và \(k\). 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ụ

6 2
2
5
4
2
6
2

14

Nguồn

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

Tác giả: Brian Dean.

Farmer John nhận ra rằng nhiều con bò của ông mắc chứng sợ không gian rộng một cách kỳ lạ. Để giúp chúng bớt sợ việc gặm cỏ, ông chia cánh đồng lớn thành nhiều vùng nhỏ hơn bằng cách dựng các hàng rào dọc (theo hướng bắc–nam) và ngang (theo hướng đông–tây).

Cánh đồng lớn là một hình chữ nhật có hai đỉnh đối diện tại \((0,0)\) và \((A,B)\). FJ dựng \(n\) hàng rào dọc (\(0 \leq n \leq 2000\)) tại các vị trí phân biệt \(a_1 \ldots a_n\) (\(0<a_i<A\)); mỗi hàng rào chạy từ \((a_i,0)\) đến \((a_i,B)\). Ông cũng dựng \(m\) hàng rào ngang (\(0 \leq m \leq 2000\)) tại các vị trí \(b_1 \ldots b_m\) (\(0<b_i<B\)); mỗi hàng rào như vậy chạy từ \((0,b_i)\) đến \((A,b_i)\). Mỗi hàng rào dọc cắt mọi hàng rào ngang, chia cánh đồng lớn thành tổng cộng \((n+1)(m+1)\) vùng.

Không may, FJ hoàn toàn quên làm cổng trên các hàng rào, khiến đàn bò không thể rời khỏi vùng đang bao quanh chúng để đi khắp cánh đồng! Ông muốn khắc phục bằng cách dỡ bỏ một số đoạn hàng rào để bò có thể đi giữa các vùng kề nhau. Ông muốn chọn một số cặp vùng kề nhau và dỡ bỏ toàn bộ đoạn hàng rào ngăn cách mỗi cặp; sau đó, ông muốn đàn bò có thể đi qua những chỗ mở này để đến bất kỳ nơi nào trong cánh đồng lớn.

Ví dụ, FJ có thể bắt đầu với một cấu trúc hàng rào như sau:

+---+--+
|   |  |
+---+--+
|   |  |
|   |  |
+---+--+

và mở nó ra như sau:

+---+--+
|      |
+---+  +
|      |
|      |
+---+--+

Hãy giúp FJ xác định tổng chiều dài hàng rào nhỏ nhất phải dỡ bỏ để đạt được mục tiêu.

Dữ liệu vào

Dòng đầu tiên chứa \(A\), \(B\), \(n\) và \(m\) (\(1 \leq A,B \leq 1\,000\,000\,000\)). \(n\) dòng tiếp theo lần lượt chứa \(a_1 \ldots a_n\), và \(m\) dòng sau đó lần lượt chứa \(b_1 \ldots b_m\).

Dữ liệu ra

In chiều dài hàng rào nhỏ nhất mà FJ phải dỡ bỏ. Lưu ý rằng kết quả có thể quá lớn để chứa trong một số nguyên 32 bit tiêu chuẩn, vì vậy bạn có thể cần sử dụng kiểu số nguyên 64 bit (ví dụ, long long trong C/C++).

Ví dụ

15 15 5 2
2
5
10
6
4
11
3

44

Nguồn

USACO 2016 February Contest, Gold - Fenced In: https://usaco.org/index.php?page=viewproblem2&cpid=623

Tác giả: Brian Dean.