USACO 2021 - Tháng 1 - Hạng Đồng

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, Bessie đã ngân nga cowphabet hết lần này đến lần khác, và Farmer John 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 John nghe Bessie đọc, hãy tính số lần ít nhất Bessie phải ngân nga toàn bộ cowphabet để Farmer John có thể nghe được xâu đó. Farmer John không phải lúc nào cũng chú ý nên có thể đã bỏ lỡ một số chữ cái Bessie đọc. Xâu được cho chỉ gồm những chữ cái ông nhớ đã nghe thấy.

Dữ liệu vào

Dòng đầu tiên chứa 26 chữ cái thường từ a đến z theo thứ tự xuất hiện trong cowphabet.

Dòng tiếp theo chứa xâu chữ cái thường mà Farmer John nghe Bessie đọc. Xâu có độ dài từ \(1\) đến \(1000\).

Dữ liệu ra

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

Phân nhóm

• Trong các test 2-5, cowphabet có thứ tự giống bảng chữ cái thông thường.
• Trong các test 6-10, không có ràng buộc bổ sung.

Ví dụ

abcdefghijklmnopqrstuvwxyz
mood

3

abcdefghijklMnOpqrstuvwxyz
abcdefghijklmnOpqrstuvwxyz
abcDefghijklmnopqrstuvwxyz

Nguồn

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

Tác giả: Nick Wu.

Farmer John lại đang cố chụp ảnh \(N\) con bò của mình (\(2\le N\le 1000\)).

Mỗi con bò có một số nguyên "mã giống" trong đoạn \(1\ldots100\). Farmer John có một ý tưởng rất đặc biệt cho bức ảnh: ông muốn chia tất cả các con bò thành những nhóm rời nhau, tức mỗi con thuộc đúng một nhóm, rồi xếp các nhóm sao cho tổng mã giống của các con trong nhóm đầu tiên là số chẵn, tổng trong nhóm thứ hai là số lẻ, và cứ thế xen kẽ chẵn, lẻ.

Số nhóm lớn nhất Farmer John có thể tạo là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Dòng tiếp theo chứa \(N\) số nguyên, cách nhau bởi dấu cách, là mã giống của \(N\) con bò.

Dữ liệu ra

In số nhóm lớn nhất có thể có trong bức ảnh của Farmer John. Có thể chứng minh rằng luôn tồn tại ít nhất một cách chia hợp lệ.

Phân nhóm

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

Ví dụ

7
1 3 5 7 9 11 13

3

7
11 2 17 13 1 15 3

5

Nguồn

USACO 2021 January Contest, Bronze - Even More Odd Photos: https://usaco.org/index.php?page=viewproblem2&cpid=1084

Tác giả: Nick Wu.

(dịch đại khái)

Cho \(N\) \((1 \leq N \leq 20)\) chú bò với độ cao \(a_1, a_2, \dots, a_N\). Trang trại có \(N\) chuồng với giới hạn độ cao \(b_1, b_2, \dots, b_N\) (tức, nếu \(b_5=17\), thì chỉ có chú bò cao không quá 17 đơn vị mới được ở chuồng 5).

Có bao nhiêu cách xếp bỏ vào các chuồng sao cho mỗi chú bò ở một chuồng khác nhau, và chú bò nào cũng ở trong chuồng mà không vượt giới hạn độ cao của chuồng đó?

Dữ liệu đầu vào

• Dòng đầu tiên chứa số \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_n\) \((1 \leq a_i \leq 10^9)\)
• Dòng thứ ba chứa \(N\) số nguyên \(b_1, b_2, \dots, b_n\) \((1 \leq b_i \leq 10^9)\)

Định dạng đầu ra

• Số lượng cách thỏa mãn đề. Đáp án không vượt quá kiểu dữ liệu số nguyên 64-bit (long long trong C++)

Điểm số

• Test 1-5 thỏa mãn \(N \leq 8\).
• Test 6-12 không có giới hạn nào khác.

Ví dụ

4
1 2 3 4
2 4 3 4

8