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

Ít người biết rằng bò rất thích các câu đố, đặc biệt là câu đố chữ. Gần đây, những con bò của Nông dân John đã tạo ra một trò chơi "tìm từ" thú vị. Dưới đây là một ví dụ về trò chơi như vậy:

USOPEN
OOMABO
MOOMXO
PQMROM

Vì là bò nên từ duy nhất chúng quan tâm là MOO. Từ này có thể xuất hiện ở nhiều vị trí trong bảng tìm từ, theo chiều ngang, chiều dọc hoặc đường chéo. Ví dụ trên chứa 6 từ MOO.

Nông dân John cũng là một người hâm mộ các câu đố chữ. Vì đàn bò không muốn ông giải bảng tìm từ trước khi chúng có cơ hội tự thử sức, chúng đã mã hóa nội dung bảng bằng một "mật mã thay thế", trong đó mỗi chữ cái trong bảng chữ cái được thay bằng một chữ cái khác. Chẳng hạn, A có thể được ánh xạ thành X, B có thể được ánh xạ thành A, v.v. Không chữ cái nào được ánh xạ thành chính nó, và không có hai chữ cái nào được ánh xạ thành cùng một chữ cái (vì nếu không, việc giải mã sẽ nhập nhằng).

Thật không may, đàn bò đã làm thất lạc mật mã thay thế cần thiết để giải mã bảng. Hãy giúp chúng xác định số lượng từ MOO lớn nhất có thể tồn tại trong bảng với một lựa chọn mật mã thay thế phù hợp.

Dữ liệu vào

Tệp moocrypt.in:

Dòng đầu tiên chứa \(N\) và \(M\), lần lượt là số hàng và số cột của bảng (cả hai đều không quá 50). Mỗi dòng trong \(N\) dòng tiếp theo chứa \(M\) ký tự, mô tả một hàng của bảng đã mã hóa. Mỗi ký tự là một chữ cái tiếng Anh viết hoa trong khoảng A đến Z.

Dữ liệu ra

Tệp moocrypt.out:

In số lượng từ MOO lớn nhất có thể có trong bảng nếu bảng được giải mã bằng một mật mã thay thế phù hợp.

Ví dụ

4 6
TAMHGI
MMQVWM
QMMQSM
HBQUMQ

6

Nguồn

USACO 2015 US Open, Bronze — Moocryption

Tác giả bài: Brian Dean, 2015.

Farmer John và cô bò Bessie thích trao đổi các câu đố toán học vào thời gian rảnh. Câu đố gần nhất FJ đưa cho Bessie khá khó và cô không giải được. Giờ đây, cô muốn trả đũa FJ bằng cách đưa cho ông một câu đố hóc búa.

Bessie đưa cho FJ biểu thức \((B+E+S+S+I+E)(G+O+E+S)(M+O+O)\), chứa bảy biến \(B,E,S,I,G,O,M\) (ký tự "\(O\)" là một biến, không phải chữ số không). Với mỗi biến, cô đưa cho FJ một danh sách gồm không quá 20 giá trị nguyên mà biến đó có thể nhận. Cô yêu cầu FJ đếm số cách khác nhau để gán giá trị cho các biến sao cho toàn bộ biểu thức có giá trị chẵn.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa một biến và một giá trị mà biến đó có thể nhận. Mỗi biến xuất hiện trong danh sách ít nhất một lần và nhiều nhất 20 lần. Với cùng một biến, không có giá trị khả dĩ nào được liệt kê quá một lần. Mọi giá trị khả dĩ đều nằm trong khoảng từ \(-300\) đến \(300\).

Dữ liệu ra

In một số nguyên duy nhất: số cách FJ có thể gán giá trị cho các biến sao cho biểu thức trên có giá trị chẵn.

Ví dụ

10
B 2
E 5
S 7
I 10
O 16
M 19
B 3
G 1
I 9
M 2

6

(B,E,S,I,G,O,M) = (2, 5, 7, 10, 1, 16, 19) -> 53,244
                = (2, 5, 7, 10, 1, 16, 2 ) -> 35,496
                = (2, 5, 7, 9,  1, 16, 2 ) -> 34,510
                = (3, 5, 7, 10, 1, 16, 2 ) -> 36,482
                = (3, 5, 7, 9,  1, 16, 19) -> 53,244
                = (3, 5, 7, 9,  1, 16, 2 ) -> 35,496

Nguồn

