USACO 2025 - Tháng 1 - Hạng Bạc

\(N\) (\(1 \leq N \leq 5 \cdot 10^5\)) con bò của Farmer John đang đứng thành một hàng, với bò \(1\) ở đầu hàng và bò \(N\) ở cuối hàng. Các con bò của FJ cũng thuộc nhiều loài khác nhau. Ông ký hiệu mỗi loài bằng một số nguyên từ \(1\) đến \(N\). Con bò thứ \(i\) tính từ đầu hàng thuộc loài \(a_i\) (\(1 \leq a_i \leq N\)).

FJ đang đưa đàn bò đến khám tại một bệnh viện bò địa phương. Tuy nhiên, bác sĩ thú y cho bò rất kén chọn và chỉ muốn khám con bò thứ \(i\) trong hàng nếu nó thuộc loài \(b_i\) (\(1 \leq b_i \leq N\)).

FJ lười biếng và không muốn sắp xếp lại hoàn toàn đàn bò. Ông sẽ thực hiện thao tác sau đúng một lần.

• Chọn hai số nguyên \(l\) và \(r\) sao cho \(1 \leq l \le r \leq N\). Đảo ngược thứ tự các con bò nằm giữa con bò thứ \(l\) và con bò thứ \(r\) trong hàng, tính cả hai đầu.

FJ muốn đo lường mức độ hiệu quả của cách làm này. Hãy tìm tổng số con bò được bác sĩ thú y khám trên tất cả \(N(N+1)/2\) thao tác có thể.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\).

Dòng thứ hai chứa \(a_1, a_2, \ldots, a_N\).

Dòng thứ ba chứa \(b_1, b_2, \ldots, b_N\).

Dữ liệu ra

In một dòng chứa tổng số con bò được bác sĩ thú y khám trên tất cả các thao tác có thể.

Ví dụ

3
1 3 2
3 2 1

3

3
1 2 3
1 2 3

12

7
1 3 2 2 1 3 2
3 2 2 1 2 3 1

60

Phân nhóm

• Input 4: \(N\le 100\).
• Input 5: \(N\le 5000\).
• Inputs 6-9: \(a_i, b_i\) đều được sinh ngẫu nhiên đều trong đoạn \([1,N]\).
• Inputs 10-15: \(a_i, b_i\) đều được sinh ngẫu nhiên đều trong đoạn \([1,2]\).
• Inputs 16-23: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Silver — Cow Checkups

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1470

Tác giả đề: Chongtian Ma, Haokai Ma và Alex Liang

Lại là một ngày lạnh lẽo và buồn chán tại trang trại của Farmer John. Để giết thời gian, Farmer John đã nghĩ ra một hoạt động giải trí thú vị liên quan đến việc thực hiện các thao tác trên một mảng số nguyên.

Farmer John có một mảng \(a\) gồm \(N\) (\(1 \leq N \leq 2 \cdot 10^5\)) số nguyên không âm và một số nguyên \(M\) (\(1 \leq M \leq 10^9\)). Sau đó, FJ sẽ hỏi Bessie một số nguyên \(x\). Trong một thao tác, FJ có thể chọn một chỉ số \(i\) rồi trừ \(1\) khỏi hoặc cộng \(1\) vào \(a_i\). Giá trị buồn chán của FJ là số thao tác ít nhất ông phải thực hiện sao cho \(a_i-x\) chia hết cho \(M\) với mọi \(1 \leq i \leq N\).

Trong tất cả các giá trị \(x\) có thể, hãy in giá trị buồn chán nhỏ nhất có thể của FJ.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1 \leq T \leq 10\)), số bộ test độc lập cần giải.

Dòng đầu tiên của mỗi bộ test chứa \(N\) và \(M\).

Dòng thứ hai của mỗi bộ test chứa \(a_1, a_2, ..., a_N\) (\(0 \leq a_i \leq 10^9\)).

Đảm bảo tổng \(N\) trên tất cả các bộ test không vượt quá \(5 \cdot 10^5\).

Dữ liệu ra

