USACO 2025 - Tháng 2 - Hạng Đồng

Farmer John có một tấm toan hình vuông được biểu diễn bằng một lưới \(N \times N\) ô (\(2 \leq N \leq 2000\), \(N\) chẵn). Ông vẽ lên tấm toan theo các bước sau:

1. Đầu tiên, ông chia tấm toan thành bốn góc phần tư bằng nhau, ngăn cách bởi các đường ngang và dọc đi qua tâm tấm toan.
2. Tiếp theo, ông vẽ một bức tranh tuyệt đẹp ở góc phần tư trên bên phải. Mỗi ô trong góc phần tư này có trạng thái được tô (ký hiệu bằng #) hoặc không được tô (ký hiệu bằng .).
3. Cuối cùng, vì rất tự hào về bức tranh của mình, ông phản chiếu nó qua các đường ngang và dọc nói trên sang các góc phần tư còn lại của tấm toan.

Ví dụ, giả sử \(N=8\) và ở bước 2, FJ vẽ bức tranh sau trong góc phần tư trên bên phải:

.#..
.#..
.##.
....

Sau khi phản chiếu qua các đường ngang và dọc sang các góc phần tư khác ở bước 3, tấm toan sẽ trông như sau:

..#..#..
..#..#..
.##..##.
........
........
.##..##.
..#..#..
..#..#..

Tuy nhiên, trong khi FJ đang ngủ, Bessie đột nhập vào kho và đánh cắp tấm toan quý giá của ông. Cô phá hoại toàn bộ tấm toan — xóa màu ở một số ô đã tô và tô thêm nhiều ô khác! Trước khi FJ thức dậy, cô trả tấm toan lại cho ông.

FJ muốn chỉnh sửa tấm toan để nó một lần nữa thỏa mãn điều kiện phản chiếu, tức là nó là kết quả của việc phản chiếu góc phần tư trên bên phải sang từng góc phần tư còn lại. Vì tài nguyên có hạn, ông muốn làm điều này với ít thao tác nhất có thể, trong đó mỗi thao tác là tô một ô hoặc xóa màu khỏi một ô.

Bạn được cho tấm toan sau khi bị Bessie phá hoại, cùng một dãy \(U\) (\(0\le U \leq 10^5\)) cập nhật trên tấm toan; mỗi cập nhật đảo trạng thái của một ô: từ # thành . hoặc ngược lại. Trước mọi cập nhật và sau mỗi cập nhật, hãy in ra số thao tác tối thiểu \(x\) mà FJ cần thực hiện để thỏa mãn điều kiện phản chiếu.

Dữ liệu vào

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

\(N\) dòng tiếp theo, mỗi dòng chứa \(N\) ký tự biểu diễn tấm toan sau khi bị Bessie phá hoại. Mỗi ký tự là # hoặc ..

\(U\) dòng sau đó, mỗi dòng chứa hai số nguyên \(r\) và \(c\), với \(1 \leq r,c \leq N\), biểu diễn một cập nhật tại ô ở hàng thứ \(r\) tính từ trên xuống và cột thứ \(c\) tính từ trái sang.

Dữ liệu ra

In ra \(U+1\) dòng biểu diễn \(x\) trước mọi cập nhật và sau mỗi cập nhật.

Ví dụ

4 5
..#.
##.#
####
..##
1 3
2 3
4 3
4 4
4 4

4
3
2
1
0
1

....
####
####
....

....
##.#
####
..##

....
####
####
..##

Phân nhóm

• Dữ liệu 2–3: \(N \le 4\).
• Dữ liệu 4–6: \(U \le 10\).
• Dữ liệu 7–16: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 February Contest, Bronze — Reflection. Tác giả: Chongtian Ma.

https://usaco.org/index.php?page=viewproblem2&cpid=1491

Bạn được cho một mảng \(a\) gồm \(N\) số nguyên không âm \(a_1,a_2,\dots,a_N\) (\(1\le N\le 2\cdot 10^5\), \(0\le a_i\le N\)). Trong một thao tác, bạn có thể thay đổi bất kỳ phần tử nào của \(a\) thành một số nguyên không âm bất kỳ.

mex của một mảng là số nguyên không âm nhỏ nhất không xuất hiện trong mảng. Với mỗi \(i\) từ \(0\) đến \(N\), hãy tính số thao tác tối thiểu cần thiết để mex của \(a\) bằng \(i\).

Dữ liệu vào

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

Dòng tiếp theo chứa \(a_1,a_2,\dots,a_N\).

Dữ liệu ra

Với mỗi \(i\) từ \(0\) đến \(N\), in trên một dòng riêng số thao tác tối thiểu ứng với \(i\). Lưu ý rằng luôn có thể làm cho mex của \(a\) bằng bất kỳ \(i\) nào từ \(0\) đến \(N\).

Ví dụ

4
2 2 2 0

1
0
3
1
2

Phân nhóm

• Dữ liệu 2–6: \(N\le 10^3\).
• Dữ liệu 7–11: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 February Contest, Bronze — Making Mexes. Tác giả: Benjamin Qi.

https://usaco.org/index.php?page=viewproblem2&cpid=1492

Bessie đang học lập trình bằng một ngôn ngữ lập trình đơn giản. Trước tiên, cô định nghĩa một chương trình hợp lệ, rồi thực thi nó để tạo ra một dãy đầu ra.

Định nghĩa:

• Một chương trình là một dãy không rỗng gồm các câu lệnh.
• Một câu lệnh có dạng PRINT \(c\), trong đó \(c\) là một số nguyên, hoặc có dạng REP \(o\), theo sau bởi một chương trình rồi đến END, trong đó \(o\) là một số nguyên ít nhất bằng \(1\).

Thực thi:

• Thực thi một chương trình nghĩa là thực thi tuần tự các câu lệnh của nó.
• Thực thi câu lệnh PRINT \(c\) sẽ nối \(c\) vào cuối dãy đầu ra.
• Thực thi một câu lệnh bắt đầu bằng REP \(o\) sẽ thực thi tuần tự chương trình bên trong tổng cộng \(o\) lần.

Sau đây là một ví dụ về chương trình mà Bessie biết viết:

REP 3
    PRINT 1
    REP 2
        PRINT 2
    END
END

Chương trình in ra dãy \([1,2,2,1,2,2,1,2,2]\).

Bessie muốn in ra một dãy gồm \(N\) (\(1\le N\le 100\)) số nguyên dương. Elsie thách cô chỉ dùng không quá \(K\) (\(1\le K\le 3\)) câu lệnh PRINT. Lưu ý rằng Bessie có thể dùng bao nhiêu câu lệnh REP tùy ý. Đồng thời, mỗi số nguyên dương trong dãy không lớn hơn \(K\).

Với mỗi trong số \(T\) (\(1\le T\le 100\)) trường hợp kiểm thử độc lập, hãy xác định liệu Bessie có thể viết một chương trình in ra dãy cho trước bằng không quá \(K\) câu lệnh PRINT hay không.

Dữ liệu vào

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

Dòng đầu tiên của mỗi trường hợp kiểm thử chứa hai số nguyên cách nhau bởi dấu cách, \(N\) và \(K\).

Dòng thứ hai của mỗi trường hợp kiểm thử chứa một dãy \(N\) số nguyên dương cách nhau bởi dấu cách, mỗi số không quá \(K\); đây là dãy Bessie muốn tạo ra.

Dữ liệu ra

Với mỗi trường hợp kiểm thử, in YES hoặc NO (phân biệt chữ hoa chữ thường) trên một dòng riêng.

Ví dụ

2
1 1
1
4 1
1 1 1 1

YES
YES

REP 4
    PRINT 1
END

11
4 2
1 2 2 2
4 2
1 1 2 1
4 2
1 1 2 2
6 2
1 1 2 2 1 1
10 2
1 1 1 2 2 1 1 1 2 2
8 3
3 3 1 2 2 1 2 2
9 3
1 1 2 2 2 3 3 3 3
16 3
2 2 3 2 2 3 1 1 2 2 3 2 2 3 1 1
24 3
1 1 2 2 3 3 3 2 2 3 3 3 1 1 2 2 3 3 3 2 2 3 3 3
9 3
1 2 2 1 3 3 1 2 2
6 3
1 2 1 2 2 3

YES
NO
YES
NO
YES
YES
YES
YES
YES
NO
NO

PRINT 1
REP 3
    PRINT 2
END

REP 2
    PRINT 3
END
REP 2
    PRINT 1
    REP 2
        PRINT 2
    END
END

Phân nhóm

• Dữ liệu 3: \(K=1\).
• Dữ liệu 4–7: \(K\le 2\).
• Dữ liệu 8–13: Không có ràng buộc bổ sung.

Nguồn

Đề bài gốc: USACO 2025 February Contest, Bronze — Printing Sequences

Tác giả: Alex Liang.