USACO 2022 - Tháng 2 - Hạng Vàng

Farmer John có \(N\) món quà được đánh số \(1\ldots N\) dành cho \(N\) con bò cũng được đánh số \(1\ldots N\) (\(1\le N\le 18\)). Mỗi con bò có một danh sách mong muốn là một hoán vị của toàn bộ \(N\) món quà; con bò thích những món xuất hiện sớm hơn trong danh sách hơn những món xuất hiện muộn hơn.

FJ đã lười biếng và chỉ gán quà \(i\) cho bò \(i\) với mọi \(i\). Giờ đây, đàn bò đã tụ họp và quyết định phân phối lại các món quà sao cho sau khi phân phối lại, mỗi con bò nhận được chính món quà ban đầu của mình hoặc một món mà nó thích hơn món ban đầu.

Còn có một ràng buộc bổ sung: một món quà chỉ được phân phối lại cho một con bò nếu ban đầu nó được gán cho một con bò cùng giống (mỗi con bò là Holstein hoặc Guernsey). Cho \(Q\) (\(1\le Q\le\min(10^5,2^N)\)) chuỗi giống độ dài \(N\), với mỗi chuỗi hãy đếm số cách phân phối lại phù hợp với chuỗi đó.

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 danh sách ưu tiên của một con bò. Bảo đảm rằng mỗi dòng là một hoán vị của \(1\dots N\).

Dòng tiếp theo chứa \(Q\).

\(Q\) dòng cuối, mỗi dòng chứa một chuỗi giống dài \(N\) ký tự và chỉ gồm các ký tự G và H. Không có chuỗi giống nào xuất hiện nhiều hơn một lần.

Dữ liệu ra

Với mỗi chuỗi giống, in trên một dòng mới số cách phân phối lại phù hợp với chuỗi đó.

Phân nhóm

• Với \(T=2,\ldots,13\), test \(T\) thỏa mãn \(N=T+4\).
• Các test 14–18 thỏa mãn \(N=18\).

Ví dụ

4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4
5
HHHH
HHGG
GHGH
HGGG
GHHG

2
1
1
2
2

Nguồn

USACO 2022 February Contest, Gold — Redistributing Gifts: https://usaco.org/index.php?page=viewproblem2&cpid=1209

Tác giả: Benjamin Qi.

Để đủ điều kiện tham dự trại hè dành cho bò, Bessie cần đạt điểm tốt ở bài cuối cùng của kỳ thi USACOW Open. Bài này có \(T\) bộ test phân biệt (\(2\le T\le 10^3\)) với trọng số bằng nhau, trong đó bộ test đầu tiên là ví dụ. Điểm cuối cùng của cô bằng số bộ test mà lần nộp cuối cùng vượt qua.

Đáng tiếc, Bessie quá mệt để suy nghĩ về bài toán, nhưng vì đáp án của mỗi bộ test chỉ là "yes" hoặc "no", cô có một kế hoạch! Cụ thể, cô quyết định liên tục nộp lời giải bất định sau:

if input == sample_input:
  print sample_output
else:
  print "yes" or "no" each with probability 1/2, independently for each test case

Lưu ý rằng với mọi bộ test ngoài ví dụ, chương trình này có thể sinh kết quả khác khi được nộp lại, vì vậy số bộ test mà nó vượt qua sẽ thay đổi.

Bessie biết rằng tổng cộng cô không thể nộp quá \(K\) (\(1\le K\le 10^9\)) lần, vì nếu không cô chắc chắn sẽ bị loại. Giá trị kỳ vọng lớn nhất có thể của điểm số cuối cùng của Bessie là bao nhiêu, giả sử cô tuân theo chiến lược tối ưu?

Dữ liệu vào

Dòng duy nhất chứa hai số nguyên \(T\) và \(K\) cách nhau bởi dấu cách.

Dữ liệu ra

In đáp án dưới dạng số thập phân có sai số tuyệt đối hoặc tương đối so với đáp án thực tế không quá \(10^{-6}\).

Phân nhóm

• Các test 3–6 thỏa mãn \(T\le 25\) và \(K\le 100\).
• Các test 7–9 thỏa mãn \(K\le 10^6\).
• Các test 10–17 không có ràng buộc bổ sung.

Ví dụ

2 3

1.875

4 2

2.8750000000000000000

Nguồn

USACO 2022 February Contest, Gold — Cow Camp: https://usaco.org/index.php?page=viewproblem2&cpid=1210

Tác giả: Benjamin Qi.

\(N\) con bò của Farmer John (\(1\leq N\leq 10^5\)) sống rải rác cách xa nhau trên trang trại và muốn xây dựng một mạng liên lạc để có thể trao đổi tin nhắn điện tử dễ dàng hơn (tất nhiên, mọi tin nhắn đều chứa các biến thể của "moo").

Con bò thứ \(i\) nằm tại một vị trí phân biệt \((x_i,y_i)\), trong đó \(0\leq x_i\leq 10^6\) và \(0\leq y_i\leq 10\). Chi phí xây dựng một liên kết liên lạc giữa bò \(i\) và bò \(j\) bằng bình phương khoảng cách giữa chúng: \((x_i-x_j)^2+(y_i-y_j)^2\).

Hãy tính chi phí nhỏ nhất cần thiết để xây dựng một mạng liên lạc mà qua đó mọi con bò đều có thể liên lạc. Hai con bò có thể liên lạc nếu chúng được nối trực tiếp bởi một liên kết, hoặc nếu có một chuỗi liên kết mà tin nhắn có thể đi theo.

Lưu ý: giới hạn thời gian của bài này là 4 giây, gấp đôi mức mặc định.

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ả tọa độ nguyên \(x\) và \(y\) của một con bò.

Dữ liệu ra

In chi phí nhỏ nhất của một mạng cho phép mọi con bò liên lạc. Lưu ý rằng chi phí này có thể quá lớn để lưu trong số nguyên 32 bit và có thể cần sử dụng số nguyên 64 bit (chẳng hạn kiểu long long trong C++).

Phân nhóm

• Các test 2–3 thỏa mãn \(N\le 1000\).
• Các test 4–15 không có ràng buộc bổ sung.

Ví dụ

10
83 10
77 2
93 4
86 6
49 1
62 7
90 3
63 4
40 10
72 0

660

Nguồn

USACO 2022 February Contest, Gold — Moo Network: https://usaco.org/index.php?page=viewproblem2&cpid=1211

Tác giả: Brian Dean.