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

Những chú bò đã tạo ra một loại câu đố mới mang tên Herdle và nó đã trở thành một hiện tượng lan truyền trong thế giới loài bò.

Mỗi ngày, một câu đố mới được phát hành để những chú bò giải. Câu đố có dạng một lưới \(3\times 3\) biểu diễn một cánh đồng trong trang trại, mỗi ô trên cánh đồng có một chú bò thuộc một giống nhất định. Chỉ có 26 giống có thể xuất hiện, mỗi giống được ký hiệu bằng một chữ cái in hoa khác nhau từ A đến Z. Người chơi không được cho biết cách các giống bò được sắp xếp trên cánh đồng — mục tiêu là tìm ra cách sắp xếp ấy thông qua một loạt lần đoán.

Trong mỗi lần đoán, những chú bò nhập một lưới chữ cái in hoa \(3\times 3\), biểu thị một cách có thể để lấp đầy cánh đồng bằng bò. Một số ô trong dự đoán có thể đúng. Các ô này được tô xanh lá để báo cho những chú bò biết rằng chúng đúng. Những ô khác trong dự đoán có thể chứa bò đúng giống nhưng sai vị trí. Các ô này được tô vàng.

Số ô được tô vàng có thể giúp suy ra số bò thuộc một giống nhất định. Ví dụ, giả sử lưới dự đoán chứa 4 bò giống A, còn lưới đáp án chứa 2 bò giống A, và không có chữ A nào trùng vị trí (tức là không chữ nào được tô xanh lá). Khi đó, chỉ hai chữ A trong lưới dự đoán được tô vàng. Chính xác hơn, nếu có \(x\) bò thuộc một giống nhất định trong lưới dự đoán và \(y<x\) bò thuộc giống này trong lưới đáp án (không tính những con bò đúng vị trí và do đó được tô xanh lá), thì chỉ \(y\) trong số \(x\) con bò của lưới dự đoán được tô vàng.

Cho lưới đáp án đúng và một lưới biểu diễn dự đoán cho đáp án này, hãy tính số ô được tô xanh lá và số ô được tô vàng.

Dữ liệu vào

3 dòng đầu tiên biểu diễn lưới đáp án đúng. 3 dòng tiếp theo biểu diễn một dự đoán cho đáp án này.

Dữ liệu ra

In hai dòng. Trên dòng đầu tiên, in số ô cần được tô xanh lá. Trên dòng thứ hai, in số ô cần được tô vàng.

Phân nhóm

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

Ví dụ

COW
SAY
MOO
WIN
THE
IOI

1
1

AAA
BBB
CCC
AYY
AAA
ZZZ

1
2

Nguồn

USACO 2022 January Contest, Bronze — Herdle: https://usaco.org/index.php?page=viewproblem2&cpid=1179

Tác giả: Brian Dean, lấy cảm hứng từ ứng dụng “Wordle”.

Để giết thời gian trong chuồng, những chú bò thích chơi các trò xúc xắc đơn giản. Một trong số đó được chơi bằng hai viên xúc xắc X và Y. Cả hai được gieo, và viên xúc xắc hiện số lớn hơn sẽ thắng. Nếu cả hai hiện cùng một số, chúng được gieo lại (có thể phải gieo lại nhiều lần, miễn là vẫn tiếp tục hòa). Ta nói xúc xắc X thắng xúc xắc Y nếu xác suất X thắng trò chơi này lớn hơn xác suất Y thắng.

Xét các viên xúc xắc 4 mặt sau:

• Xúc xắc A có các số 4, 5, 6 và 7 trên các mặt.
• Xúc xắc B có các số 2, 4, 5 và 10 trên các mặt.
• Xúc xắc C có các số 1, 4, 8 và 9 trên các mặt.

Các viên xúc xắc này có một tính chất khá thú vị: A thắng B, B thắng C, và C cũng thắng A. Cụ thể, không có viên nào là “tốt nhất” và thắng cả hai viên còn lại. Trong trường hợp không có hai viên xúc xắc nào hòa nhau và không có một viên duy nhất tốt nhất, ta gọi bộ ba xúc xắc là “không bắc cầu”. Trong một bộ ba xúc xắc không bắc cầu, mỗi viên thắng một viên khác và thua viên còn lại.

