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

Bessie đang chơi một trò chơi điện tử! Trong trò chơi, ba chữ cái A, B và C là những nút bấm hợp lệ duy nhất. Bessie có thể nhấn các nút theo bất kỳ thứ tự nào mình muốn; tuy nhiên, chỉ có \(N\) combo phân biệt có thể xuất hiện (\(1 \le N \le 20\)). Combo thứ \(i\) được biểu diễn bởi một chuỗi \(S_i\) có độ dài từ 1 đến 15 và chỉ chứa các chữ cái A, B, C.

Mỗi khi Bessie nhấn một dãy chữ cái khớp với một combo, cô nhận được một điểm cho combo đó. Các combo có thể chồng lấn nhau hoặc thậm chí kết thúc cùng lúc! Ví dụ, nếu \(N=3\) và ba combo là ABA, CB, ABACB, khi Bessie nhấn ABACB, cô sẽ có 3 điểm. Bessie có thể ghi điểm từ cùng một combo nhiều lần.

Dĩ nhiên Bessie muốn kiếm điểm nhanh nhất có thể. Nếu cô nhấn chính xác \(K\) nút (\(1 \le K \le 1\,000\)), số điểm tối đa cô có thể kiếm được là bao nhiêu?

Dữ liệu vào

• Dòng 1 chứa hai số nguyên \(N\) và \(K\), cách nhau bởi dấu cách.
• Các dòng từ 2 đến \(N+1\): dòng \(i+1\) chỉ chứa chuỗi \(S_i\), biểu diễn combo thứ \(i\).

Dữ liệu ra

In một số nguyên duy nhất là số điểm tối đa Bessie có thể đạt được.

Ví dụ

3 7
ABA
CB
ABACB

4

Nguồn

USACO 2012 January Contest, Gold - Video Game: https://usaco.org/index.php?page=viewproblem2&cpid=109

Tác giả: Neal Wu, 2012.

Farmer John và Bessie đã nghĩ ra một trò vận động mới cho đàn bò. Đàn bò chạy trên một đường đua hình tròn có độ dài \(M\) (\(2 \le M \le 1\,000\,000\,000\)), xuất phát từ cùng một vị trí. Trò chơi diễn ra trong \(N\) vòng (\(1 \le N \le 14\)), sử dụng một bộ gồm \(8N\) lá bài, trên mỗi lá ghi một số \(X_i\) (\(0 \le X_i < M\)).

Trong mỗi vòng, FJ chuyển 8 lá trên cùng sang một chồng riêng và chọn 4 lá trên cùng hoặc 4 lá dưới cùng để Bessie chơi. Sau đó, Bessie chọn 2 lá trên cùng hoặc 2 lá dưới cùng trong 4 lá FJ đã chọn. Tiếp theo, FJ đọc số trên lá trên cùng, \(X_{\text{top}}\), và đàn bò chạy một quãng đường \(R \times X_{\text{top}}\), trong đó \(R\) là tổng quãng đường đàn bò đã chạy cho đến lúc đó. Sau đó Bessie đọc số trên lá dưới cùng, \(X_{\text{bottom}}\), và đàn bò chạy một quãng đường \(X_{\text{bottom}}\).

FJ lo rằng sau buổi tập, đàn bò sẽ quá mệt để quay lại điểm đầu đường đua nếu chúng kết thúc ở quá xa. Ông tin rằng nếu đàn bò kết thúc ở vị trí cách điểm xuất phát hơn \(K\) (\(0 \le K \le \lfloor M/2 \rfloor\)), chúng sẽ không thể trở về nhà.

Đề bài đảm bảo rằng nếu FJ chơi đúng, ông luôn có thể bảo đảm đàn bò về được nhà, bất kể Bessie đi nước nào! Ở mỗi vòng, nhiệm vụ của bạn là xác định FJ nên chọn nửa nào của các lá bài sao cho, dù từ thời điểm đó trở đi Bessie làm gì, FJ vẫn luôn có thể đưa đàn bò về nhà. Sau đó Bessie sẽ thực hiện nước đi được cho trong dữ liệu vào và bạn có thể tiếp tục sang vòng kế tiếp. Lưu ý rằng dù các nước đi của Bessie được cung cấp trong dữ liệu vào, bạn vẫn phải chỉ ra những nước đi cho FJ có thể thành công bất kể Bessie chọn gì (do đó, về bản chất, FJ thực sự không biết Bessie sẽ làm gì trong các lượt của cô).

