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

Để cải thiện thể lực, những chú bò đã bắt đầu tập thể dục dụng cụ! Nông dân John chỉ định cô bò yêu thích Bessie huấn luyện \(N\) cô bò còn lại và đánh giá sự tiến bộ của họ khi học các kỹ năng thể dục khác nhau.

Trong mỗi buổi thuộc \(K\) buổi tập (\(1 \leq K \leq 10\)), Bessie xếp hạng \(N\) cô bò theo thành tích của họ (\(1 \leq N \leq 20\)). Sau đó, cô tò mò về tính nhất quán giữa các bảng xếp hạng này. Một cặp gồm hai cô bò khác nhau được gọi là nhất quán nếu một cô luôn thể hiện tốt hơn cô còn lại trong mọi buổi tập.

Hãy giúp Bessie tính tổng số cặp nhất quán.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên dương \(K\) và \(N\). Mỗi dòng trong \(K\) dòng tiếp theo chứa các số nguyên \(1 \ldots N\) theo một thứ tự nào đó, biểu thị thứ hạng của các cô bò (các cô bò được nhận diện bằng các số \(1 \ldots N\)). Nếu \(A\) xuất hiện trước \(B\) trên một trong các dòng này, điều đó có nghĩa là bò \(A\) thể hiện tốt hơn bò \(B\).

Dữ liệu ra

In trên một dòng số cặp nhất quán.

Ví dụ

3 4
4 1 2 3
4 1 3 2
4 2 1 3

4

Nguồn

USACO 2019 December Contest, Bronze - Cow Gymnastics: https://usaco.org/index.php?page=viewproblem2&cpid=963

Tác giả: Nick Wu.

Nông dân John đã ra ngoài đi dạo dọc con đường và giờ ông nghĩ rằng có lẽ mình đã bị lạc!

Dọc con đường có \(N\) trang trại (\(1 \leq N \leq 100\)) nằm liên tiếp thành một hàng. Thật không may, các trang trại không có số nhà, khiến Nông dân John khó xác định vị trí của mình trên đường. Tuy nhiên, mỗi trang trại đều có một hộp thư đầy màu sắc bên đường, vì vậy Nông dân John hy vọng rằng nếu quan sát màu sắc của những hộp thư gần mình nhất, ông có thể xác định duy nhất vị trí hiện tại.

Mỗi màu hộp thư được biểu thị bằng một chữ cái trong phạm vi A..Z, vì vậy dãy \(N\) hộp thư dọc con đường có thể được biểu diễn bằng một xâu độ dài \(N\) gồm các chữ cái trong phạm vi A..Z. Một số hộp thư có thể cùng màu với những hộp thư khác. Nông dân John muốn biết giá trị nhỏ nhất của \(K\) sao cho khi quan sát bất kỳ dãy \(K\) hộp thư liên tiếp nào, ông đều có thể xác định duy nhất vị trí của dãy đó trên đường.

Ví dụ, giả sử dãy hộp thư dọc con đường là ABCDABC. Nông dân John không thể chọn \(K=3\), vì nếu nhìn thấy ABC, có hai vị trí khả dĩ trên đường mà dãy màu liên tiếp này có thể xuất hiện. Giá trị nhỏ nhất của \(K\) thỏa mãn là \(K=4\), vì nếu ông quan sát bất kỳ nhóm 4 hộp thư liên tiếp nào, dãy màu này sẽ xác định duy nhất vị trí của ông trên đường.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), và dòng thứ hai chứa một xâu gồm \(N\) ký tự, mỗi ký tự thuộc phạm vi A..Z.

Dữ liệu ra

In một dòng chứa một số nguyên duy nhất, là giá trị nhỏ nhất của \(K\) giải quyết được bài toán của Nông dân John.

Ví dụ

7
ABCDABC

4

Nguồn

USACO 2019 December Contest, Bronze - Where Am I?: https://usaco.org/index.php?page=viewproblem2&cpid=964

Tác giả: Brian Dean.

Mỗi ngày, Nông dân John vắt sữa 8 cô bò sữa của mình, tên là Bessie, Buttercup, Belinda, Beatrice, Bella, Blue, Betsy và Sue.

Thật không may, những cô bò khá kén chọn và yêu cầu Nông dân John vắt sữa theo một thứ tự tôn trọng \(N\) ràng buộc (\(1 \leq N \leq 7\)). Mỗi ràng buộc có dạng "\(X\) must be milked beside \(Y\)", quy định rằng bò \(X\) phải xuất hiện trong thứ tự vắt sữa ngay sau bò \(Y\) hoặc ngay trước bò \(Y\).

Hãy giúp Nông dân John xác định một thứ tự các cô bò thỏa mãn tất cả các ràng buộc bắt buộc này. Đề bài đảm bảo luôn tồn tại một thứ tự như vậy. Nếu có nhiều thứ tự hợp lệ, hãy in thứ tự đứng đầu theo thứ tự bảng chữ cái. Nghĩa là, cô bò đầu tiên phải có tên nhỏ nhất theo thứ tự bảng chữ cái trong số tất cả những cô bò có thể đứng đầu ở một thứ tự hợp lệ bất kỳ. Trong tất cả các thứ tự bắt đầu bằng cùng cô bò đứng đầu này, cô bò thứ hai phải có tên nhỏ nhất theo thứ tự bảng chữ cái trong số mọi thứ tự hợp lệ có thể có, và cứ tiếp tục như vậy.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa một câu mô tả một ràng buộc có dạng "\(X\) must be milked beside \(Y\)", trong đó \(X\) và \(Y\) là tên của một số cô bò của Nông dân John (tám tên có thể có đã được liệt kê ở trên).

Dữ liệu ra

In một thứ tự của các cô bò trên 8 dòng, mỗi dòng một tên bò, sao cho thỏa mãn tất cả các ràng buộc. Nếu có nhiều thứ tự hợp lệ, hãy in thứ tự sớm nhất theo thứ tự bảng chữ cái.

Ví dụ

3
Buttercup must be milked beside Bella
Blue must be milked beside Bella
Sue must be milked beside Beatrice

Beatrice
Sue
Belinda
Bessie
Betsy
Blue
Bella
Buttercup

Nguồn

USACO 2019 December Contest, Bronze - Livestock Lineup: https://usaco.org/index.php?page=viewproblem2&cpid=965

Tác giả: Brian Dean.