USACO 2024 - Tháng 12 - Hạng Bạc

Bessie và Elsie phát hiện một hàng gồm \(N\) chiếc bánh (\(2\leq N\leq 5\cdot 10^5\), \(N\) chẵn), có kích thước lần lượt là \(a_1,a_2,\dots,a_N\) theo thứ tự đó (\(1\leq a_i\leq 10^9\)).

Mỗi cô bò đều muốn ăn nhiều nhất có thể. Tuy nhiên, vì là những cô bò rất văn minh, họ quyết định chơi một trò chơi để chia bánh! Hai cô bò luân phiên lượt chơi. Mỗi lượt là một trong hai hành động sau:

1. Bessie chọn hai chiếc bánh kề nhau và xếp chồng chúng, tạo thành một chiếc bánh mới có kích thước bằng tổng kích thước của chúng.
2. Elsie chọn chiếc bánh ngoài cùng bên trái hoặc ngoài cùng bên phải và cất vào phần dự trữ của mình.

Khi chỉ còn một chiếc bánh, Bessie ăn chiếc bánh đó, còn Elsie ăn tất cả bánh trong phần dự trữ. Nếu cả hai chơi tối ưu để tối đa hóa lượng bánh mình ăn và Bessie đi trước, mỗi cô bò sẽ ăn bao nhiêu bánh?

Dữ liệu vào

Mỗi đầu vào gồm \(T\) (\(1\leq T\leq 10\)) bộ test độc lập. Đảm bảo tổng tất cả các giá trị \(N\) trong một đầu vào không vượt quá \(10^6\).

Mỗi bộ test có định dạng như sau. Dòng đầu chứa \(N\). Dòng tiếp theo chứa \(N\) số nguyên cách nhau bởi dấu cách, \(a_1,a_2,\ldots,a_N\).

Dữ liệu ra

Với mỗi bộ test, in một dòng chứa \(b\) và \(e\), lần lượt là lượng bánh Bessie và Elsie sẽ ăn nếu cả hai chơi tối ưu.

Phân nhóm

• Test 2: Tất cả \(a_i\) bằng nhau.
• Test 3: \(N\leq 10\).
• Các test 4–7: \(N\leq 5000\).
• Các test 8–11: Không có ràng buộc bổ sung.

Ví dụ

2
4
40 30 20 10
4
10 20 30 40

60 40
60 40

Nguồn

Đề bài gốc: USACO 2024 December Contest, Silver — Cake Game

Tác giả: Linda Zhao, Agastya Goel, Gavin Ye.

Farmer John đang mở rộng trang trại! Ông đã tìm ra địa điểm hoàn hảo trong Rừng Đỏ-Đen, gồm \(N\) cây (\(1\leq N\leq 10^5\)) trên một trục số, cây thứ \(i\) nằm tại vị trí \(x_i\) (\(-10^9\leq x_i\leq 10^9\)).

Luật bảo vệ môi trường hạn chế những cây Farmer John có thể chặt để lấy chỗ cho trang trại. Có \(K\) ràng buộc (\(1\leq K\leq 10^5\)), mỗi ràng buộc quy định rằng luôn phải có ít nhất \(t_i\) cây (\(1\leq t_i\leq N\)) trong đoạn \([l_i,r_i]\), tính cả hai đầu mút (\(-10^9\leq l_i\leq r_i\leq 10^9\)). Đảm bảo ban đầu Rừng Đỏ-Đen thỏa mãn các ràng buộc này.

Farmer John muốn trang trại của mình lớn nhất có thể. Hãy giúp ông tính số cây tối đa có thể chặt mà vẫn thỏa mãn mọi ràng buộc!

Dữ liệu vào

Mỗi đầu vào gồm \(T\) (\(1\leq T\leq 10\)) bộ test độc lập. Đảm bảo tổng tất cả các giá trị \(N\) và tổng tất cả các giá trị \(K\) trong một đầu vào đều không vượt quá \(3\cdot 10^5\).

Dòng đầu chứa \(T\). Sau đó, mỗi bộ test có định dạng:

