USACO 2024 - Tháng 12 - Hạng Đồng

Bessie đã quay lại trường học! Cô bắt đầu làm bài tập toán, trong đó cô được yêu cầu làm tròn các số nguyên dương đến các lũy thừa của \(10\).

Để làm tròn một số nguyên dương \(a\) đến \(10^b\) gần nhất, với \(b\) là một số nguyên dương, trước tiên Bessie tìm chữ số thứ \(b\) tính từ bên phải. Gọi chữ số này là \(x\).

Nếu \(x \geq 5\), Bessie cộng \(10^b\) vào \(a\).

Sau đó, Bessie đặt tất cả các chữ số từ chữ số thứ \(b\) tính từ bên phải trở về bên phải, kể cả chữ số đó, thành \(0\).

Ví dụ, nếu Bessie muốn làm tròn \(456\) đến \(10^2\) (hàng trăm) gần nhất, trước tiên cô tìm chữ số thứ \(2\) tính từ bên phải là \(5\). Do đó \(x=5\). Vì \(x\geq 5\), Bessie cộng \(100\) vào \(a\). Cuối cùng, cô đặt chữ số thứ \(2\) tính từ bên phải và tất cả các chữ số bên phải nó trong \(a\) thành \(0\), thu được \(500\).

Tuy nhiên, nếu Bessie làm tròn \(446\) đến \(10^2\) gần nhất, kết quả sẽ là \(400\).

Sau khi xem bài tập của Bessie, Elsie cho rằng mình đã phát minh ra một kiểu làm tròn mới: làm tròn dây chuyền. Để làm tròn dây chuyền đến \(10^b\) gần nhất, trước tiên Elsie làm tròn đến \(10^1\) gần nhất, sau đó đến \(10^2\) gần nhất, và tiếp tục như vậy cho đến \(10^b\) gần nhất.

Bessie nghĩ Elsie đã sai, nhưng quá bận làm bài tập toán để xác nhận nghi ngờ của mình. Cô giao cho bạn đếm số lượng số nguyên \(x\) từ \(2\) đến \(N\) (\(1\leq N\leq 10^9\)) sao cho làm tròn \(x\) đến \(10^P\) gần nhất khác với làm tròn dây chuyền đến \(10^P\) gần nhất, trong đó \(P\) là số nguyên nhỏ nhất thỏa mãn \(10^P\geq x\).

Dữ liệu vào

Bạn phải trả lời nhiều bộ test.

Dòng đầu chứa một số nguyên \(T\) (\(1\leq T\leq 10^5\)), là số bộ test. Tiếp theo là \(T\) bộ test.

Dòng duy nhất của mỗi bộ test chứa một số nguyên \(N\). Tất cả các giá trị \(N\) trong cùng một tệp đầu vào được đảm bảo đôi một khác nhau.

Dữ liệu ra

In ra \(T\) dòng, dòng thứ \(i\) chứa đáp án cho bộ test thứ \(i\). Mỗi dòng là một số nguyên biểu thị số lượng số nguyên từ \(2\) đến \(N\) cho kết quả khác nhau khi dùng hai phương pháp làm tròn.

Phân nhóm

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

Ví dụ

4
1
100
4567
3366

0
5
183
60

Nguồn

Đề bài gốc: USACO 2024 December Contest, Bronze — Roundabout Rounding

Tác giả: Weiming Zhou.

Farmer John có một khối phô mai hình lập phương. Khối phô mai nằm trong không gian tọa độ ba chiều, trải từ \((0,0,0)\) đến \((N,N,N)\) (\(2\leq N\leq 1000\)). Farmer John sẽ thực hiện một chuỗi \(Q\) (\(1\leq Q\leq 2\cdot 10^5\)) thao tác cập nhật trên khối phô mai.

Trong mỗi thao tác cập nhật, FJ sẽ khoét bỏ khối phô mai kích thước \(1\times 1\times 1\) trải từ tọa độ nguyên \((x,y,z)\) đến \((x+1,y+1,z+1)\), trong đó \(0\leq x,y,z<N\). Đảm bảo tại vị trí FJ khoét luôn tồn tại một khối phô mai \(1\times 1\times 1\). Vì FJ đang chơi Moocraft, trọng lực không khiến các phần phô mai rơi xuống khi phần phô mai bên dưới bị khoét bỏ.