USACO 2015 US Open, Bronze — Bessie Gets Even. Tác giả đề: Brian Dean, 2015.

https://usaco.org/index.php?page=viewproblem2&cpid=546

Farmer John vừa nhận một lô gồm \(N\) kiện cỏ khô lớn (\(1 \le N \le 4000\)) và đặt chúng tại nhiều vị trí khác nhau dọc theo con đường dẫn đến chuồng. Không may, ông hoàn toàn quên mất rằng cô bò Bessie đang gặm cỏ dọc con đường, và giờ cô có thể đã bị mắc kẹt giữa các kiện cỏ!

Mỗi kiện cỏ \(j\) có kích thước \(S_j\) và một vị trí phân biệt \(P_j\) cho biết nơi nó nằm trên con đường một chiều. Bessie bắt đầu tại một vị trí không có kiện cỏ nào và có thể tự do di chuyển dọc theo đường, kể cả đi tới đúng vị trí của một kiện cỏ, nhưng cô không thể đi xuyên qua vị trí này. Tuy nhiên, nếu chạy theo cùng một hướng trên quãng đường dài \(D\), cô sẽ đạt đủ tốc độ để phá xuyên qua và loại bỏ vĩnh viễn bất kỳ kiện cỏ nào có kích thước nhỏ hơn nghiêm ngặt \(D\). Dĩ nhiên, sau khi làm vậy, cô có thể có thêm không gian để lấy đà lao vào các kiện cỏ khác và tiếp tục phá chúng.

Bessie có thể thoát ra ngoài nếu cuối cùng cô phá xuyên qua được kiện cỏ ngoài cùng bên trái hoặc ngoài cùng bên phải. Hãy tính tổng độ dài của phần đường gồm các vị trí bắt đầu có giá trị thực mà từ đó Bessie không thể thoát. Chẳng hạn, nếu Bessie không thể thoát khi bắt đầu giữa hai kiện cỏ ở vị trí 1 và 5, thì chúng tạo nên một phần đường có độ dài 4 mà từ đó cô không thể thoát.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo mô tả một kiện cỏ, gồm hai số nguyên cho biết kích thước và vị trí của kiện cỏ; mỗi số đều nằm trong khoảng \(1 \ldots 10^9\).

Dữ liệu ra

In một số nguyên duy nhất: độ dài của phần đường mà từ đó Bessie không thể thoát.

Ví dụ

5
8 1
1 4
8 8
7 15
4 20

14

Nguồn

USACO 2015 US Open, Bronze — Trapped in the Haybales (Bronze). Tác giả đề: Brian Dean, 2015.

https://usaco.org/index.php?page=viewproblem2&cpid=547

Trang trại của Farmer John có dạng một lưới gồm \(N \times N\) ô đồng (\(2 \le N \le 18\)), mỗi ô được ghi một chữ cái trong bảng chữ cái. Ví dụ:

ABCD
BXZX
CDXB
WCBA

Mỗi ngày, cô bò Bessie đi từ ô trên cùng bên trái đến ô dưới cùng bên phải; ở mỗi bước, cô đi sang ô ngay bên phải hoặc xuống ô ngay bên dưới. Bessie ghi lại chuỗi được tạo nên trong quá trình này từ các chữ cái trên những ô cô đi qua. Tuy nhiên, cô sẽ mất phương hướng nếu chuỗi đó là một palindrome (đọc xuôi và đọc ngược giống nhau), vì cô bối rối không biết mình đã đi theo hướng nào.

Hãy giúp Bessie xác định số palindrome khác nhau mà cô có thể tạo ra trong chuyến đi. Các cách khác nhau tạo ra cùng một palindrome chỉ được tính một lần; chẳng hạn, có nhiều đường đi tạo ra palindrome ABXZXBA trong ví dụ trên, nhưng Bessie chỉ có thể tạo ra bốn palindrome phân biệt: ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), và \(N\) dòng còn lại chứa \(N\) hàng của lưới ô đồng. Mỗi hàng chứa \(N\) ký tự trong khoảng từ A đến Z.

Dữ liệu ra

In số palindrome phân biệt mà Bessie có thể tạo ra.

Ví dụ

4
ABCD
BXZX
CDXB
WCBA

4

Nguồn

USACO 2015 US Open, Bronze — Palindromic Paths (Bronze). Tác giả đề: Brian Dean, 2015.

https://usaco.org/index.php?page=viewproblem2&cpid=548