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

\(N\) con bò của Farmer John cứ luôn đi lang thang đến tận những nơi xa xôi của trang trại! Ông cần bạn giúp lùa chúng về đứng gần nhau.

Cánh đồng chính của trang trại dài và hẹp — ta có thể coi nó như một trục số, trên đó một con bò có thể đứng tại bất kỳ vị trí nguyên nào. \(N\) con bò hiện đang đứng tại các vị trí nguyên khác nhau, và Farmer John muốn di chuyển chúng sao cho chúng đứng tại các vị trí liên tiếp (chẳng hạn các vị trí 3, 4, 5, 6, 7 và 8).

Đáng tiếc, những con bò khá buồn ngủ và Farmer John rất khó thu hút sự chú ý để khiến chúng di chuyển. Tại bất kỳ thời điểm nào, ông chỉ có thể khiến một con bò di chuyển nếu nó đang ở một "đầu mút" (tức là có vị trí nhỏ nhất hoặc lớn nhất trong số tất cả các con bò). Khi di chuyển một con bò, ông có thể yêu cầu nó chuyển đến bất kỳ vị trí nguyên chưa bị chiếm nào, miễn là tại vị trí mới, nó không còn là một đầu mút. Có thể thấy rằng theo thời gian, những nước đi kiểu này thường đẩy các con bò ngày càng lại gần nhau hơn.

Hãy xác định số lần di chuyển ít nhất và nhiều nhất có thể thực hiện trước khi các con bò tụ lại tại \(N\) vị trí liên tiếp.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(3 \leq N \leq 10^5\)). Mỗi dòng trong \(N\) dòng tiếp theo chứa vị trí nguyên của một con bò, nằm trong phạm vi \(1 \ldots 10^9\).

Dữ liệu ra

Dòng đầu tiên chứa số lần di chuyển ít nhất Farmer John cần thực hiện để đưa các con bò lại gần nhau. Dòng thứ hai chứa số lần di chuyển nhiều nhất mà ông có thể thực hiện trước khi các con bò tụ lại với nhau.

Ví dụ

3
7
4
9

1
2

Nguồn

USACO 2019 February Contest, Silver — Sleepy Cow Herding

Tác giả: Matthew Fahrbach.

Farmer John không giỏi làm nhiều việc cùng lúc. Ông thường xuyên bị xao nhãng, khiến những dự án dài trở nên khó hoàn thành. Hiện tại, ông đang cố sơn một mặt của chuồng bò, nhưng cứ sơn xong một vùng hình chữ nhật nhỏ, ông lại bị phân tâm bởi việc chăm sóc đàn bò, khiến một số phần của chuồng được phủ nhiều lớp sơn hơn những phần khác.

Ta có thể mô tả mặt chuồng bò như một mặt phẳng \(x\)-\(y\) hai chiều. Trên đó, Farmer John sơn \(N\) hình chữ nhật có các cạnh song song với các trục tọa độ; mỗi hình được mô tả bằng tọa độ góc dưới bên trái và góc trên bên phải.

Farmer John muốn phủ vài lớp sơn lên chuồng để không phải sơn lại trong tương lai gần. Tuy nhiên, ông không muốn lãng phí thời gian bằng cách phủ quá nhiều lớp sơn. Hóa ra \(K\) lớp sơn là số lượng tối ưu. Hãy giúp ông xác định diện tích chuồng được phủ đúng \(K\) lớp sơn sau khi ông sơn tất cả các hình chữ nhật của mình.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\) (\(1 \leq K \leq N \leq 10^5\)). Mỗi dòng trong \(N\) dòng còn lại chứa bốn số nguyên \(x_1, y_1, x_2, y_2\), mô tả một vùng hình chữ nhật được sơn với góc dưới bên trái \((x_1, y_1)\) và góc trên bên phải \((x_2, y_2)\). Tất cả các giá trị \(x\) và \(y\) đều nằm trong phạm vi \(0 \ldots 1000\), và mọi hình chữ nhật đều có diện tích dương.

Dữ liệu ra

In ra diện tích của phần chuồng được phủ đúng \(K\) lớp sơn.

Ví dụ

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

8

Nguồn

USACO 2019 February Contest, Silver — Painting the Barn

Tác giả: Nick Wu.

Một đợt hạn hán kéo dài đã khiến \(N\) đồng cỏ của Farmer John không còn chút cỏ nào. Tuy nhiên, mùa mưa sắp đến và đã tới lúc "phủ xanh trở lại". Trong nhà kho, Farmer John có hai thùng, mỗi thùng chứa một loại hạt giống cỏ khác nhau. Ông muốn trồng cỏ trên từng đồng cỏ trong số \(N\) đồng cỏ, và chọn đúng một loại cỏ để trồng trên mỗi đồng.

Là một người chăn bò sữa, Farmer John muốn bảo đảm đáp ứng những nhu cầu ăn uống có phần đặc biệt của \(M\) con bò. Mỗi con trong số \(M\) con bò có hai đồng cỏ yêu thích. Một số con có chế độ ăn yêu cầu chúng chỉ ăn nhất quán một loại cỏ — vì vậy Farmer John muốn bảo đảm hai đồng cỏ yêu thích của bất kỳ con bò nào như vậy được trồng cùng một loại cỏ. Những con bò khác có một chế độ ăn rất khác, đòi hỏi chúng phải ăn các loại cỏ khác nhau. Đối với những con bò ấy, hiển nhiên Farmer John muốn bảo đảm hai đồng cỏ yêu thích của chúng chứa hai loại cỏ khác nhau.

Hãy giúp Farmer John xác định số cách khác nhau để trồng cỏ trên \(N\) đồng cỏ.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(2 \leq N \leq 10^5\)) và \(M\) (\(1 \leq M \leq 10^5\)). Mỗi dòng trong \(M\) dòng tiếp theo chứa một ký tự là S hoặc D, theo sau là hai số nguyên trong phạm vi \(1 \ldots N\), mô tả cặp đồng cỏ yêu thích của một con bò của Farmer John. Nếu ký tự là S, dòng này biểu thị một con bò cần cùng một loại cỏ trên hai đồng cỏ yêu thích. Nếu ký tự là D, dòng này biểu thị một con bò cần hai loại cỏ khác nhau.

Dữ liệu ra

In ra số cách Farmer John có thể trồng cỏ trên \(N\) đồng cỏ. Hãy viết đáp án ở dạng nhị phân.

Ví dụ

3 2
S 1 2
D 3 2

10

Nguồn

USACO 2019 February Contest, Silver — The Great Revegetation

Tác giả: Dhruv Rohatgi và Brian Dean.