Dữ liệu vào

• Dòng 1 chứa ba số nguyên \(N\), \(M\), \(K\), cách nhau bởi dấu cách.
• Dòng 2 chứa một chuỗi gồm \(N\) ký tự. Nếu ký tự thứ \(i\) là T, Bessie sẽ chọn 2 lá trên cùng ở vòng thứ \(i\). Ngược lại, ký tự thứ \(i\) là B, cho biết Bessie sẽ chọn 2 lá dưới cùng ở vòng thứ \(i\).
• Các dòng từ 3 đến \(2+N\): mỗi dòng chứa tám số nguyên biểu diễn 8 lá bài được dùng trong vòng đó, theo thứ tự từ trên xuống dưới.

Dữ liệu ra

In một chuỗi gồm \(N\) ký tự, trong đó ký tự thứ \(i\) là T nếu FJ nên chọn 4 lá trên cùng, hoặc là B nếu FJ nên chọn 4 lá dưới cùng ở vòng thứ \(i\). Nếu có nhiều cách đưa đàn bò về nhà, hãy chọn chuỗi nhỏ nhất theo thứ tự từ điển (tức là chuỗi đứng trước theo thứ tự bảng chữ cái).

Ví dụ

2 2 0
TT
1 0 0 0 0 0 0 1
0 1 1 1 0 0 1 0

TB

Nguồn

USACO 2012 January Contest, Gold - Cow Run: https://usaco.org/index.php?page=viewproblem2&cpid=110

Tác giả: Mark Gordon, 2011.

Bessie và những người bạn bò ở các trang trại gần đó cuối cùng đã quyết định nối các trang trại với nhau bằng những con đường mòn nhằm lập liên minh chống lại các nông dân. Ban đầu, đàn bò ở mỗi trong số \(N\) trang trại (\(1 \le N \le 100\,000\)) được yêu cầu xây một đường mòn đến đúng một trang trại khác, tạo thành tổng cộng \(N\) đường mòn. Tuy nhiên, sau nhiều tháng thực hiện dự án, mới chỉ có \(M\) (\(1 \le M < N\)) đường mòn thực sự được xây.

Những cuộc tranh cãi giữa các trang trại về việc trang trại nào đã xây một đường mòn giờ đây đe dọa chia rẽ liên minh bò. Để xoa dịu căng thẳng, Bessie muốn tính xem \(M\) đường mòn hiện có có thể đã được xây theo bao nhiêu cách. Ví dụ, nếu có một đường mòn nối trang trại 3 và 4, một khả năng là trang trại 3 đã xây đường mòn đó, còn khả năng kia là trang trại 4 đã xây nó. Hãy giúp Bessie tính số cách khác nhau để gán mỗi đường mòn cho trang trại đã xây nó, lấy modulo \(1\,000\,000\,007\). Hai cách gán được coi là khác nhau nếu có ít nhất một đường mòn được xây bởi hai trang trại khác nhau trong hai cách gán.

Dữ liệu vào

• Dòng 1 chứa hai số nguyên \(N\) và \(M\), cách nhau bởi dấu cách.
• Các dòng từ 2 đến \(1+M\): dòng \(i+1\) mô tả đường mòn thứ \(i\). Mỗi dòng chứa hai số nguyên \(u_i\) và \(v_i\) cách nhau bởi dấu cách (\(1 \le u_i,v_i \le N\), \(u_i \ne v_i\)), mô tả cặp trang trại được đường mòn nối với nhau.

Dữ liệu ra

In một dòng duy nhất chứa số cách gán các đường mòn cho các trang trại, lấy modulo \(1\,000\,000\,007\). Nếu không có cách gán nào thỏa mãn các điều kiện trên, in ra 0.

Ví dụ

5 4
1 2
3 2
4 5
4 5

6

Nguồn

USACO 2012 January Contest, Gold - Bovine Alliance: https://usaco.org/index.php?page=viewproblem2&cpid=111

Tác giả: Mark Gordon, 2011.