USACO 2014 - Tháng 1 - Hạng Vàng

Ném đá trên băng dành cho bò là một môn thể thao mùa lạnh phổ biến được thi đấu tại Moolympics.

Tương tự môn ném đá trên băng thông thường, môn thể thao này có hai đội, mỗi đội trượt \(N\) tảng đá nặng (\(3 \le N \le 50\,000\)) trên một sân băng. Khi trận đấu kết thúc, có \(2N\) tảng đá trên sân, mỗi tảng nằm tại một điểm phân biệt trong mặt phẳng hai chiều.

Tuy nhiên, cách tính điểm trong phiên bản dành cho bò khá kỳ lạ. Một tảng đá được coi là bị "bắt" nếu nó nằm bên trong một tam giác có ba đỉnh là các tảng đá của đối phương; một tảng đá nằm trên biên của tam giác như vậy cũng được tính là bị bắt. Điểm của một đội là số tảng đá của đối phương bị bắt.

Cho vị trí của tất cả \(2N\) tảng đá, hãy tính tỉ số chung cuộc của một trận ném đá trên băng dành cho bò.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên là tọa độ \(x\) và \(y\) của một tảng đá thuộc đội A; mỗi tọa độ nằm trong đoạn từ \(-40\,000\) đến \(+40\,000\).
• \(N\) dòng cuối, mỗi dòng chứa hai số nguyên là tọa độ \(x\) và \(y\) của một tảng đá thuộc đội B; mỗi tọa độ nằm trong đoạn từ \(-40\,000\) đến \(+40\,000\).

Ràng buộc

• \(3 \le N \le 50\,000\).
• Mỗi tọa độ nằm trong đoạn từ \(-40\,000\) đến \(+40\,000\).
• Tất cả \(2N\) tảng đá nằm tại các điểm phân biệt.

Dữ liệu ra

In ra hai số nguyên cách nhau bởi một dấu cách, lần lượt là điểm của đội A và đội B.

Ví dụ

4
0 0
0 2
2 0
2 2
1 1
1 10
-10 3
10 3

1 2

Nguồn

USACO 2014 January Contest, Gold — Cow Curling

Tác giả: Brian Dean, 2014.

Farmer John đang giúp biến cánh đồng rộng lớn của mình thành một đường trượt tuyết cho kỳ Moolympics mùa đông sắp tới. Cánh đồng có kích thước \(M \times N\) (\(1 \le M,N \le 100\)), và trạng thái cuối cùng mong muốn của nó được mô tả bằng một lưới ký tự \(M \times N\), chẳng hạn như:

RSRSSS
RSRSSS
RSRSSS

Mỗi ký tự mô tả cách tuyết trong một ô vuông đơn vị của cánh đồng cần được xử lý: R biểu thị tuyết "gồ ghề" (rough) hoặc S biểu thị tuyết "nhẵn" (smooth) (ban tổ chức Moolympics cho rằng một đường trượt sẽ thú vị hơn nếu có cả những vùng gồ ghề lẫn những vùng nhẵn).

Để xây dựng đường trượt mong muốn, Farmer John dự định cải tiến máy kéo để nó có thể dập bất kỳ vùng \(B \times B\) nào trên cánh đồng (\(B \le M\), \(B \le N\)) thành toàn bộ tuyết nhẵn hoặc toàn bộ tuyết gồ ghề. Vì việc thiết lập lại máy kéo giữa hai lần dập tốn rất nhiều thời gian, FJ muốn chọn \(B\) lớn nhất có thể. Với \(B=1\), hiển nhiên ông có thể tạo ra đường trượt mong muốn bằng cách dập từng ô riêng lẻ thành R hoặc S theo yêu cầu. Tuy nhiên, với các giá trị \(B\) lớn hơn, thiết kế đường trượt mong muốn có thể không còn tạo được. Mọi ô vuông đơn vị của đường trượt đều phải được máy kéo của FJ dập ít nhất một lần; không ô nào được phép giữ nguyên trạng thái mặc định.

Hãy giúp FJ xác định giá trị \(B\) lớn nhất mà ông có thể sử dụng thành công.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(M\) và \(N\) cách nhau bởi một dấu cách.
• \(M\) dòng tiếp theo, mỗi dòng gồm đúng \(N\) ký tự, mỗi ký tự là R hoặc S, mô tả thiết kế đường trượt tuyết mong muốn.

Ràng buộc

• \(1 \le M,N \le 100\).

Dữ liệu ra

In ra giá trị \(B\) lớn nhất mà Farmer John có thể sử dụng để tạo ra đúng thiết kế đường trượt mong muốn.

Ví dụ

3 6
RSRSSS
RSRSSS
RSRSSS

3

Nguồn

USACO 2014 January Contest, Gold — Building a Ski Course

Tác giả: Nathan Pinsker, 2014.

Đường trượt tuyết băng đồng tại Moolympics mùa đông được mô tả bằng một lưới độ cao \(M \times N\) (\(1 \le M,N \le 500\)), trong đó mỗi độ cao nằm trong đoạn từ \(0\) đến \(1\,000\,000\,000\).

Một số ô trong lưới được chỉ định làm điểm xuất phát của đường trượt. Ban tổ chức Moolympics muốn gán một mức độ khó cho mỗi điểm xuất phát. Mức độ khó của một điểm xuất phát \(P\) là giá trị nhỏ nhất có thể của \(D\) sao cho một cô bò bắt đầu tại \(P\) có thể đi đến tổng cộng ít nhất \(T\) ô trong lưới (\(1 \le T \le MN\)), với điều kiện cô chỉ có thể di chuyển từ một ô sang ô kề nếu chênh lệch tuyệt đối giữa độ cao của hai ô không vượt quá \(D\). Hai ô được coi là kề nhau nếu một ô nằm ngay phía bắc, nam, đông hoặc tây của ô kia.

Hãy giúp ban tổ chức tính mức độ khó của từng điểm xuất phát.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên \(M\), \(N\) và \(T\).
• \(M\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên là độ cao của các ô.
• \(M\) dòng cuối, mỗi dòng chứa \(N\) giá trị bằng \(0\) hoặc \(1\); giá trị \(1\) cho biết ô tương ứng là một điểm xuất phát.

Ràng buộc

• \(1 \le M,N \le 500\).
• \(1 \le T \le MN\).
• Mỗi độ cao nằm trong đoạn từ \(0\) đến \(1\,000\,000\,000\).

Dữ liệu ra

In ra tổng mức độ khó của tất cả các điểm xuất phát. Lưu ý rằng tổng này có thể không biểu diễn được bằng số nguyên \(32\) bit, mặc dù từng mức độ khó riêng lẻ thì có thể.

Ví dụ

3 5 10
20 21 18 99 5
19 22 20 16 17
18 17 40 60 80
1 0 0 0 0
0 0 0 0 0
0 0 0 0 1

24

Nguồn

USACO 2014 January Contest, Gold — Ski Course Rating

Tác giả: William Hu và Brian Dean, 2014.