USACO 2012 - US Open - Hạng Bạc

Một sự thật ít người biết về loài bò là chúng rất thích giải đố! Nhân dịp sinh nhật Bessie, Farmer John tặng cô một câu đố cơ khí thú vị để giải. Câu đố gồm ba vật thể rắn, mỗi vật thể được tạo thành từ các ô vuông đơn vị \(1 \times 1\) dán với nhau. Mỗi vật thể là một hình "liên thông", theo nghĩa là ta có thể đi từ một ô vuông bất kỳ của vật thể đến bất kỳ ô vuông nào khác trên cùng vật thể bằng cách bước qua các ô thuộc vật thể theo hướng bắc, nam, đông hoặc tây.

Một vật thể có thể được di chuyển bằng cách trượt nó lặp đi lặp lại một đơn vị về phía bắc, nam, đông hoặc tây. Mục tiêu của câu đố là di chuyển các vật thể sao cho chúng tách rời nhau, tức là các hình chữ nhật bao của chúng không còn có bất kỳ phần giao nào với diện tích dương. Với hình dạng và vị trí của ba vật thể, nhiệm vụ của bạn là giúp Bessie xác định số lần trượt riêng lẻ tối thiểu cần thiết để tách các vật thể ra.

Dữ liệu vào

• Dòng 1 chứa ba số nguyên \(N1\), \(N2\) và \(N3\), cách nhau bởi dấu cách, lần lượt mô tả số ô vuông đơn vị tạo nên vật thể 1, 2 và 3.
• Các dòng từ 2 đến \(1+N1\): Mỗi dòng mô tả vị trí \((x,y)\) của góc tây nam của một ô vuông thuộc vật thể 1. Mọi tọa độ đều nằm trong khoảng từ 0 đến 9.
• Các dòng từ \(2+N1\) đến \(1+N1+N2\): Mỗi dòng mô tả vị trí \((x,y)\) của góc tây nam của một ô vuông thuộc vật thể 2. Mọi tọa độ đều nằm trong khoảng từ 0 đến 9.
• Các dòng từ \(2+N1+N2\) đến \(1+N1+N2+N3\): Mỗi dòng mô tả vị trí \((x,y)\) của góc tây nam của một ô vuông thuộc vật thể 3. Mọi tọa độ đều nằm trong khoảng từ 0 đến 9.

Dữ liệu ra

• Dòng 1 chứa số lần di chuyển tối thiểu cần thiết để tách ba vật thể, hoặc -1 nếu không thể tách chúng ra.

Ví dụ

12 3 5
0 0
1 0
2 0
3 0
3 1
0 1
0 2
0 3
0 4
1 4
2 4
3 4
2 1
2 2
1 2
2 3
3 3
4 3
4 4
4 2

5

Nguồn

USACO 2012 US Open, Silver Division — Unlocking Blocks (Silver)

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 2\,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, Silver Division — Bookshelf (Silver)

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

Chán đua ngựa, Farmer John quyết định nghiên cứu tính khả thi của môn đua bò. Ông cho \(N\) con bò (\(1 \le N \le 100\,000\)) chạy một cuộc đua gồm \(L\) vòng quanh đường đua hình tròn có độ dài \(C\). Tất cả bò xuất phát tại cùng một điểm trên đường đua và chạy với các vận tốc khác nhau; cuộc đua kết thúc khi con bò nhanh nhất đã chạy đủ tổng quãng đường \(LC\).

FJ nhận thấy nhiều lần một con bò vượt qua một con khác và tự hỏi loại "sự kiện vượt nhau" này xảy ra bao nhiêu lần trong toàn bộ cuộc đua. Cụ thể hơn, một sự kiện vượt nhau được xác định bởi một cặp bò \((x,y)\) và một thời điểm \(t\) (nhỏ hơn hoặc bằng thời điểm kết thúc cuộc đua), tại đó bò \(x\) vượt lên trước bò \(y\). Hãy giúp FJ đếm tổng số sự kiện vượt nhau trong toàn bộ cuộc đua.

Dữ liệu vào

• Dòng 1 chứa ba số nguyên \(N\), \(L\) và \(C\), cách nhau bởi dấu cách (\(1 \le L,C \le 25\,000\)).
• Các dòng từ 2 đến \(1+N\): Dòng \(i+1\) chứa vận tốc của con bò \(i\), là một số nguyên trong khoảng từ 1 đến \(1\,000\,000\).

Dữ liệu ra

• Dòng 1 chứa tổng số sự kiện vượt nhau trong toàn bộ cuộc đua.

Ví dụ

4 2 100
20
100
70
1

4

Nguồn

USACO 2012 US Open, Silver Division — Running Laps

Tác giả: Brian Dean, 2012.