Cho các số trên các mặt của hai viên xúc xắc 4 mặt A và B, hãy giúp những chú bò xác định xem có cách gán số cho các mặt của viên xúc xắc thứ ba C để bộ xúc xắc trở thành không bắc cầu hay không. Các số trên mặt của mọi viên xúc xắc phải là số nguyên từ 1 đến 10, kể cả hai đầu.

Dữ liệu vào

Mỗi dữ liệu vào gồm nhiều bộ test độc lập, và cần giải đúng tất cả để giải đúng toàn bộ dữ liệu vào. Dòng đầu chứa \(T\) (\(1\le T\le 10\)), là số bộ test cần giải.

\(T\) dòng tiếp theo, mỗi dòng mô tả một bộ test bằng 8 số: các số trên bốn mặt của xúc xắc A, rồi các số trên bốn mặt của xúc xắc B. Mọi số đều nằm trong khoảng từ 1 đến 10 và không nhất thiết được sắp xếp. Cùng một số có thể xuất hiện nhiều lần, kể cả trên cùng một viên xúc xắc.

Dữ liệu ra

In \(T\) dòng. Dòng thứ \(k\) là yes nếu có thể thiết kế xúc xắc C để biến bộ test thứ \(k\) thành một bộ xúc xắc không bắc cầu, và là no nếu không thể.

Phân nhóm

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

Ví dụ

3
4 5 6 7 2 4 5 10
2 2 2 2 1 1 1 1
1 1 1 1 2 2 2 2

yes
no
no

Nguồn

USACO 2022 January Contest, Bronze — Non-Transitive Dice: https://usaco.org/index.php?page=viewproblem2&cpid=1180

Tác giả: Brian Dean.

Do hạn hán, cỏ trên đồng của Nông dân John đã khô héo. Sau nhiều giờ tuyệt vọng và suy ngẫm, Nông dân John nảy ra ý tưởng tuyệt vời là mua ngô để cho những chú bò quý giá của mình ăn.

\(N\) chú bò của FJ (\(1\le N\le 10^5\)) xếp thành một hàng, trong đó chú bò thứ \(i\) có mức đói \(h_i\) (\(0\le h_i\le 10^9\)). Vì bò là động vật có tính xã hội và nhất quyết ăn cùng nhau, cách duy nhất để FJ giảm mức đói của đàn bò là chọn hai chú bò kề nhau \(i\) và \(i+1\), rồi cho mỗi con một túi ngô, khiến mức đói của mỗi con giảm đi một.

FJ muốn cho bò ăn đến khi tất cả có cùng một mức đói không âm. Hãy giúp FJ xác định số túi ngô ít nhất cần dùng để đạt được điều này, hoặc in \(-1\) nếu không thể.

Dữ liệu vào

Mỗi dữ liệu vào gồm nhiều bộ test độc lập, và cần giải đúng tất cả để giải đúng toàn bộ dữ liệu vào. Dòng đầu chứa \(T\) (\(1\le T\le 100\)), là số bộ test cần giải. Tiếp theo là \(T\) bộ test, mỗi bộ được mô tả bằng một cặp dòng. Dòng đầu của mỗi cặp chứa \(N\), dòng thứ hai chứa \(h_1,h_2,\ldots,h_N\). Tổng \(N\) trên mọi bộ test không vượt quá \(10^5\). Giá trị \(N\) có thể khác nhau giữa các bộ test.

Dữ liệu ra

In \(T\) dòng, mỗi dòng ứng với một bộ test.

Lưu ý rằng các số nguyên lớn trong bài có thể đòi hỏi kiểu số nguyên 64 bit (ví dụ long long trong C/C++).

Phân nhóm

• Mọi bộ test trong input 2 thỏa mãn \(N\le 3\) và \(h_i\le 100\).
• Mọi bộ test trong các input 3–8 thỏa mãn \(N\le 100\) và \(h_i\le 100\).
• Mọi bộ test trong các input 9–14 thỏa mãn \(N\le 100\).
• Input 15 không có ràng buộc bổ sung.

Ngoài ra, \(N\) luôn chẵn trong các input 3–5 và 9–11, và \(N\) luôn lẻ trong các input 6–8 và 12–14.

Ví dụ

5
3
8 10 5
6
4 6 4 4 6 4
3
0 1 0
2
1 2
3
10 9 9

14
16
-1
-1
-1

Nguồn

USACO 2022 January Contest, Bronze — Drought: https://usaco.org/index.php?page=viewproblem2&cpid=1181

Tác giả: Arpan Banerjee.