USACO 2021 - Tháng 1 - Hạng Vàng - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	USACO 2021 - Uddered but not Herd	100 (p)	4.0s	512M
2	USACO 2021 - Telephone	100 (p)	4.0s	512M
3	USACO 2021 - Dance Mooves	100 (p)	4.0s	512M

1. USACO 2021 - Uddered but not Herd

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Một sự thật ít người biết là bò có phiên bản bảng chữ cái riêng, gọi là "cowphabet". Nó gồm 26 chữ cái từ a đến z, nhưng khi đọc cowphabet, một con bò liệt kê các chữ cái theo một thứ tự cụ thể có thể khác thứ tự abcdefghijklmnopqrstuvwxyz quen thuộc.

Để giết thời gian, Mildred, chị em họ của Bessie, đã ngân nga cowphabet hết lần này đến lần khác, và Farmer Nhoj muốn biết cô đã ngân nga bao nhiêu lần.

Cho một xâu chữ cái thường mà Farmer Nhoj nghe Mildred đọc, hãy tính số lần ít nhất Mildred phải ngân nga toàn bộ cowphabet để ông có thể nghe được xâu đó. Farmer Nhoj không phải lúc nào cũng chú ý nên có thể đã bỏ lỡ một số chữ cái Mildred đọc. Xâu được cho chỉ gồm những chữ cái ông nhớ đã nghe thấy.

Lưu ý: Giới hạn thời gian cho mỗi test của bài này gấp đôi mức mặc định.

Dữ liệu vào

Dòng duy nhất chứa xâu chữ cái thường mà Farmer Nhoj nghe Mildred đọc. Xâu có độ dài từ \(1\) đến \(10^5\).

Dữ liệu ra

In số lần ít nhất Mildred phải ngân nga toàn bộ cowphabet.

Phân nhóm

Trong các test 1-5, Farmer Nhoj chỉ nghe những chữ cái xuất hiện trong tên Mildred hoặc Bessie.
Trong các test 6-16, Farmer Nhoj không nghe bất kỳ chữ cái nào xuất hiện trong tên Mildred.

Ví dụ

Ví dụ 1

Input

mildredree

Output

Giải thích

Mildred phải ngân nga cowphabet ít nhất ba lần. Cô chỉ cần ngân nga ba lần nếu cowphabet bắt đầu bằng mildre và Farmer Nhoj nghe được các chữ cái viết hoa dưới đây:

MILDREabcfghjknopqstuvwxyz
milDREabcfghjknopqstuvwxyz
mildrEabcfghjknopqstuvwxyz

Nguồn

USACO 2021 January Contest, Gold - Uddered but not Herd: https://usaco.org/index.php?page=viewproblem2&cpid=1089

Tác giả: Nick Wu và Brian Dean.

2. USACO 2021 - Telephone

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

\(N\) con bò của Farmer John, được đánh số \(1\ldots N\), đang đứng thành một hàng (\(1\le N\le 5\cdot10^4\)). Con bò thứ \(i\) có mã giống \(b_i\) trong đoạn \(1\ldots K\), với \(1\le K\le 50\). Đàn bò cần bạn giúp tìm cách tốt nhất để truyền một thông điệp từ bò \(1\) đến bò \(N\).

Truyền thông điệp từ bò \(i\) đến bò \(j\) mất \(|i-j|\) đơn vị thời gian. Tuy nhiên, không phải mọi giống bò đều sẵn sàng liên lạc với nhau. Điều này được mô tả bằng ma trận \(S\) kích thước \(K\times K\), trong đó \(S_{ij}=1\) nếu một con bò giống \(i\) sẵn sàng truyền thông điệp cho một con bò giống \(j\), và bằng \(0\) nếu không. Không nhất thiết \(S_{ij}=S_{ji}\); thậm chí có thể \(S_{ii}=0\) nếu bò giống \(i\) không sẵn sàng liên lạc với nhau.

Hãy xác định thời gian ít nhất cần thiết để truyền thông điệp.

Dữ liệu vào

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

