USACO 2021 - US Open - Hạng Bạc

Bessie thích giải mê cung. Cô cũng thích chơi cờ ca-rô ba ô, hay chính xác hơn là phiên bản dành cho bò được mô tả dưới đây. Farmer John đã tìm ra một cách mới để cô chơi cả hai trò cùng lúc!

Trước hết là cờ ca-rô dành cho bò. Thay vì đặt X và O trên bảng \(3\times3\), những chú bò dùng M và O trên bảng \(3\times3\). Trong mỗi lượt, người chơi có thể đặt M hoặc O vào một ô trống bất kỳ. Đây cũng là một điểm khác với cờ ca-rô thông thường, nơi một người luôn đánh X và người kia luôn đánh O. Người chiến thắng là người đầu tiên ghép được MOO theo chiều ngang, dọc hoặc chéo. Đọc ngược cũng được tính, ví dụ có thể thắng bằng cách ghép OOM trên một hàng. Giống cờ ca-rô thông thường, có thể xuất hiện trạng thái bảng không có người thắng. Một nước đi thường được biểu diễn bằng ba ký tự, có dạng Mij hoặc Oij, trong đó \(i\) và \(j\) đều thuộc phạm vi \(1\ldots3\), lần lượt chỉ hàng và cột để đặt chữ cái tương ứng.

Để thử thách Bessie, Farmer John thiết kế một mê cung hình vuông gồm lưới \(N\times N\) ô (\(3\le N\le25\)). Một số ô, bao gồm toàn bộ các ô biên, chứa những kiện cỏ khô lớn nên Bessie không thể bước vào. Bessie có thể di chuyển tự do giữa các ô còn lại bằng cách bước theo bốn hướng bắc, nam, đông và tây.

Một số ô chứa mảnh giấy ghi một nước đi. Trong khi di chuyển qua mê cung, mỗi khi bước lên một ô như vậy, Bessie bắt buộc thực hiện nước đi tương ứng trong ván cờ mà cô đang chơi đồng thời, trừ khi ô tương ứng trên bảng cờ đã có chữ cái; trong trường hợp đó cô không làm gì. Bessie không có đối thủ trong ván cờ này, nhưng một số ô trong mê cung có thể cản trở mục tiêu cuối cùng ghép được MOO của cô.

Giả sử Bessie ngừng chơi ngay khi chiến thắng. Hãy xác định số cấu hình bảng cờ chiến thắng phân biệt mà cô có thể tạo ra bằng cách di chuyển thích hợp qua mê cung.

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 \(3N\) ký tự mô tả mê cung. Mỗi ô được mô tả bằng một khối ba ký tự:

• ### là tường;
• ... là ô trống;
• BBB là ô không phải tường và chứa Bessie;
• một nước đi cờ bò là ô không phải tường, buộc Bessie thực hiện nước đi tương ứng.

Có đúng một ô BBB.

Dữ liệu ra

In số cấu hình bảng cờ bò chiến thắng phân biệt, có thể bằng \(0\), mà Bessie có thể tạo ra bằng cách di chuyển trong mê cung và dừng lại sau khi chiến thắng.

Phân nhóm

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

Ví dụ

7
#####################
###O11###...###M13###
###......O22......###
###...######M22######
###BBB###M31###M11###
###...O32...M33O31###
#####################

8

Trong ví dụ này, Bessie có thể đạt được tám cấu hình bảng chiến thắng sau:

O.M
.O.
MOM

O..
.O.
.OM

O.M
.O.
.OM

O..
.O.
MOM

O..
...
OOM

..M
.O.
OOM

...
.O.
OOM

...
...
OOM

Để giải thích một trong các cấu hình trên, xét trường hợp:

O..
...
OOM

Bessie có thể đến ô O11 trước, sau đó di chuyển đến hành lang phía dưới và lần lượt đi qua O32, M33, O31. Ván cờ kết thúc tại đó vì cô đã thắng; chẳng hạn, cô không thể tiếp tục đến ô M11 nằm phía bắc vị trí hiện tại trên ô O31.

Nguồn

USACO 2021 US Open, Silver - Maze Tac Toe: https://usaco.org/index.php?page=viewproblem2&cpid=1134

Tác giả: Brian Dean.

Những chú bò của Farmer John tổ chức một buổi họp trực tuyến hằng ngày trên nền tảng họp video “mooZ”. Để giải trí trong buổi họp, chúng đã nghĩ ra một trò chơi số học đơn giản.

Elsie có ba số nguyên dương \(A\), \(B\) và \(C\) (\(1\le A\le B\le C\)). Ba số này phải được giữ bí mật nên cô không tiết lộ trực tiếp cho chị gái Bessie. Thay vào đó, cô cho Bessie biết \(N\) số nguyên phân biệt \(x_1,x_2,\ldots,x_N\) (\(4\le N\le7\), \(1\le x_i\le10^9\)), đồng thời khẳng định mỗi \(x_i\) là một trong các giá trị \(A\), \(B\), \(C\), \(A+B\), \(B+C\), \(C+A\) hoặc \(A+B+C\). Tuy nhiên, Elsie có thể đang nói dối; các số \(x_i\) có thể không tương ứng với bất kỳ bộ ba hợp lệ \((A,B,C)\) nào.

