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

Một đám cháy đã bùng phát trong trang trại, và những chú bò đang vội vã tìm cách dập lửa!

Trang trại được mô tả bởi một lưới ký tự \(10 \times 10\) như sau:

..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........

Ký tự B biểu thị chuồng bò, nơi vừa bốc cháy. Ký tự L biểu thị một hồ nước, còn R biểu thị vị trí của một tảng đá lớn.

Những chú bò muốn lập một "đội chuyền xô" bằng cách đứng dọc theo một đường đi giữa hồ và chuồng bò, để có thể chuyền những xô nước dọc theo đường đi nhằm giúp dập lửa. Một chiếc xô có thể được chuyền giữa hai con bò nếu chúng kề nhau ngay theo hướng bắc, nam, đông hoặc tây. Điều tương tự cũng áp dụng cho một con bò đứng cạnh hồ: nó chỉ có thể lấy một xô nước từ hồ nếu đứng kề ngay với hồ. Tương tự, một con bò chỉ có thể hắt một xô nước vào chuồng nếu đứng kề ngay với chuồng.

Hãy xác định số ô . ít nhất cần có bò đứng để lập được một đội chuyền xô thành công.

Không thể đặt bò vào ô chứa tảng đá lớn, và chuồng bò cùng hồ nước được đảm bảo không kề nhau ngay.

Dữ liệu vào

Dữ liệu vào gồm 10 dòng, mỗi dòng có 10 ký tự, mô tả bố cục của trang trại.

Dữ liệu ra

In ra một số nguyên duy nhất là số bò ít nhất cần thiết để lập được một đội chuyền xô khả thi.

Ví dụ

..........
..........
..........
..B.......
..........
.....R....
..........
..........
.....L....
..........

7

..........
..........
..........
..B.......
..C.......
..CC.R....
...CCC....
.....C....
.....L....
..........

Nguồn

USACO 2019 US Open Contest, Bronze — Bucket Brigade

Tác giả: Brian Dean.

Ngành kinh doanh sữa đang phát triển mạnh! Nhà máy chế biến sữa của Farmer John gồm \(N\) trạm chế biến, được đánh số thuận tiện từ \(1 \ldots N\) (\(1 \leq N \leq 100\)), và \(N-1\) lối đi, mỗi lối nối một cặp trạm nào đó. (Các lối đi rất tốn kém, nên Farmer John đã chọn dùng số lối đi ít nhất sao cho từ bất kỳ trạm nào cũng có thể cuối cùng đi tới mọi trạm khác.)

Để cố gắng nâng cao hiệu quả, Farmer John lắp một băng chuyền trên mỗi lối đi. Thật không may, ông nhận ra quá muộn rằng mỗi băng chuyền chỉ chuyển động theo một chiều, vì vậy giờ đây chỉ có thể đi trên mỗi lối đi theo một hướng duy nhất! Do đó, không còn có thể đi từ bất kỳ trạm nào tới bất kỳ trạm nào khác.

Tuy nhiên, Farmer John cho rằng mọi chuyện vẫn có thể cứu vãn, miễn là tồn tại ít nhất một trạm \(i\) sao cho từ mọi trạm khác cuối cùng đều có thể đi tới trạm \(i\). Lưu ý rằng việc đi tới trạm \(i\) từ một trạm \(j\) bất kỳ khác có thể phải đi qua các trạm trung gian giữa \(i\) và \(j\). Hãy giúp Farmer John xác định xem một trạm \(i\) như vậy có tồn tại hay không.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\), là số trạm chế biến. Mỗi dòng trong \(N-1\) dòng tiếp theo chứa hai số nguyên cách nhau bởi dấu cách \(a_i\) và \(b_i\), với \(1 \leq a_i, b_i \leq N\) và \(a_i \neq b_i\). Điều này cho biết có một băng chuyền chuyển động từ trạm \(a_i\) tới trạm \(b_i\), chỉ cho phép di chuyển theo hướng từ \(a_i\) tới \(b_i\).

Dữ liệu ra

Nếu tồn tại một trạm \(i\) sao cho từ bất kỳ trạm nào khác cũng có thể đi tới trạm \(i\), hãy in ra giá trị \(i\) nhỏ nhất như vậy. Nếu không, in ra \(-1\).

Ví dụ

3
1 2
3 2

2

Nguồn

USACO 2019 US Open Contest, Bronze — Milk Factory

Tác giả: Dhruv Rohatgi.

Năm nay là năm 3019, và trong một nghìn năm qua đã diễn ra một lượng tiến hóa đáng kinh ngạc ở loài bò, tạo nên những con bò với đủ loại đặc điểm thú vị.

Lịch sử tiến hóa của loài bò có thể được mô tả bằng một cây, bắt đầu tại gốc với một con bò tổ tiên cơ bản không có đặc điểm đặc biệt nào. Ở mỗi tầng hậu duệ trong cây, hoặc tất cả các con bò đều tiến hóa thêm một đặc điểm mới (chẳng hạn khả năng thở ra lửa trong hình dưới đây, nơi tất cả những con bò có đốm cuối cùng đều thở ra lửa), hoặc quần thể bò phân nhánh, trong đó một số con tiến hóa thêm một đặc điểm mới (ví dụ như biết bay) còn một số thì không.

Các lá ở đáy cây biểu thị tất cả những quần thể con hình thành vào năm 3019. Không có hai lá (quần thể con) nào chứa các tập đặc điểm giống hệt nhau. Ví dụ, quần thể con số 1 gồm những con bò không có đặc điểm đặc biệt nào, còn quần thể con số 3 gồm những con bò biết bay và có khả năng thần giao cách cảm. Trái lại, quần thể con số 2 có những con bò biết bay nhưng không có khả năng thần giao cách cảm. Quần thể con số 3 là duy nhất với tổ hợp bò vừa biết bay vừa có khả năng thần giao cách cảm.

Một cây tiến hóa như trên được gọi là "hợp lệ" nếu mỗi đặc điểm mới tiến hóa chỉ bắt nguồn trên đúng một cạnh của cây (tức là nó xuất hiện tại một thời điểm duy nhất trong lịch sử). Ví dụ, một cây sẽ không hợp lệ nếu các đốm tiến hóa xuất hiện trên hai nhánh riêng biệt. Cho trước mô tả về các quần thể con của bò vào năm 3019, hãy xác định liệu chúng có thể được mô tả bằng một cây tiến hóa hợp lệ hay không.

Dữ liệu vào

Dòng đầu tiên chứa số quần thể con \(N\) (\(2 \leq N \leq 25\)). Mỗi dòng trong \(N\) dòng tiếp theo mô tả một quần thể con. Dòng bắt đầu bằng một số nguyên \(K\) (\(0 \leq K \leq 25\)), sau đó là \(K\) đặc điểm có ở tất cả những con bò trong quần thể con đó. Mỗi đặc điểm là một xâu gồm không quá 20 ký tự chữ thường (a..z). Không có hai quần thể con nào có các đặc điểm giống hệt nhau.

Dữ liệu ra

In ra yes nếu có thể lập một cây tiến hóa hợp lệ giải thích nguồn gốc của các quần thể con này, và in ra no nếu không thể.

Ví dụ

4
2 spots firebreathing
0
1 flying
2 telepathic flying

yes

Nguồn

USACO 2019 US Open Contest, Bronze — Cow Evolution

Tác giả: Brian Dean.