• Dòng đầu chứa hai số nguyên \(N\) và \(K\).
• Dòng tiếp theo chứa \(N\) số nguyên \(x_1,\dots,x_N\).
• Mỗi dòng trong \(K\) dòng tiếp theo chứa ba số nguyên cách nhau bởi dấu cách: \(l_i\), \(r_i\) và \(t_i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng chứa một số nguyên là số cây tối đa Farmer John có thể chặt.

Phân nhóm

• Test 2: \(N,K\leq 16\).
• Các test 3–5: \(N,K\leq 1000\).
• Các test 6–7: \(t_i=1\) với mọi \(i=1,\dots,K\).
• Các test 8–11: Không có ràng buộc bổ sung.

Ví dụ

3
7 1
8 4 10 1 2 6 7
2 9 3
7 2
8 4 10 1 2 6 7
2 9 3
1 10 1
7 2
8 4 10 1 2 6 7
2 9 3
1 10 4

4
4
3

Nguồn

Đề bài gốc: USACO 2024 December Contest, Silver — Deforestation

Tác giả: Tina Wang, Jiahe Lu, Benjamin Qi.

Nhà máy sữa của Farmer John có thể được mô tả bằng một lưới ô vuông \(N\times N\) (\(1\leq N\leq 1000\)) chứa các băng chuyền. Vị trí \((a,b)\) chỉ ô ở hàng thứ \(a\) tính từ trên xuống và cột thứ \(b\) tính từ trái sang. Có \(5\) loại ô:

1. L — băng chuyền hướng sang trái, di chuyển mọi vật trên nó sang trái \(1\) ô sau mỗi đơn vị thời gian.
2. R — băng chuyền hướng sang phải, di chuyển mọi vật trên nó sang phải \(1\) ô sau mỗi đơn vị thời gian.
3. U — băng chuyền hướng lên trên, di chuyển mọi vật trên nó lên trên \(1\) ô sau mỗi đơn vị thời gian.
4. D — băng chuyền hướng xuống dưới, di chuyển mọi vật trên nó xuống dưới \(1\) ô sau mỗi đơn vị thời gian.
5. ? — Farmer John chưa xây băng chuyền tại ô đó.

Lưu ý rằng băng chuyền cũng có thể đưa vật ra ngoài lưới. Một ô \(c\) là không sử dụng được nếu một vật được đặt tại ô \(c\) sẽ không bao giờ thoát khỏi lưới băng chuyền (tức là nó sẽ di chuyển mãi trong lưới).

Ban đầu Farmer John chưa bắt đầu xây nhà máy nên mọi ô đều là ?. Trong \(Q\) ngày tiếp theo (\(1\leq Q\leq 2\cdot 10^5\)), từ ngày \(1\) đến ngày \(Q\), Farmer John sẽ chọn một ô chưa có băng chuyền và xây một băng chuyền tại đó.

Cụ thể, trong ngày thứ \(i\), Farmer John xây một băng chuyền loại \(t_i\) (\(t_i\in\{\text{L,R,U,D}\}\)) tại vị trí \((r_i,c_i)\) (\(1\leq r_i,c_i\leq N\)). Đảm bảo vị trí \((r_i,c_i)\) chưa có băng chuyền.

Sau mỗi ngày, hãy giúp Farmer John tìm số ô không sử dụng được nhỏ nhất có thể đạt được bằng cách xây băng chuyền một cách tối ưu trên tất cả các ô còn lại chưa có băng chuyền.

Dữ liệu vào

Dòng đầu chứa \(N\) và \(Q\).

Dòng thứ \(i\) trong \(Q\) dòng tiếp theo chứa lần lượt \(r_i\), \(c_i\) và \(t_i\).

Dữ liệu ra

In ra \(Q\) dòng, dòng thứ \(i\) mô tả số ô không sử dụng được nhỏ nhất nếu Farmer John xây băng chuyền tối ưu trên tất cả các ô còn lại hiện chưa có băng chuyền.

Phân nhóm

• Các test 4–5: \(N\leq 10\).
• Các test 6–7: \(N\leq 40\).
• Các test 8–13: Không có ràng buộc bổ sung.

Ví dụ

3 5
1 1 R
3 3 L
3 2 D
1 2 L
2 1 U

0
0
0
2
3

RL?
U??
?DL

RLR
URR
LDL

3 8
1 1 R
1 2 L
1 3 D
2 3 U
3 3 L
3 2 R
3 1 U
2 1 D

0
2
2
4
4
6
6
9

RLD
D?U
URL

4 13
2 2 R
2 3 R
2 4 D
3 4 D
4 4 L
4 3 L
4 2 U
3 1 D
4 1 R
2 1 L
1 1 D
1 4 L
1 3 D

0
0
0
0
0
0
0
0
11
11
11
11
13

Nguồn

Đề bài gốc: USACO 2024 December Contest, Silver — 2D Conveyor Belt

Tác giả: Alex Liang.