Bessie thấy bài toán này quá khó hiểu, vì vậy hãy xác định số bộ ba \((A,B,C)\) phù hợp với các số Elsie đã đưa ra. Kết quả có thể bằng không.

Mỗi tệp dữ liệu vào chứa \(T\) bộ test (\(1\le T\le100\)) cần được giải độc lập.

Dữ liệu vào

Dòng đầu tiên chứa \(T\).

Mỗi bộ test bắt đầu bằng \(N\), số số nguyên Elsie cho Bessie. Dòng thứ hai của bộ test chứa \(N\) số nguyên phân biệt \(x_1,x_2,\ldots,x_N\).

Dữ liệu ra

Với mỗi bộ test, in số bộ ba \((A,B,C)\) phù hợp với các số Elsie đã đưa ra.

Phân nhóm

• Trong các test 1-4, mọi \(x_i\) không vượt quá \(50\).
• Các test 5-6 thỏa mãn \(N=7\).
• Các test 7-15 không có ràng buộc bổ sung.

Ví dụ

10
7
1 2 3 4 5 6 7
4
4 5 7 8
4
4 5 7 9
4
4 5 7 10
4
4 5 7 11
4
4 5 7 12
4
4 5 7 13
4
4 5 7 14
4
4 5 7 15
4
4 5 7 16

1
3
5
1
4
3
0
0
0
1

Với \(x=\{4,5,7,9\}\), năm bộ ba có thể là:

Nguồn

USACO 2021 US Open, Silver - Do You Know Your ABCs?: https://usaco.org/index.php?page=viewproblem2&cpid=1135

Tác giả: Benjamin Qi.

Bessie đã theo học chương trình tiến sĩ khoa học máy tính vì yêu thích ngành này, đồng thời bị cuốn hút bởi viễn cảnh một ngày nào đó trở thành “Tiến sĩ Bessie”. Sau một thời gian nghiên cứu, cô đã công bố \(N\) bài báo (\(1\le N\le10^5\)); bài báo thứ \(i\) nhận được \(c_i\) lượt trích dẫn (\(0\le c_i\le10^5\)) từ các bài báo khác trong giới nghiên cứu.

Bessie nghe nói thành công của một nhà khoa học có thể được đo bằng chỉ số \(h\). Chỉ số \(h\) là số nguyên lớn nhất \(h\) sao cho nhà khoa học có ít nhất \(h\) bài báo, mỗi bài có ít nhất \(h\) lượt trích dẫn. Ví dụ, một người có \(4\) bài báo với số lượt trích dẫn tương ứng là \((1,100,2,3)\) có chỉ số \(h\) bằng \(2\); nếu các số lượt trích dẫn là \((1,100,3,3)\) thì chỉ số \(h\) bằng \(3\).

Để tăng chỉ số \(h\), Bessie dự định viết tối đa \(K\) bài tổng quan (\(0\le K\le10^5\)), mỗi bài trích dẫn nhiều bài báo trước đây của cô. Tuy nhiên, do giới hạn số trang, mỗi bài tổng quan chỉ có thể trích dẫn tối đa \(L\) bài báo (\(0\le L\le10^5\)). Một bài báo không thể được trích dẫn nhiều lần trong cùng một bài tổng quan, nhưng có thể được trích dẫn trong nhiều bài tổng quan.

Hãy xác định chỉ số \(h\) lớn nhất mà Bessie có thể đạt được sau khi viết các bài tổng quan này. Bessie không được trích dẫn một bài tổng quan từ một bài tổng quan khác của chính mình.

Lưu ý rằng cố vấn của Bessie có lẽ nên nói cho cô biết việc viết bài tổng quan chỉ nhằm tăng chỉ số \(h\) là không đúng đắn về mặt đạo đức; các nhà khoa học khác không nên noi theo Bessie.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(K\) và \(L\).

Dòng thứ hai chứa \(N\) số nguyên \(c_1,\ldots,c_N\) cách nhau bởi dấu cách.

Dữ liệu ra

In chỉ số \(h\) lớn nhất trên một dòng.

Phân nhóm

• Các test 1-6 thỏa mãn \(N\le100\).
• Các test 7-16 không có ràng buộc bổ sung.

Ví dụ

4 4 1
1 100 1 1

3

4 1 4
1 100 1 1

2

Giải thích ví dụ 1. Bessie có thể viết tối đa \(4\) bài tổng quan, mỗi bài trích dẫn tối đa \(1\) bài báo. Nếu cô trích dẫn mỗi bài trong số bài báo thứ nhất và thứ ba hai lần, chỉ số \(h\) của cô trở thành \(3\).

Giải thích ví dụ 2. Bessie có thể viết nhiều nhất một bài tổng quan. Nếu cô trích dẫn bất kỳ bài nào trong số bài báo thứ nhất, thứ ba hoặc thứ tư ít nhất một lần, chỉ số \(h\) của cô trở thành \(2\).

Nguồn

USACO 2021 US Open, Silver - Acowdemia: https://usaco.org/index.php?page=viewproblem2&cpid=1136

Tác giả: Dhruv Rohatgi.