USACO 2018 - US Open - Hạng Đồng

Bác nông dân John sở hữu 26 cô bò. Thật tình cờ, tên của chúng bắt đầu bằng các chữ cái khác nhau trong bảng chữ cái, nên ông thường gọi mỗi cô bò bằng chữ cái đầu trong tên của cô ấy — một ký tự thuộc khoảng \(A \ldots Z\).

Gần đây, đàn bò rất say mê trò cờ ca-rô, nhưng vì không thích việc mỗi lần chỉ có hai cô bò được chơi nên chúng đã sáng tạo ra một biến thể cho phép nhiều cô bò cùng chơi! Tương tự cờ ca-rô thông thường, trò chơi diễn ra trên một bảng \(3 \times 3\). Tuy nhiên, thay vì chỉ dùng X và O, mỗi ô được đánh dấu bằng một ký tự duy nhất thuộc khoảng \(A \ldots Z\), biểu thị chữ cái đầu của cô bò chiếm ô đó.

Một bảng đấu có thể trông như sau:

COW
XXO
ABC

Đàn bò điền đủ cả chín ô rồi mới bối rối không biết phải xác định ai thắng cuộc. Rõ ràng, giống như trong cờ ca-rô thông thường, nếu một cô bò chiếm trọn một hàng, một cột hoặc một đường chéo thì cô ấy có thể tự mình tuyên bố chiến thắng. Tuy nhiên, vì đàn bò cho rằng điều này khó xảy ra khi có nhiều người chơi hơn, chúng quyết định cho phép lập đội gồm hai cô bò. Một đội hai cô bò có thể tuyên bố chiến thắng nếu một hàng, một cột hoặc một đường chéo chỉ gồm các ký tự của hai cô bò trong đội, đồng thời các ký tự của cả hai cô bò đều xuất hiện trên hàng, cột hoặc đường chéo đó, chứ không chỉ ký tự của một cô.

Hãy giúp đàn bò xác định có bao nhiêu cá nhân và bao nhiêu đội hai cô bò có thể tuyên bố chiến thắng. Lưu ý rằng cùng một ô trên bảng có thể được sử dụng trong nhiều cách tuyên bố chiến thắng khác nhau.

Dữ liệu vào

Dữ liệu vào gồm ba dòng, mỗi dòng chứa ba ký tự thuộc khoảng \(A \ldots Z\).

Dữ liệu ra

Dữ liệu ra gồm hai dòng. Trên dòng đầu tiên, in số cô bò có thể tự mình tuyên bố chiến thắng. Trên dòng thứ hai, in số đội gồm hai cô bò có thể tuyên bố chiến thắng.

Ví dụ

COW
XXO
ABC

0
2

Nguồn

USACO 2018 US Open Contest, Bronze — Team Tic Tac Toe

Tác giả bài toán: Brian Dean.

\(N\) cô bò của bác nông dân John (\(2 \leq N \leq 100\)), như thường lệ được đánh số thuận tiện từ \(1 \ldots N\), tình cờ có quá nhiều thời gian rảnh. Vì vậy, chúng đã xây dựng một cấu trúc xã hội phức tạp liên quan đến thứ tự bác nông dân John vắt sữa chúng vào mỗi buổi sáng. Sau nhiều tuần nghiên cứu, ông phát hiện cấu trúc này dựa trên hai đặc điểm chính.

Thứ nhất, do hệ thống thứ bậc xã hội của đàn bò, một số cô bò nhất quyết phải được vắt sữa trước những cô bò khác dựa trên địa vị xã hội của từng cô. Ví dụ, nếu bò 3 có địa vị cao nhất, bò 2 có địa vị trung bình và bò 5 có địa vị thấp, thì bò 3 phải được vắt sữa sớm nhất, sau đó đến bò 2 và cuối cùng là bò 5.

Thứ hai, một số cô bò chỉ chấp nhận được vắt sữa tại một vị trí nhất định trong thứ tự. Ví dụ, bò 4 có thể nhất quyết đòi được vắt sữa ở vị trí thứ hai trong toàn đàn.

May mắn thay, bác nông dân John luôn có thể vắt sữa đàn bò theo một thứ tự thỏa mãn tất cả các điều kiện này.

