| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2026 - Chip Exchange | 100 (p) | 4.0s | 512M |
| 2 | USACO 2026 - COW Splits | 100 (p) | 4.0s | 512M |
| 3 | USACO 2026 - Photoshoot | 100 (p) | 4.0s | 512M |
Bessie có \(A\) chip loại A và \(B\) chip loại B (\(0\le A,B\le 10^9\)). Cô có thể thực hiện thao tác sau bao nhiêu lần tùy thích:
Hãy xác định số nguyên không âm nhỏ nhất \(x\) thỏa mãn điều sau: sau khi nhận thêm \(x\) chip ngẫu nhiên, Bessie được đảm bảo có thể đạt được ít nhất \(f_A\) chip loại A (\(0\le f_A\le 10^9\)).
Dòng đầu tiên chứa \(T\), số lượng bộ test độc lập (\(1\le T\le 10^4\)).
Tiếp theo là \(T\) bộ test, mỗi bộ gồm năm số nguyên \(A,B,c_A,c_B,f_A\).
Với mỗi bộ test, in đáp án trên một dòng riêng.
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ụ 1
2
2 3 1 1 6
2 3 1 1 41
0Ví dụ 2
5
0 0 2 3 5
0 1 2 3 5
1 0 2 3 5
10 10 2 3 5
0 0 1 1000000000 10000000009
8
7
0
1000000000000000000Trong bộ test đầu tiên, ban đầu Bessie không có chip nào. Nếu nhận được \(9\) chip bất kỳ, cô có thể thực hiện thao tác để đạt được ít nhất \(5\) chip loại A. Chẳng hạn, nếu nhận được \(2\) chip loại A và \(7\) chip loại B, cô có thể thực hiện thao tác hai lần để đạt được \(6\ge 5\) chip loại A. Tuy nhiên, nếu chỉ nhận được \(8\) chip loại B, cô chỉ có thể đạt được \(4<5\) chip loại A.
Trong bộ test thứ tư, ngay từ đầu cô đã có đủ chip loại A.
USACO 2026 Contest 1, Bronze, bài Chip Exchange. Tác giả: Benjamin Qi.
https://usaco.org/index.php?page=viewproblem2&cpid=1539
Bessie được cho một số nguyên dương \(N\) và một xâu \(S\) có độ dài \(3N\), được tạo bằng cách nối \(N\) xâu độ dài \(3\), trong đó mỗi xâu là một phép dịch vòng của COW. Nói cách khác, mỗi xâu sẽ là COW, OWC hoặc WCO.
Xâu \(X\) là một xâu bình phương khi và chỉ khi tồn tại một xâu \(Y\) sao cho \(X=Y+Y\), trong đó \(+\) biểu thị phép nối xâu. Chẳng hạn, COWCOW và CC là các xâu bình phương, còn COWO và OC thì không.
Trong một thao tác, Bessie có thể xóa khỏi \(S\) một dãy con \(T\) bất kỳ, với \(T\) là một xâu bình phương. Dãy con của một xâu là xâu có thể thu được bằng cách xóa một số (có thể bằng không) ký tự khỏi xâu ban đầu.
Nhiệm vụ của bạn là giúp Bessie xác định liệu có thể biến \(S\) thành xâu rỗng hay không. Ngoài ra, nếu có thể, bạn phải đưa ra một cách thực hiện.
Bessie còn được cho một tham số \(k\) bằng \(0\) hoặc \(1\). Gọi \(M\) là số thao tác trong cách thực hiện của bạn.
Dòng đầu tiên chứa \(T\), số lượng bộ test độc lập (\(1\le T\le 10^4\)), và \(k\) (\(0\le k\le 1\)).
Dòng đầu tiên của mỗi bộ test chứa \(N\) (\(1\le N\le 10^5\)).
Dòng thứ hai của mỗi bộ test chứa \(S\).
Tổng \(N\) trên tất cả các bộ test không vượt quá \(10^5\).
Với mỗi bộ test, in một hoặc hai dòng theo quy tắc sau.
Nếu không thể biến \(S\) thành xâu rỗng, in \(-1\) trên một dòng duy nhất.
Ngược lại, trên dòng đầu tiên, in \(M\) — số thao tác trong cách thực hiện của bạn. Trên dòng thứ hai, in \(3N\) số nguyên cách nhau bởi dấu cách. Số nguyên thứ \(i\), ký hiệu là \(x\), cho biết ký tự thứ \(i\) của \(S\) được xóa trong dãy con của thao tác thứ \(x\) (\(1\le x\le M\)).
Ví dụ 1
3 1
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC-1
1
1 1 1 1 1 1 1 1 1 1 1 1
3
3 3 2 3 3 2 1 1 1 1 1 1 1 1 1 1 1 1Đối với bộ test cuối cùng, số thao tác tối ưu là hai, nên mọi cách thực hiện hợp lệ với \(M=2\) hoặc \(M=3\) đều được chấp nhận.
Với \(M=3\), sau đây là một cách thực hiện:
COWCOW.WW. Khi đó còn lại COCO.Ví dụ 2
3 0
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC-1
1
1 1 1 1 1 1 1 1 1 1 1 1
2
1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2USACO 2026 Contest 1, Bronze, bài COW Splits. Tác giả: Aakash Gokhale.
https://usaco.org/index.php?page=viewproblem2&cpid=1540
Farmer John đang ngắm đàn bò của mình trên một cánh đồng kỳ diệu và muốn chụp ảnh các tập con của đàn bò.
Cánh đồng có thể được xem là một lưới \(N\times N\) (\(1\leq N\leq 500\)), với đúng một chú bò đứng yên tại mỗi vị trí. Máy ảnh của Farmer John có thể chụp một hình vuông \(K\times K\) bất kỳ nằm trong cánh đồng (\(1\leq K\leq \min(N,25)\)).
Tại mọi thời điểm, mỗi chú bò có một giá trị vẻ đẹp từ \(0\) đến \(10^6\). Chỉ số hấp dẫn của một bức ảnh là tổng giá trị vẻ đẹp của những chú bò có trong ảnh.
Ban đầu, giá trị vẻ đẹp của mọi chú bò đều bằng \(0\), vì vậy chỉ số hấp dẫn của mọi bức ảnh lúc đầu đều bằng \(0\).
Tại \(Q\) thời điểm (\(1\leq Q\leq 3\cdot 10^4\)), giá trị vẻ đẹp của một chú bò sẽ tăng thêm một số nguyên dương do ăn loại cỏ kỳ diệu được trồng trên cánh đồng của Farmer John.
Farmer John muốn biết chỉ số hấp dẫn lớn nhất của một bức ảnh mà ông có thể chụp sau mỗi lần trong \(Q\) lần cập nhật.
Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\).
Dòng tiếp theo chứa số nguyên \(Q\).
Mỗi dòng trong \(Q\) dòng tiếp theo chứa ba số nguyên \(r\), \(c\) và \(v\), lần lượt là hàng, cột và giá trị vẻ đẹp mới (\(1\leq r,c\leq N\), \(1\leq v\leq 10^6\)). Đảm bảo rằng giá trị vẻ đẹp mới lớn hơn giá trị vẻ đẹp tại vị trí đó trước lần cập nhật.
In ra \(Q\) dòng, tương ứng với chỉ số hấp dẫn lớn nhất của một bức ảnh sau mỗi lần cập nhật.
Ví dụ 1
4 2
3
2 2 11
3 4 3
3 1 10011
11
111Sau lần cập nhật đầu tiên, một bức ảnh có chỉ số hấp dẫn lớn nhất là bức ảnh có góc trên bên trái tại \((2,2)\) và góc dưới bên phải tại \((3,3)\), với chỉ số hấp dẫn bằng \(11+0+0+0=11\).
Lần cập nhật thứ hai không ảnh hưởng đến chỉ số hấp dẫn lớn nhất.
Sau lần cập nhật thứ ba, bức ảnh có chỉ số hấp dẫn lớn nhất đổi thành bức ảnh có góc trên bên trái tại \((2,1)\) và góc dưới bên phải tại \((3,2)\), với chỉ số hấp dẫn bằng \(0+11+100+0=111\).
Ví dụ 2
3 1
3
2 2 3
2 2 5
2 2 73
5
7Chỉ có một chú bò có giá trị vẻ đẹp dương, nên bức ảnh có chỉ số hấp dẫn lớn nhất sẽ luôn chứa chú bò đó.
USACO 2026 Contest 1, Bronze, bài Photoshoot. Tác giả: Brian Law và Cici Liu.
https://usaco.org/index.php?page=viewproblem2&cpid=1541