| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2022 - Minimizing Haybales | 100 (p) | 4.0s | 512M |
| 2 | USACO 2022 - Counting Haybales | 100 (p) | 4.0s | 512M |
| 3 | USACO 2022 - Multiple Choice Test | 100 (p) | 4.0s | 512M |
Bessie đang buồn chán và lại một lần nữa gây rắc rối trong chuồng của Nông dân John. FJ có \(N\) (\(1\le N\le 10^5\)) chồng kiện cỏ khô. Với mỗi \(i\in[1,N]\), chồng thứ \(i\) có \(h_i\) (\(1\le h_i\le 10^9\)) kiện cỏ. Bessie không muốn kiện cỏ nào bị rơi, nên thao tác duy nhất cô có thể thực hiện là:
Dãy chiều cao nhỏ nhất theo thứ tự từ điển mà Bessie có thể thu được sau một chuỗi các thao tác này là gì?
Lưu ý: giới hạn thời gian và bộ nhớ cho bài này lần lượt là 4 giây và 512 MB, gấp đôi giá trị mặc định.
Dòng đầu chứa \(N\) và \(K\). Dòng thứ \(i+1\) chứa chiều cao của chồng kiện cỏ thứ \(i\).
In \(N\) dòng, dòng thứ \(i\) chứa chiều cao của chồng kiện cỏ thứ \(i\) trong lời giải.
Ví dụ 1
5 3
7
7
3
6
26
7
7
2
3Một cách để Bessie đổi chỗ các chồng là:
7 7 3 6 2
-> 7 7 6 3 2
-> 7 7 6 2 3
-> 7 6 7 2 3
-> 6 7 7 2 3
USACO 2022 January Contest, Platinum — Minimizing Haybales: https://usaco.org/index.php?page=viewproblem2&cpid=1188
Tác giả: Daniel Zhang và Benjamin Qi.
Như thường lệ, cô bò Bessie đang gây rắc rối trong chuồng của Nông dân John. FJ có \(N\) (\(1\le N\le 5000\)) chồng kiện cỏ khô. Với mỗi \(i\in[1,N]\), chồng thứ \(i\) có \(h_i\) (\(1\le h_i\le 10^9\)) kiện cỏ. Bessie không muốn kiện cỏ nào bị rơi, nên thao tác duy nhất cô có thể thực hiện là:
Có bao nhiêu cấu hình có thể thu được sau khi thực hiện thao tác trên hữu hạn lần, lấy modulo \(10^9+7\)? Hai cấu hình được coi là giống nhau nếu với mọi \(i\), chồng thứ \(i\) có cùng số kiện cỏ trong cả hai cấu hình.
Dòng đầu chứa \(T\) (\(1\le T\le 10\)), là số bộ test độc lập; cần giải đúng tất cả để giải đúng một dữ liệu vào.
Mỗi bộ test gồm \(N\), rồi một dãy \(N\) chiều cao. Đảm bảo tổng \(N\) trên mọi bộ test không vượt quá \(5000\).
In \(T\) dòng, mỗi dòng ứng với một bộ test.
Ví dụ 1
7
4
2 2 2 3
4
3 3 1 2
4
5 3 4 2
6
3 3 1 1 2 2
6
1 3 3 4 1 2
6
4 1 2 3 5 4
10
1 5 6 6 6 4 2 3 2 54
4
5
15
9
8
19Với bộ test đầu tiên, bốn cấu hình có thể có là:
Với bộ test thứ hai, bốn cấu hình có thể có là:
USACO 2022 January Contest, Platinum — Counting Haybales: https://usaco.org/index.php?page=viewproblem2&cpid=1189
Tác giả: Daniel Zhang.
Những chú bò đang làm một bài thi trắc nghiệm. Nhưng thay vì một bài thi thông thường, nơi các lựa chọn của bạn được chấm riêng cho từng câu rồi cộng lại, trong bài thi này các lựa chọn được cộng lại trước khi chấm điểm.
Cụ thể, bạn được cho \(N\) (\(2\le N\le 10^5\)) nhóm vectơ nguyên trên mặt phẳng 2D, trong đó mỗi vectơ được biểu diễn bằng một cặp có thứ tự \((x,y)\). Hãy chọn một vectơ từ mỗi nhóm sao cho tổng các vectơ cách gốc tọa độ xa nhất có thể.
Đảm bảo tổng số vectơ không vượt quá \(2\cdot 10^5\). Mỗi nhóm có ít nhất \(2\) vectơ, và trong một nhóm, mọi vectơ đều khác nhau. Đồng thời, giá trị tuyệt đối của mọi tọa độ \(x\) và \(y\) không vượt quá \(\frac{10^9}{N}\).
Dòng đầu chứa \(N\), là số nhóm.
Mỗi nhóm bắt đầu bằng \(G\), là số vectơ trong nhóm, tiếp theo là \(G\) dòng chứa các vectơ của nhóm đó. Các nhóm liên tiếp được ngăn cách bởi dòng trống.
In bình phương khoảng cách Euclid lớn nhất có thể.
Ví dụ 1
3
2
-2 0
1 0
2
0 -2
0 1
3
-5 -5
5 1
10 10242Tối ưu là chọn \((1,0)\) từ nhóm đầu tiên, \((0,1)\) từ nhóm thứ hai và \((10,10)\) từ nhóm thứ ba. Tổng của các vectơ này là \((11,11)\), có bình phương khoảng cách đến gốc tọa độ là \(11^2+11^2=242\).
USACO 2022 January Contest, Platinum — Multiple Choice Test: https://usaco.org/index.php?page=viewproblem2&cpid=1190
Tác giả: Benjamin Qi.