Không may, gần đây bò 1 bị ốm, nên bác nông dân John muốn vắt sữa cô ấy sớm nhất có thể để cô ấy trở về chuồng và nghỉ ngơi đầy đủ. Hãy giúp ông xác định vị trí sớm nhất mà bò 1 có thể xuất hiện trong thứ tự vắt sữa.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(M\) (\(1 \leq M < N\)) và \(K\) (\(1 \leq K < N\)), cho biết bác nông dân John có \(N\) cô bò, \(M\) cô trong số đó đã tự sắp xếp thành một hệ thống thứ bậc xã hội, và \(K\) cô yêu cầu được vắt sữa tại một vị trí cụ thể trong thứ tự. Dòng tiếp theo chứa \(M\) số nguyên đôi một khác nhau \(m_i\) (\(1 \leq m_i \leq N\)). Các cô bò trên dòng này phải được vắt sữa theo đúng thứ tự xuất hiện trên dòng. Mỗi dòng trong \(K\) dòng tiếp theo chứa hai số nguyên \(c_i\) (\(1 \leq c_i \leq N\)) và \(p_i\) (\(1 \leq p_i \leq N\)), cho biết bò \(c_i\) phải được vắt sữa ở vị trí \(p_i\).

Bảo đảm rằng với các ràng buộc này, bác nông dân John có thể xây dựng một thứ tự vắt sữa hợp lệ.

Dữ liệu ra

In ra vị trí sớm nhất mà bò 1 có thể đứng trong thứ tự vắt sữa.

Ví dụ

6 3 2
4 5 6
5 3
3 1

4

Nguồn

USACO 2018 US Open Contest, Bronze — Milking Order

Tác giả bài toán: Jay Leeds.

Bác nông dân John sở hữu một trang trại gia đình được truyền lại qua nhiều thế hệ, cùng một đàn bò có nguồn gốc gia đình cũng có thể được truy ngược qua nhiều thế hệ trên chính trang trại ấy. Khi xem lại các hồ sơ cũ, ông tò mò muốn biết những cô bò trong đàn hiện tại có quan hệ với nhau như thế nào. Hãy giúp ông thực hiện việc này!

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa \(N\) (\(1 \leq N \leq 100\)), theo sau là tên của hai cô bò. Mỗi tên bò là một xâu gồm không quá 10 chữ cái in hoa (\(A \ldots Z\)). Bác nông dân John muốn biết mối quan hệ giữa hai cô bò trên dòng này.

Mỗi dòng trong \(N\) dòng tiếp theo chứa hai tên bò \(X\) và \(Y\), cho biết \(X\) là mẹ của \(Y\).

Dữ liệu ra

In ra một dòng cho biết mối quan hệ giữa hai cô bò được nêu trên dòng đầu tiên của dữ liệu vào. Để đơn giản, trong các trường hợp dưới đây ta gọi hai cô bò này là BESSIE và ELSIE. Các kiểu quan hệ có thể có là:

• In SIBLINGS nếu BESSIE và ELSIE có cùng mẹ.
• BESSIE có thể là hậu duệ trực hệ của ELSIE, nghĩa là ELSIE là mẹ, bà, cụ, kỵ, v.v. của BESSIE. Trong trường hợp này, in ELSIE is the (relation) of BESSIE, trong đó (relation) là quan hệ thích hợp, chẳng hạn great-great-grand-mother.
• Nếu ELSIE là con của một tổ tiên của BESSIE, đồng thời bản thân ELSIE không phải là tổ tiên hoặc chị em của BESSIE, thì ELSIE là cô/dì của BESSIE. In ELSIE is the aunt of BESSIE nếu ELSIE là con của bà của BESSIE, ELSIE is the great-aunt of BESSIE nếu ELSIE là con của cụ của BESSIE, ELSIE is the great-great-aunt of BESSIE nếu ELSIE là con của kỵ của BESSIE, và cứ tiếp tục như vậy.
• Nếu BESSIE và ELSIE có quan hệ theo bất kỳ cách nào khác (tức là họ có chung một tổ tiên), họ là chị em họ và bạn chỉ cần in COUSINS.
• In NOT RELATED nếu BESSIE và ELSIE không có tổ tiên chung, hoặc không cô nào là hậu duệ trực hệ của cô còn lại.

Sơ đồ sau minh họa các mối quan hệ nêu trên; đây là những kiểu quan hệ duy nhất cần xét. Lưu ý rằng một số quan hệ như “cháu gái” (con gái của chị/em gái) là không cần thiết, bởi nếu BESSIE là cháu gái của ELSIE thì ELSIE là cô/dì của BESSIE.

Ví dụ

7 AA BB
MOTHER AA
GGMOTHER BB
MOTHER SISTER
GMOTHER MOTHER
GMOTHER AUNT
AUNT COUSIN
GGMOTHER GMOTHER

BB is the great-aunt of AA

Nguồn

USACO 2018 US Open Contest, Bronze — Family Tree

Tác giả bài toán: Brian Dean.