Với mỗi bộ test, in trên một dòng một số nguyên là giá trị buồn chán nhỏ nhất có thể của FJ trong tất cả các giá trị \(x\) có thể.

Ví dụ

2
5 9
15 12 18 3 8
3 69
1 988244353 998244853

10
21

Phân nhóm

• Input 2: \(N \le 1000\) và \(M \le 1000\).
• Input 3: \(N\le 1000\).
• Inputs 4-5: \(M\le 10^5\).
• Inputs 6-16: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Silver — Farmer John's Favorite Operation

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1471

Tác giả đề: Chongtian Ma

Bessie có một bảng cộng kích thước \(N\times N\) (\(1\le N\le 1000\)), trong đó số nguyên ở ô thuộc hàng \(r\) và cột \(c\) là \(r+c\), với mọi \(1\le r,c\le N\). Ví dụ, với \(N=3\), bảng sẽ trông như sau:

2 3 4
3 4 5
4 5 6

Không may, Elsie đã lấy được bảng và hoán vị nó bằng cách thực hiện ba loại thao tác sau bao nhiêu lần tùy ý:

1. Hoán đổi hai hàng.
2. Hoán đổi hai cột.
3. Chọn hai giá trị \(a\) và \(b\) đều xuất hiện trong bảng, sau đó đồng thời đổi mọi lần xuất hiện của \(a\) thành \(b\) và mọi lần xuất hiện của \(b\) thành \(a\).

Elsie luôn thực hiện các thao tác theo thứ tự tăng dần của loại; nghĩa là trước tiên cô thực hiện tùy ý (có thể không lần nào) các thao tác loại \(1\), sau đó loại \(2\), và cuối cùng là loại \(3\).

Hãy giúp Bessie khôi phục một trạng thái khả dĩ của bảng sau khi Elsie đã thực hiện xong tất cả thao tác loại \(1\) và \(2\), nhưng trước khi thực hiện bất kỳ thao tác loại \(3\) nào. Có thể có nhiều đáp án, trong trường hợp đó bạn cần in đáp án nhỏ nhất theo thứ tự từ điển.

Để so sánh hai bảng theo thứ tự từ điển, hãy so sánh các phần tử đầu tiên mà chúng khác nhau khi đọc cả hai bảng theo thứ tự tự nhiên (các hàng từ trên xuống dưới, trong mỗi hàng từ trái sang phải).

Dữ liệu vào

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

\(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên, biểu diễn bảng cộng của Bessie sau khi Elsie đã hoán vị nó.

Dữ liệu ra

Trạng thái nhỏ nhất theo thứ tự từ điển có thể có của bảng sau tất cả thao tác loại \(1\) và \(2\), nhưng trước bất kỳ thao tác loại \(3\) nào. Đảm bảo đáp án tồn tại.

Ví dụ

1
2

2

3
3 4 2
5 2 3
6 3 5

4 2 3
5 3 4
6 4 5

2 3 4
3 4 5
4 5 6
-> (thao tác 1: hoán đổi cột 2 và 3)
2 4 3
3 5 4
4 6 5
-> (thao tác 1: hoán đổi cột 1 và 2)
4 2 3
5 3 4
6 4 5
-> (thao tác 3: hoán đổi giá trị 2 và 3)
4 3 2
5 2 4
6 4 5
-> (thao tác 3: hoán đổi giá trị 3 và 4)
3 4 2
5 2 3
6 3 5

4 6 5
3 5 4
2 4 3

6
8 10 5 6 7 4
12 11 10 4 8 2
5 4 6 7 9 8
10 2 4 8 5 12
6 8 7 9 3 5
4 12 8 5 6 10

7 5 8 9 10 6
4 2 5 6 7 3
8 6 9 10 11 7
5 3 6 7 8 4
9 7 10 11 12 8
6 4 7 8 9 5

Phân nhóm

• Inputs 4-5: \(N\le 6\).
• Inputs 6-7: \(N\le 8\).
• Inputs 8-11: \(N\le 100\).
• Inputs 12-15: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Silver — Table Recovery

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1472

Tác giả đề: Benjamin Qi