USACO 2013 - Tháng 12 - Hạng Đồng

Farmer John đã ghi chép chi tiết về những con bò khi chúng vào chuồng để vắt sữa. Mỗi giờ, một nhóm 3 con bò vào chuồng và Farmer John ghi lại tên của chúng. Ví dụ, trong khoảng thời gian 5 giờ, ông có thể ghi lại danh sách sau, trong đó mỗi dòng tương ứng với một nhóm đi vào chuồng:

BESSIE ELSIE MATILDA
FRAN BESSIE INGRID
BESSIE ELSIE MATILDA
MATILDA INGRID FRAN
ELSIE BESSIE MATILDA

Farmer John nhận thấy cùng một nhóm bò có thể xuất hiện nhiều lần trong danh sách; trong ví dụ trên, nhóm gồm BESSIE, ELSIE và MATILDA xuất hiện ba lần (mặc dù Farmer John không nhất thiết ghi tên chúng theo cùng một thứ tự mỗi lần chúng vào chuồng).

Hãy giúp Farmer John đếm số lần xuất hiện của nhóm đi vào chuồng thường xuyên nhất.

Dữ liệu vào

• Dòng 1 chứa số giờ \(N\) mà Farmer John ghi chép (\(1 \le N \le 1000\)).
• Các dòng \(2..1+N\): mỗi dòng chứa tên của ba con bò, cách nhau bởi dấu cách. Mỗi tên dài từ 1 đến 10 ký tự và chỉ sử dụng các chữ cái từ A đến Z.

Dữ liệu ra

• Dòng 1 chứa số lần xuất hiện của nhóm đi vào chuồng thường xuyên nhất.

Ví dụ

5
BESSIE ELSIE MATILDA
FRAN BESSIE INGRID
BESSIE ELSIE MATILDA
MATILDA INGRID FRAN
ELSIE BESSIE MATILDA

3

Nguồn

USACO 2013 December Contest, Bronze — Problem 1: Record Keeping

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

\(N\) con bò của Farmer John (\(3 \le N \le 1000\)) đang đứng thành một hàng, mỗi con ở một vị trí khác nhau trên trục số. Chúng đang luyện tập ném bóng chày để chuẩn bị cho một trận đấu quan trọng với những con bò ở trang trại bên cạnh.

Trong lúc quan sát, Farmer John thấy một nhóm ba con bò \((X,Y,Z)\) thực hiện thành công hai cú ném. Bò \(X\) ném bóng cho bò \(Y\) ở bên phải nó, sau đó bò \(Y\) ném bóng cho bò \(Z\) ở bên phải nó. Farmer John nhận thấy cú ném thứ hai đi xa ít nhất bằng và không quá gấp đôi cú ném thứ nhất. Hãy đếm số bộ ba bò \((X,Y,Z)\) mà Farmer John có thể đã quan sát.

Dữ liệu vào

• Dòng 1 chứa số bò \(N\).
• Các dòng \(2..1+N\): mỗi dòng chứa vị trí nguyên của một con bò, nằm trong khoảng \(0..100\,000\,000\).

Dữ liệu ra

• Dòng 1 chứa số bộ ba bò \((X,Y,Z)\) sao cho \(Y\) ở bên phải \(X\), \(Z\) ở bên phải \(Y\), và khoảng cách từ \(Y\) đến \(Z\) nằm trong đoạn từ \(XY\) đến \(2XY\) (kể cả hai đầu), trong đó \(XY\) biểu thị khoảng cách từ \(X\) đến \(Y\).

Ví dụ

5
3
1
10
7
4

4

Nguồn

USACO 2013 December Contest, Bronze — Problem 2: Cow Baseball

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

Sở thích tiến hành các thí nghiệm vật lý năng lượng cao vào cuối tuần của Farmer John đã gây ra hậu quả ngoài ý muốn: \(N\) hố giun (\(2 \le N \le 12\), \(N\) chẵn) xuất hiện trên trang trại của ông, mỗi hố nằm tại một điểm phân biệt trên bản đồ hai chiều của trang trại.

Theo tính toán, Farmer John biết rằng các hố giun sẽ tạo thành \(N/2\) cặp liên kết. Ví dụ, nếu hố giun \(A\) và \(B\) được liên kết thành một cặp thì mọi vật thể đi vào hố giun \(A\) sẽ đi ra từ hố giun \(B\) theo cùng hướng chuyển động; tương tự, mọi vật thể đi vào hố giun \(B\) sẽ đi ra từ hố giun \(A\) theo cùng hướng. Điều này có thể dẫn đến những hậu quả khá khó chịu. Chẳng hạn, giả sử có hai hố giun được ghép cặp là \(A\) tại \((0,0)\) và \(B\) tại \((1,0)\), đồng thời cô bò Bessie bắt đầu ở vị trí \((1/2,0)\) và di chuyển theo chiều \(+x\). Bessie sẽ đi vào hố giun \(B\), đi ra từ \(A\), rồi lại đi vào \(B\), và cứ tiếp tục như vậy, khiến cô bị mắc kẹt trong một chu trình vô hạn!

Farmer John biết chính xác vị trí của từng hố giun trên trang trại. Ông biết rằng Bessie luôn đi theo chiều \(+x\), nhưng không nhớ hiện tại cô đang ở đâu. Hãy giúp Farmer John đếm số cách ghép cặp các hố giun sao cho Bessie có thể bị mắc kẹt trong một chu trình vô hạn nếu cô bắt đầu tại một vị trí không may mắn.

Dữ liệu vào

• Dòng đầu tiên chứa số hố giun \(N\).
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách, mô tả tọa độ \((x,y)\) của một hố giun.

Ràng buộc

• \(2 \le N \le 12\) và \(N\) chẵn.
• Mỗi tọa độ nằm trong đoạn từ \(0\) đến \(1\,000\,000\,000\).
• Các hố giun nằm tại những điểm đôi một phân biệt.

Dữ liệu ra

In ra số cách ghép cặp các hố giun sao cho Bessie có thể bị mắc kẹt trong một chu trình khi đi theo chiều \(+x\) từ một vị trí bắt đầu nào đó.

Ví dụ

4
0 0
1 0
1 1
0 1

2

Nguồn

USACO 2013 December Contest, Bronze — Problem 3: Wormholes

Tác giả: Brian Dean, 2013.