USACO 2012 - US Open - Hạng Vàng

Như chúng ta đều biết, bò Bessie không thích gì hơn việc gây rắc rối trong trang trại. Để ngăn cô gây quá nhiều phiền toái, Farmer John quyết định dùng một sợi dây dài buộc Bessie vào hàng rào. Khi nhìn từ trên xuống, hàng rào gồm \(N\) cọc (\(1 \le N \le 10\)) được bố trí dọc theo một đường thẳng đứng, còn vị trí \((bx, by)\) của Bessie nằm bên phải đường thẳng đứng này. Sợi dây FJ dùng để buộc Bessie được mô tả bằng một dãy gồm \(M\) đoạn thẳng (\(3 \le M \le 10\,000\)), trong đó đoạn đầu tiên bắt đầu tại vị trí của Bessie và đoạn cuối cùng kết thúc tại vị trí của Bessie. Không có cọc rào nào nằm trên bất kỳ đoạn thẳng nào trong số này. Tuy nhiên, các đoạn thẳng có thể cắt nhau và nhiều đoạn thẳng có thể trùng nhau tại các đầu mút.

Dưới đây là một ví dụ về quang cảnh khi nhìn từ trên xuống:

Để giúp Bessie trốn thoát, những con bò còn lại đã lấy trộm một chiếc cưa từ nhà kho. Hãy xác định số cọc rào ít nhất mà chúng phải cưa và dỡ bỏ để Bessie có thể giật dây thoát ra (nghĩa là cô có thể chạy sang phải mà sợi dây không mắc vào bất kỳ cọc rào nào).

Tất cả tọa độ \((x,y)\) trong dữ liệu vào (của cọc rào, Bessie và các đầu mút đoạn thẳng) đều nằm trong khoảng từ 0 đến \(10\,000\). Mọi cọc rào có cùng tọa độ \(x\), và \(bx\) lớn hơn giá trị này.

Dữ liệu vào

• Dòng 1 chứa bốn số nguyên \(N\), \(M\), \(bx\) và \(by\), cách nhau bởi dấu cách.
• Các dòng từ 2 đến \(1+N\): Dòng \(i+1\) chứa tọa độ \(x\) và \(y\) của cọc rào \(i\), cách nhau bởi dấu cách.
• Các dòng từ \(2+N\) đến \(2+N+M\): Mỗi dòng trong số \(M+1\) dòng này lần lượt chứa tọa độ \(x\) và \(y\) của một điểm trên sợi dây, cách nhau bởi dấu cách. Điểm đầu tiên và điểm cuối cùng luôn trùng với vị trí \((bx, by)\) của Bessie.

Dữ liệu ra

• Dòng 1 chứa số cọc ít nhất cần dỡ bỏ để Bessie có thể trốn thoát bằng cách chạy sang phải.

Ví dụ

2 10 6 1
2 3
2 1
6 1
2 4
1 1
2 0
3 1
1 3
5 4
3 0
0 1
3 2
6 1

1

Nguồn

USACO 2012 US Open, Gold Division — Tied Down

Tác giả: Brian Dean, 2012.

Khi không vắt sữa bò, xếp các kiện cỏ khô, cho đàn bò xếp hàng hay dựng hàng rào, Farmer John thích ngồi xuống đọc một cuốn sách hay. Qua nhiều năm, ông đã sưu tầm được \(N\) cuốn sách (\(1 \le N \le 100\,000\)) và muốn đóng một bộ giá sách mới để chứa tất cả chúng.

Mỗi cuốn sách \(i\) có chiều rộng \(W(i)\) và chiều cao \(H(i)\). Các cuốn sách phải được xếp lên các tầng giá theo đúng thứ tự; chẳng hạn, tầng đầu tiên phải chứa các cuốn từ 1 đến \(k\) với một giá trị \(k\) nào đó, tầng thứ hai phải bắt đầu bằng cuốn \(k+1\), và cứ tiếp tục như vậy. Tổng chiều rộng trên mỗi tầng giá không được vượt quá \(L\) (\(1 \le L \le 1\,000\,000\,000\)). Chiều cao của một tầng giá bằng chiều cao của cuốn sách cao nhất trên tầng đó, còn chiều cao của toàn bộ bộ giá sách bằng tổng chiều cao của tất cả các tầng vì chúng được xếp chồng theo phương thẳng đứng.

Hãy giúp FJ tính chiều cao nhỏ nhất có thể của toàn bộ bộ giá sách.

Dữ liệu vào

• Dòng 1 chứa hai số nguyên \(N\) và \(L\), cách nhau bởi dấu cách.
• Các dòng từ 2 đến \(1+N\): Dòng \(i+1\) chứa hai số nguyên \(H(i)\) và \(W(i)\), cách nhau bởi dấu cách (\(1 \le H(i) \le 1\,000\,000\); \(1 \le W(i) \le L\)).

Dữ liệu ra

• Dòng 1 chứa tổng chiều cao nhỏ nhất có thể của bộ giá sách.

Ví dụ

5 10
5 7
9 2
8 5
13 2
3 8

21

Nguồn

USACO 2012 US Open, Gold Division — Bookshelf

Tác giả: Neal Wu / Traditional, 2012.

Farmer John sở hữu \(N\) con bò (\(2 \le N \le 20\)), trong đó mỗi ngày con bò \(i\) cho \(M(i)\) đơn vị sữa (\(1 \le M(i) \le 100\,000\,000\)). FJ muốn tinh giản công việc vắt sữa đàn bò hằng ngày nên lắp đặt một máy vắt sữa hoàn toàn mới trong chuồng. Thật không may, chiếc máy này lại quá nhạy: nó chỉ hoạt động đúng nếu những con bò ở phía bên trái chuồng có tổng sản lượng sữa chính xác bằng tổng sản lượng sữa của những con bò ở phía bên phải chuồng!

Ta gọi một tập con của đàn bò là "cân bằng" nếu có thể chia nó thành hai nhóm có tổng sản lượng sữa bằng nhau. Vì chỉ một tập con cân bằng mới có thể làm máy vắt sữa hoạt động, FJ muốn biết có bao nhiêu tập con trong số \(N\) con bò của mình là cân bằng. Hãy giúp ông tính số lượng này.

Dữ liệu vào

• Dòng 1 chứa số nguyên \(N\).
• Các dòng từ 2 đến \(1+N\): Dòng \(i+1\) chứa \(M(i)\).

Dữ liệu ra

• Dòng 1 chứa số tập con cân bằng của đàn bò.

Ví dụ

4
1
2
3
4

3

Nguồn

USACO 2012 US Open, Gold Division — Balanced Cow Subsets

Tác giả: Neal Wu, 2012.