USACO 2014 - Tháng 2 - Hạng Bạc

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.

Mỗi buổi sáng, FJ thức dậy và đi qua trang trại từ nhà đến chuồng. Trang trại gồm \(N\) cánh đồng (\(1 \le N \le 250\)) được nối với nhau bởi \(M\) con đường hai chiều (\(1 \le M \le 25\,000\)), mỗi con đường có một độ dài tương ứng. Nhà của FJ nằm ở cánh đồng \(1\), còn chuồng nằm ở cánh đồng \(N\). Không có cặp cánh đồng nào được nối bởi nhiều con đường trùng lặp, và có thể di chuyển giữa hai cánh đồng bất kỳ trong trang trại bằng cách đi theo một dãy đường thích hợp. Khi đi từ cánh đồng này đến cánh đồng khác, FJ luôn chọn một lộ trình gồm một dãy đường có tổng độ dài nhỏ nhất.

Những cô bò của Farmer John, vẫn luôn thích gây rắc rối, quyết định cản trở thói quen buổi sáng của ông. Chúng dự định chất một đống kiện cỏ khô trên đúng một trong \(M\) con đường của trang trại, khiến độ dài của con đường đó tăng gấp đôi. Những cô bò muốn chọn con đường để chặn sao cho mức tăng quãng đường từ nhà đến chuồng của FJ là lớn nhất. Hãy giúp chúng xác định có thể làm lộ trình của FJ dài thêm nhiều nhất bao nhiêu.

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.
• \(M\) dòng tiếp theo, dòng thứ \(j\) chứa ba số nguyên \(A_j\), \(B_j\) và \(L_j\) cách nhau bởi dấu cách, mô tả con đường hai chiều thứ \(j\). Trong đó, \(A_j\) và \(B_j\) là các chỉ số từ \(1\) đến \(N\) của hai cánh đồng được nối bởi con đường, còn \(L_j\) là độ dài con đường, nằm trong đoạn từ \(1\) đến \(1\,000\,000\).

Ràng buộc

• \(1 \le N \le 250\).
• \(1 \le M \le 25\,000\).
• \(1 \le A_j,B_j \le N\).
• \(1 \le L_j \le 1\,000\,000\).
• Không có hai con đường cùng nối một cặp cánh đồng, và mọi cặp cánh đồng đều có thể đi đến nhau.

Dữ liệu ra

In ra mức tăng lớn nhất có thể của tổng độ dài lộ trình ngắn nhất của FJ khi tăng gấp đôi độ dài của một con đường duy nhất.

Ví dụ

5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2

2

Nguồn

USACO 2014 February Contest, Gold — Roadblock

Tác giả: Brian Dean.

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 một số nhưng không phải tất cả các ký tự đầu xâu, hoặc một số nhưng không phải tất cả các ký tự cuối xâu, 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 ABC có thể tạo ra một trong tám xâu sau:

AABC
ABABC
BCABC
CABC
ABCA
ABCAB
ABCBC
ABCC

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.

In đáp án theo modulo \(2014\).

Dữ liệu vào

• Dòng đầu tiên chứa một xâu đã mã hóa 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 theo modulo \(2014\) số cách 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 ban đầu có độ dài ít nhất \(2\). Nếu không có cách nào, in ra \(0\).

Ví dụ

ABABA

8

Nguồn

USACO 2014 February Contest, Silver — Secret Code

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