USACO 2026 - Kỳ thi 3 - Hạng Đồng

Bạn có một mảng số nguyên \(a_1\dots a_N\), ban đầu các phần tử nằm trong đoạn \([1,N]\) (\(1\le N\le 2\cdot 10^5\)), cùng với một số nguyên khác không \(K\) (\(-N\le K\le N, K\neq 0\)).

Bạn có thể thực hiện thao tác sau bao nhiêu lần tùy thích (có thể không lần nào): chọn một chỉ số \(i\) và gán \(a_i=a_i+K\).

Hãy tìm số thao tác ít nhất để tất cả các phần tử của mảng đôi một khác nhau.

Dữ liệu vào

Dữ liệu vào gồm \(T\) (\(1\le T\le 10\)) bộ test độc lập. Mỗi bộ test được mô tả như sau:

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

Dòng thứ hai chứa \(a_1\dots a_N\).

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

Dữ liệu ra

Với mỗi bộ test, in một dòng chứa số thao tác ít nhất.

Lưu ý: Do các số nguyên trong bài có thể rất lớn, bạn có thể cần sử dụng kiểu số nguyên 64 bit (ví dụ, long long trong C/C++).

Ví dụ

4
4 1
4 1 4 1
4 -3
4 1 4 1
4 4
4 1 4 1
3 -1
1 1 2

2
4
2
1

4 1 4 1
5 1 4 1 (a_1 += 1)
5 1 4 2 (a_4 += 1)

Phân nhóm

• Dữ liệu 2-4: \(N\le 50\).
• Dữ liệu 5-7: \(N\le 2000\).
• Dữ liệu 8-10: \(K=1\).
• Dữ liệu 11-13: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 3, Bronze — Make All Distinct. Tác giả: Akshaj Arora, Benjamin Qi.
https://usaco.org/index.php?page=viewproblem2&cpid=1587

Với mọi số nguyên dương \(x\), hàm \(f(x)\) được định nghĩa như sau:

• Nếu \(x\) có bất kỳ chữ số nào khác \(0\) và \(1\), với mỗi chữ số của \(x\), đổi chữ số đó thành \(1\) nếu nó lẻ, hoặc thành \(0\) nếu không, rồi trả về \(x\).
• Nếu không, trả về \(x-1\).

Cho một giá trị \(x\) (\(1\leq x<10^{2\cdot 10^5}\)), hãy tìm số lần cần áp dụng \(f\) lên \(x\) để \(x\) trở thành \(0\). Vì số này có thể rất lớn, hãy in phần dư của nó khi chia cho \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\le T\le 10^5\)), số lượng bộ test độc lập.

\(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(x\) chỉ gồm các chữ số từ 0 đến 9 và không có chữ số \(0\) ở đầu.

Đảm bảo tổng số chữ số trong tất cả các số nguyên đầu vào không vượt quá \(10^6\).

Dữ liệu ra

Với mỗi bộ test, in trên một dòng riêng phần dư của số lần cần áp dụng hàm khi chia cho \(10^9+7\).

Ví dụ

2
24680
210

1
4

1
1234567890123456789012345678901234567890

511620083

Phân nhóm

• Dữ liệu 3-5: \(T\le 2000\), \(x<10^9\).
• Dữ liệu 6-7: \(x<10^{18}\).
• Dữ liệu 8-9: \(x<10^{60}\).
• Dữ liệu 10-12: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 3, Bronze — Strange Function. Tác giả: Aidan Bai.
https://usaco.org/index.php?page=viewproblem2&cpid=1588

Farmer John có một xâu yêu thích \(t\) gồm \(M\) ký tự. Ông cũng có \(N\) xâu \(s_1,s_2,\ldots,s_N\), mỗi xâu gồm \(M\) ký tự (\(1\leq N,M\leq 1000\)).

FJ có thể thực hiện hai loại thao tác sau:

1. FJ chọn một xâu bất kỳ \(s_x\) và hai chỉ số \(p\), \(q\). Sau đó, ông hoán đổi ký tự thứ \(p\) và ký tự thứ \(q\) của \(s_x\) (\(1\le x\le N, 1\le p,q\le M\)).
2. FJ chọn hai xâu \(s_x\), \(s_y\) và một chỉ số \(k\). Sau đó, ông hoán đổi ký tự thứ \(k\) của \(s_x\) và ký tự thứ \(k\) của \(s_y\) (\(1\le x,y\le N, 1\le k\le M\)).

Mục tiêu của ông là biến \(s_1\) thành \(t\). Hãy tìm một dãy thao tác bất kỳ đạt được mục tiêu này. Vì FJ đang vội, ông chỉ có thời gian thực hiện tổng cộng tối đa \(2M\) thao tác. Dữ liệu vào đảm bảo có thể đạt được mục tiêu của FJ.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\le T\le 10\)), số lượng bộ test độc lập. Mỗi bộ test có định dạng sau:

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

Dòng thứ hai chứa \(t\).

Tiếp theo là \(N\) dòng, dòng thứ \(i\) chứa \(s_i\).

Dữ liệu vào đảm bảo có thể đạt được mục tiêu của FJ. Tất cả các xâu chỉ chứa các chữ cái tiếng Anh viết thường (a-z).

Dữ liệu ra

Với mỗi bộ test, hãy xuất kết quả như sau:

Trên dòng đầu tiên, in một số nguyên \(K\), là số thao tác bạn sẽ thực hiện. \(K\) phải là một số nguyên không âm không vượt quá \(2M\).

Sau đó, in \(K\) dòng mô tả các thao tác bạn sẽ thực hiện theo thứ tự. Mỗi dòng phải có một trong hai dạng sau:

• 1 x p q
• 2 x y k

Ví dụ

3
3 6
banana
nabana
banana
nnbaaa
5 3
abc
def
bca
ghi
jkl
mno
3 5
abcde
abcde
abcde
zzzzz

3
2 1 2 1
1 1 3 5
2 1 2 5
5
1 2 1 3
2 1 2 1
1 2 2 3
2 1 2 2
2 1 2 3
0

nabana    Babana    baNaBa    banaNa
banana -> Nanana -> nanana -> nanaBa
nnbaaa    nnbaaa    nnbaaa    nnbaaa

Phân nhóm

• Dữ liệu 2-6: \(N,M\le 100\).
• Dữ liệu 7-12: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 3, Bronze — Swap to Win. Tác giả: Chongtian Ma.
https://usaco.org/index.php?page=viewproblem2&cpid=1589