USACO 2013 - Tháng 1 - Hạng Bạc - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	USACO 2013 - Painting the Fence	100 (p)	4.0s	512M
2	USACO 2013 - Square Overlap	100 (p)	4.0s	512M
3	USACO 2013 - Party Invitations	100 (p)	4.0s	512M

1. USACO 2013 - Painting the Fence

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Farmer John đã nghĩ ra một phương pháp tuyệt vời để sơn hàng rào dài cạnh chuồng của mình (hãy xem hàng rào như một trục số một chiều). Ông chỉ việc gắn một chiếc chổi sơn vào Bessie, con bò yêu thích của mình, rồi thong thả đi uống một ly nước lạnh trong khi Bessie đi tới đi lui dọc hàng rào và quét sơn lên mọi đoạn hàng rào mà cô đi qua.

Bessie bắt đầu tại vị trí \(0\) trên hàng rào và thực hiện một chuỗi \(N\) bước di chuyển (\(1 \le N \le 100\,000\)). Chẳng hạn, bước 10 L nghĩa là Bessie di chuyển \(10\) đơn vị sang trái, còn 15 R nghĩa là Bessie di chuyển \(15\) đơn vị sang phải. Với danh sách tất cả các bước di chuyển của Bessie, FJ muốn biết phần nào của hàng rào được phủ ít nhất \(K\) lớp sơn. Trong suốt hành trình, Bessie sẽ cách gốc tọa độ không quá \(1\,000\,000\,000\) đơn vị.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\), cách nhau bởi dấu cách.
\(N\) dòng tiếp theo, mỗi dòng mô tả một bước di chuyển của Bessie (chẳng hạn 15 L).

Dữ liệu ra

In ra tổng độ dài được phủ ít nhất \(K\) lớp sơn.

Ví dụ

Ví dụ 1

Input

6 2
2 R
6 L
1 R
8 L
1 R
2 R

Output

Giải thích

Bessie bắt đầu tại vị trí \(0\) và di chuyển \(2\) đơn vị sang phải, sau đó \(6\) đơn vị sang trái, \(1\) đơn vị sang phải, \(8\) đơn vị sang trái và cuối cùng \(3\) đơn vị sang phải. FJ muốn biết tổng độ dài được phủ ít nhất \(2\) lớp sơn.

Có \(6\) đơn vị độ dài được phủ ít nhất \(2\) lớp sơn, bao gồm các khoảng \([-11,-8]\), \([-4,-3]\) và \([0,2]\).

Nguồn

USACO 2013 January Contest, Silver — Problem 1: Painting the Fence

Tác giả đề: Brian Dean, 2012.

2. USACO 2013 - Square Overlap

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Farmer John đang dự định xây dựng \(N\) đồng cỏ hình vuông có hàng rào bao quanh trong trang trại của mình (\(2 \le N \le 50\,000\)), mỗi đồng cỏ có kích thước chính xác \(K \times K\) (\(1 \le K \le 1\,000\,000\)). Đồng cỏ thứ \(i\) có tâm tại điểm \((x_i, y_i)\) với các tọa độ nguyên trong khoảng từ \(-1\,000\,000\) đến \(1\,000\,000\). Tuy nhiên, vì vội vàng hoàn thành kế hoạch, FJ nhận ra rằng ông có thể đã vô tình đặt hai đồng cỏ ở những vị trí chồng lấn nhau (chồng lấn ở đây nghĩa là hai đồng cỏ có chung một phần diện tích dương). Không có hai đồng cỏ nào có cùng một tâm.

Cho vị trí của mỗi đồng cỏ hình vuông dự kiến, hãy giúp FJ tính diện tích chung của hai đồng cỏ chồng lấn. In ra \(0\) nếu không có hai hình vuông nào chồng lấn, và in ra \(-1\) nếu có nhiều hơn một cặp đồng cỏ chồng lấn.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\), cách nhau bởi dấu cách. Giá trị \(K\) được đảm bảo là số chẵn.
\(N\) dòng tiếp theo: dòng thứ \(i\) chứa hai số nguyên \(x_i\) và \(y_i\), mô tả tâm của đồng cỏ thứ \(i\).

Dữ liệu ra

In ra diện tích chung của hai hình vuông chồng lấn. In ra \(0\) nếu không có hai hình vuông nào chồng lấn, và in ra \(-1\) nếu có nhiều hơn một cặp đồng cỏ chồng lấn.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Có \(4\) hình vuông, mỗi hình có kích thước \(6 \times 6\). Hình vuông đầu tiên có tâm tại \((0,0)\), và các hình còn lại cũng lần lượt có tâm như trong dữ liệu vào.

Đồng cỏ số \(1\) và số \(3\) chồng lấn trên một diện tích bằng \(20\) đơn vị vuông.

Nguồn

USACO 2013 January Contest, Silver — Problem 2: Square Overlap

Tác giả đề: Brian Dean, 2013.

3. USACO 2013 - Party Invitations

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Farmer John tổ chức một bữa tiệc và muốn mời một số con bò của mình để cho chúng thấy ông quan tâm đến đàn bò đến nhường nào. Tuy nhiên, ông cũng muốn mời số lượng bò ít nhất có thể, bởi ông vẫn nhớ rất rõ thảm họa xảy ra trong lần gần nhất ông mời quá nhiều bò đến dự tiệc.

Trong đàn bò của FJ, có một số nhóm bạn rất khó tách rời. Với bất kỳ nhóm nào như vậy (giả sử có kích thước \(k\)), nếu FJ mời ít nhất \(k-1\) con bò trong nhóm đến dự tiệc thì ông cũng phải mời con bò cuối cùng, qua đó mời toàn bộ nhóm. Các nhóm có thể có kích thước bất kỳ và thậm chí có thể giao nhau, mặc dù không có hai nhóm nào chứa chính xác cùng một tập hợp thành viên. Tổng kích thước của tất cả các nhóm không vượt quá \(250\,000\).

Cho các nhóm trong đàn bò của FJ, hãy xác định số lượng bò tối thiểu mà FJ có thể mời đến bữa tiệc nếu ông quyết định rằng trước tiên chắc chắn phải mời bò số \(1\) (các con bò được đánh số thuận tiện từ \(1\) đến \(N\), với \(N\) không vượt quá \(1\,000\,000\)).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) (số lượng bò) và \(G\) (số lượng nhóm), cách nhau bởi dấu cách.
\(G\) dòng tiếp theo, mỗi dòng mô tả một nhóm bò. Dòng bắt đầu bằng một số nguyên cho biết kích thước \(S\) của nhóm, theo sau là \(S\) con bò trong nhóm (mỗi con được biểu diễn bằng một số nguyên trong khoảng từ \(1\) đến \(N\)).

Dữ liệu ra

In ra số lượng bò tối thiểu mà FJ có thể mời đến bữa tiệc.

Ví dụ

Ví dụ 1

Input

10 4
2 1 3
2 3 4
6 1 2 3 4 6 7
4 4 3 2 1

Output

Giải thích

Có \(10\) con bò và \(4\) nhóm. Nhóm đầu tiên gồm bò \(1\) và bò \(3\), và các nhóm còn lại cũng lần lượt gồm các con bò như trong dữ liệu vào.

Ngoài bò số \(1\), FJ phải mời bò số \(3\) (do ràng buộc của nhóm đầu tiên), bò số \(4\) (do ràng buộc của nhóm thứ hai), và cả bò số \(2\) (do ràng buộc của nhóm cuối cùng).

Nguồn

USACO 2013 January Contest, Silver — Problem 3: Party Invitations

Tác giả đề: Travis Hance, 2012.