Dòng tiếp theo chứa \(N\) số nguyên \(b_1,b_2,\ldots,b_N\), cách nhau bởi dấu cách.

\(K\) dòng tiếp theo mô tả ma trận \(S\). Mỗi dòng là một xâu gồm \(K\) bit; \(S_{ij}\) là bit thứ \(j\) của xâu thứ \(i\) tính từ trên xuống.

Dữ liệu ra

In một số nguyên là thời gian ít nhất cần thiết. Nếu không thể truyền thông điệp từ bò \(1\) đến bò \(N\), in \(-1\).

Phân nhóm

Các test 1-5 thỏa mãn \(N\le 1000\).
Các test 6-13 không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Dãy truyền tối ưu là \(1\to4\to3\to5\). Tổng thời gian là \(|1-4|+|4-3|+|3-5|=6\).

Nguồn

USACO 2021 January Contest, Gold - Telephone: https://usaco.org/index.php?page=viewproblem2&cpid=1090

Tác giả: Dhruv Rohatgi.

3. USACO 2021 - Dance Mooves

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Những chú bò của Farmer John đang biểu diễn các bước nhảy mới!

Ban đầu, cả \(N\) con bò (\(2\le N\le 10^5\)) đứng thành một hàng, với bò \(i\) ở vị trí thứ \(i\). Chuỗi động tác gồm \(K\) cặp vị trí (\(1\le K\le 2\cdot10^5\)): \((a_1,b_1),(a_2,b_2),\ldots,(a_K,b_K)\). Ở phút thứ \(i=1\ldots K\), hai con bò đang đứng tại vị trí \(a_i\) và \(b_i\) đổi chỗ.

Cùng \(K\) lần đổi chỗ này lại diễn ra trong các phút \(K+1\ldots2K\), rồi \(2K+1\ldots3K\), và tiếp tục lặp theo chu kỳ trong tổng cộng \(M\) phút (\(1\le M\le 10^{18}\)). Nói cách khác:

Phút \(1\): bò tại \(a_1\) và \(b_1\) đổi chỗ.
Phút \(2\): bò tại \(a_2\) và \(b_2\) đổi chỗ.
\(\ldots\)
Phút \(K\): bò tại \(a_K\) và \(b_K\) đổi chỗ.
Phút \(K+1\): bò tại \(a_1\) và \(b_1\) đổi chỗ.
Phút \(K+2\): bò tại \(a_2\) và \(b_2\) đổi chỗ.
Và cứ tiếp tục như vậy.

Với mỗi con bò, hãy xác định số vị trí phân biệt trong hàng mà nó từng đứng.

Lưu ý: Giới hạn thời gian cho mỗi test của bài này gấp đôi mức mặc định.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(K\) và \(M\). Mỗi dòng thứ \(i\) trong \(K\) dòng tiếp theo chứa \(a_i\) và \(b_i\) (\(1\le a_i<b_i\le N\)).

Dữ liệu ra

In \(N\) dòng, dòng thứ \(i\) chứa số vị trí phân biệt mà bò \(i\) từng đến.

Phân nhóm

Các test 1-5 thỏa mãn \(N\le 100\), \(K\le 200\).
Các test 6-10 thỏa mãn \(M=10^{18}\).
Các test 11-20 không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Sau \(7\) phút, các con bò theo thứ tự vị trí tăng dần là \([3,4,5,2,1,6]\).

Bò \(1\) đến các vị trí \(\{1,2,3,4,5\}\).
Bò \(2\) đến các vị trí \(\{1,2,3,4\}\).
Bò \(3\) đến các vị trí \(\{1,2,3\}\).
Bò \(4\) đến các vị trí \(\{2,3,4\}\).
Bò \(5\) đến các vị trí \(\{3,4,5\}\).
Bò \(6\) không bao giờ di chuyển nên luôn ở vị trí \(6\).

Nguồn

USACO 2021 January Contest, Gold - Dance Mooves: https://usaco.org/index.php?page=viewproblem2&cpid=1091

Tác giả: Chris Zhang.