Sau mỗi lần cập nhật, hãy in số cấu hình khác nhau mà FJ có thể đặt một viên gạch kích thước \(1\times 1\times N\) vào khối phô mai sao cho không phần nào của viên gạch chồng lên phần phô mai còn lại. Mọi đỉnh của viên gạch phải có tọa độ nguyên thuộc đoạn \([0,N]\) trên cả ba trục. FJ có thể xoay viên gạch theo bất kỳ cách nào.

Dữ liệu vào

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

\(Q\) dòng tiếp theo chứa \(x\), \(y\) và \(z\), là tọa độ cần khoét.

Dữ liệu ra

Sau mỗi thao tác cập nhật, in ra một số nguyên là số cấu hình.

Phân nhóm

• Các test 2–4: \(N\leq 10\) và \(Q\leq 1000\).
• Các test 5–7: \(N\leq 100\) và \(Q\leq 1000\).
• Các test 8–16: Không có ràng buộc bổ sung.

Ví dụ

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

0
0
1
2
5

Nguồn

Đề bài gốc: USACO 2024 December Contest, Bronze — Farmer John's Cheese Block

Tác giả: Chongtian Ma, Alex Liang.

Farmer John đang cố mô tả cuộc thi USACO yêu thích của mình cho Elsie, nhưng cô không hiểu tại sao ông lại thích nó đến vậy. Ông nói: “Phần yêu thích của tôi trong cuộc thi là khi Bessie nói ‘It's Mooin' Time’ rồi rống moo khắp cuộc thi.”

Elsie vẫn không hiểu, nên Farmer John tải cuộc thi xuống dưới dạng tệp văn bản và cố giải thích ý mình. Cuộc thi được biểu diễn bằng một xâu chữ cái thường có độ dài \(N\) (\(3\leq N\leq 20\,000\)). Một tiếng moo nói chung được định nghĩa là xâu con \(c_ic_jc_j\), trong đó một ký tự \(c_i\) đứng ngay trước hai lần xuất hiện của một ký tự \(c_j\), với \(c_i\neq c_j\). Theo Farmer John, Bessie rống moo rất nhiều, nên nếu một tiếng moo nào đó xuất hiện ít nhất \(F\) (\(1\leq F\leq N\)) lần trong cuộc thi thì nó có thể là do Bessie tạo ra.

Tuy nhiên, bản tải xuống của Farmer John có thể đã bị hỏng và tệp văn bản có thể có nhiều nhất một ký tự khác với tệp gốc. Hãy in ra tất cả những tiếng moo mà Bessie có thể đã tạo ra khi tính đến lỗi tiềm ẩn này, theo thứ tự bảng chữ cái.

Dữ liệu vào

Dòng đầu chứa \(N\) và \(F\), lần lượt là độ dài xâu và ngưỡng tần suất để một tiếng moo được coi là do Bessie tạo ra.

Dòng thứ hai chứa một xâu chữ cái thường có độ dài \(N\), biểu diễn cuộc thi.

Dữ liệu ra

In ra số lượng tiếng moo có thể do Bessie tạo ra, tiếp theo là danh sách các tiếng moo theo thứ tự từ điển. Mỗi tiếng moo nằm trên một dòng riêng.

Phân nhóm

• Các test 4–8: \(N\leq 100\).
• Các test 9–13: Không có ràng buộc bổ sung.

Ví dụ

10 2
zzmoozzmoo

1
moo

17 2
momoobaaaaaqqqcqq

3
aqq
baa
cqq

3 1
ooo

25
aoo
boo
coo
doo
eoo
foo
goo
hoo
ioo
joo
koo
loo
moo
noo
poo
qoo
roo
soo
too
uoo
voo
woo
xoo
yoo
zoo

Nguồn

Đề bài gốc: USACO 2024 December Contest, Bronze — It's Mooin' Time

Tác giả: Suhas Nagar.