USACO 2014 - Tháng 2 - Hạng Đồng

Farmer John để vài chiếc gương cũ ở bên ngoài ngôi nhà, và những cô bò của ông, vẫn tinh nghịch như mọi khi, đã lấy trộm chúng!

Những cô bò đã bố trí các tấm gương trên một cánh đồng hình chữ nhật gồm \(N\) hàng và \(M\) cột ô vuông (\(1 \le N,M \le 1\,000\)). Trong mỗi ô, chúng đặt một tấm gương hai mặt nối hai góc đối diện. Hai cách bố trí có thể có này được biểu diễn bằng ký tự / (một tấm gương nối góc dưới bên trái với góc trên bên phải) và ký tự \ (một tấm gương nối góc trên bên trái với góc dưới bên phải).

Một buổi tối, cô bò Bessie mang một chiếc bút laser ra cánh đồng gương. Đứng bên ngoài cánh đồng, cô chiếu tia sáng theo phương ngang dọc theo một hàng hoặc theo phương thẳng đứng dọc theo một cột, khiến tia sáng phản xạ trên một số tấm gương. Vì tất cả các tấm gương đều nằm theo đường chéo, một tia sáng nằm ngang sau khi phản xạ trên gương sẽ chuyển sang di chuyển theo phương dọc và ngược lại. Bessie muốn biết tia sáng của mình có thể phản xạ trên nhiều nhất bao nhiêu tấm gương trong một lần chiếu. Cho cách bố trí cánh đồng gương, hãy giúp Bessie tính con số này.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) cách nhau bởi một dấu cách.
• \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) ký tự / hoặc \, mô tả một hàng của cánh đồng gương.

Ràng buộc

• \(1 \le N,M \le 1\,000\).

Dữ liệu ra

In ra một số nguyên duy nhất là số lần phản xạ tối đa của một tia sáng nằm ngang hoặc thẳng đứng được chiếu từ bên ngoài cánh đồng gương. In ra \(-1\) nếu tia sáng có thể phản xạ vô hạn lần.

Ví dụ

3 3
/\\
\\\
/\/

3

Nguồn

USACO 2014 February Contest, Bronze — Mirror Field

Tác giả: Mark Gordon.

Bessie có một chiếc điện thoại di động mới và rất thích gửi tin nhắn, mặc dù cô thường xuyên mắc lỗi chính tả vì bộ móng lớn khiến cô khó gõ trên màn hình nhỏ. Farmer John đồng ý giúp cô bằng cách viết một ứng dụng tự động hoàn thành từ: ứng dụng nhận một phần đầu của từ và đề xuất cách hoàn thành nó.

Ứng dụng tự động hoàn thành có quyền truy cập vào một từ điển gồm \(W\) từ, mỗi từ chỉ gồm các chữ cái thường từ a đến z, và tổng số chữ cái của tất cả các từ không vượt quá \(1\,000\,000\). Đầu vào của ứng dụng còn có danh sách \(N\) phần đầu của từ (\(1 \le N \le 1\,000\)), mỗi phần gồm không quá \(1\,000\) chữ cái thường. Cùng với mỗi phần đầu thứ \(i\), một số nguyên \(K_i\) cũng được cung cấp; ứng dụng phải tìm từ thứ \(K_i\) theo thứ tự bảng chữ cái trong số các từ nhận phần đầu thứ \(i\) làm tiền tố. Nói cách khác, nếu sắp xếp tất cả các cách hoàn thành hợp lệ của phần đầu thứ \(i\), ứng dụng phải đưa ra cách hoàn thành đứng thứ \(K_i\) trong dãy này.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(W\) và \(N\).
• \(W\) dòng tiếp theo, dòng thứ \(i\) trong số này chứa từ thứ \(i\) của từ điển.
• \(N\) dòng cuối, dòng thứ \(i\) trong số này chứa một số nguyên \(K_i\), theo sau là một phần đầu của từ.

Ràng buộc

• \(1 \le N \le 1\,000\).
• Tổng số chữ cái trong tất cả các từ của từ điển không vượt quá \(1\,000\,000\).
• Mỗi phần đầu của từ chứa không quá \(1\,000\) chữ cái thường.
• Tất cả các từ và phần đầu của từ chỉ chứa các chữ cái thường từ a đến z.

Dữ liệu ra

Với mỗi phần đầu thứ \(i\), in ra trên một dòng chỉ số trong từ điển (một số nguyên từ \(1\) đến \(W\)) của cách hoàn thành thứ \(K_i\) theo thứ tự bảng chữ cái, hoặc \(-1\) nếu có ít hơn \(K_i\) cách hoàn thành.

Ví dụ

10 3
dab
ba
ab
daa
aa
aaa
aab
abc
ac
dadba
4 a
2 da
4 da

3
1
-1

Nguồn

USACO 2014 February Contest, Silver — Auto-Complete

Tác giả: Traditional.

Farmer John có một thông điệp bí mật muốn giấu những cô bò của mình; thông điệp là một xâu có độ dài ít nhất \(2\) và chỉ chứa các ký tự từ A đến Z.

Để mã hóa thông điệp, FJ áp dụng một chuỗi các "thao tác" lên nó. Mỗi thao tác trên một xâu \(S\) trước hết rút ngắn \(S\) bằng cách xóa ký tự đầu tiên hoặc ký tự cuối cùng, sau đó ghép xâu \(S\) ban đầu vào đầu hoặc cuối xâu đã rút ngắn. Chẳng hạn, một thao tác trên xâu ABCD có thể tạo ra một trong bốn xâu sau:

BCDABCD
ABCABCD
ABCDABC
ABCDBCD

Cho xâu đã mã hóa cuối cùng, hãy đếm số cách FJ có thể tạo ra xâu này bằng cách áp dụng liên tiếp một hoặc nhiều thao tác lên một xâu nguồn nào đó. Các thao tác được coi là khác nhau ngay cả khi chúng tạo ra cùng một bản mã của thông điệp của FJ. Chẳng hạn, có bốn cách riêng biệt để thu được AAA từ AA, tương ứng với bốn thao tác có thể có nêu trên.

Dữ liệu vào

• Dòng đầu tiên chứa một xâu có độ dài không quá \(100\).

Ràng buộc

• Xâu đầu vào có độ dài không quá \(100\).

Dữ liệu ra

In ra số cách khác nhau mà FJ có thể tạo ra xâu đã cho bằng cách áp dụng liên tiếp một hoặc nhiều thao tác lên một xâu nguồn có độ dài ít nhất \(2\). Nếu không có cách nào, in ra \(0\).

Ví dụ

ABABA

6

Nguồn

USACO 2014 February Contest, Bronze — Secret Code

Tác giả: Brian Dean và Lewin Gan.