USACO 2022 - Tháng 2 - Hạng Bạch Kim

Sau khi tác phẩm trước đây của Bessie được giới phê bình ca ngợi, cô được mời làm công việc thiết kế các bộ tranh. Cô thiết kế những bức tranh này bằng cách chọn \(1\le N\le 10^5\) hình chữ nhật có cạnh song song với các trục trên mặt phẳng, sao cho không có hai cạnh nào thẳng hàng. Biên của các hình chữ nhật này xác định biên của các miền màu trong bức tranh.

Vẫn là một nghệ sĩ tiên phong, Bessie quyết định rằng bức tranh nên giống một con bò Holstein. Cụ thể hơn, mỗi miền do các hình chữ nhật tạo thành được tô đen hoặc trắng, không có hai miền kề nhau nào cùng màu, và miền nằm ngoài tất cả các hình chữ nhật được tô trắng.

Sau khi chọn các hình chữ nhật, Bessie muốn bạn in một trong hai kết quả tùy theo tham số \(T\):

• Nếu \(T=1\), in tổng số miền.
• Nếu \(T=2\), in số miền trắng, sau đó là số miền đen.

Lưu ý: giới hạn thời gian của bài này là 4 giây, gấp đôi mức mặc định.

Dữ liệu vào

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

Mỗi dòng trong \(N\) dòng tiếp theo mô tả một hình chữ nhật dưới dạng \((x_1,y_1),(x_2,y_2)\), trong đó \(1\le x_1<x_2\le 2N\) và \(1\le y_1<y_2\le 2N\). \((x_1,y_1)\) và \((x_2,y_2)\) lần lượt là góc dưới bên trái và góc trên bên phải của hình chữ nhật.

Bảo đảm rằng tất cả các \(x_i\) tạo thành một hoán vị của \(1\ldots 2N\), và điều tương tự cũng đúng với tất cả các \(y_i\).

Dữ liệu ra

In một số nguyên nếu \(T=1\); nếu không, in hai số nguyên cách nhau bởi dấu cách.

Phân nhóm

1. Các test 3–4 thỏa mãn \(N\le 10^3\).
2. Trong các test 5–7, không có hai biên hình chữ nhật nào giao nhau.
3. Trong các test 8–10, \(T=1\) và biên của tất cả các hình chữ nhật liên thông với nhau.
4. Trong các test 11–13, \(T=2\) và biên của tất cả các hình chữ nhật liên thông với nhau.
5. Trong các test 14–18, \(T=1\).
6. Trong các test 19–23, \(T=2\).

Ví dụ

2 1
1 1 3 3
2 2 4 4

4

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

4 5

Nguồn

USACO 2022 February Contest, Platinum — Paint by Rectangles: https://usaco.org/index.php?page=viewproblem2&cpid=1212

Tác giả: Andi Qu.

Bò Bessie rất hào hứng vì gần đây đã được quay lại học trực tiếp! Đáng tiếc, giáo viên của cô, Farmer John, giảng bài rất nhàm chán nên cô thường xuyên ngủ gật trong lớp.

Farmer John nhận thấy Bessie không chú ý trong giờ học. Ông nhờ một học sinh khác trong lớp là Elsie ghi lại số lần Bessie ngủ gật trong mỗi buổi học. Có \(N\) buổi học (\(2\le N\le 10^5\)), và Elsie ghi nhận rằng Bessie ngủ gật \(a_i\) lần (\(1\le a_i\le 10^{18}\)) trong buổi học thứ \(i\). Tổng số lần Bessie ngủ gật trong tất cả các buổi học không vượt quá \(10^{18}\).

Vì rất thích cạnh tranh với Bessie, Elsie muốn khiến Farmer John nghĩ rằng Bessie luôn ngủ gật cùng một số lần trong mọi buổi học — qua đó làm cho vấn đề có vẻ hoàn toàn là lỗi của Bessie, không phụ thuộc vào những bài giảng đôi khi nhàm chán của Farmer John.

Elsie chỉ được phép sửa nhật ký bằng cách gộp hai buổi học kề nhau hoặc tách một buổi học thành hai. Ví dụ, nếu \(a=[1,2,3,4,5]\) và Elsie gộp buổi học thứ hai với buổi học thứ ba, nhật ký sẽ trở thành \([1,5,4,5]\). Nếu sau đó Elsie chọn tách buổi học thứ ba thành hai, nhật ký có thể trở thành một trong các dãy \([1,5,0,4,5]\), \([1,5,1,3,5]\), \([1,5,2,2,5]\), \([1,5,3,1,5]\) hoặc \([1,5,4,0,5]\).

Cho \(Q\) (\(1\le Q\le 10^5\)) ứng viên \(q_1,\ldots,q_Q\) cho con số Bessie ít yêu thích nhất (\(1\le q_i\le 10^{18}\)), với mỗi ứng viên hãy giúp Elsie tính số lần sửa nhật ký ít nhất cần thực hiện để tất cả các số trong nhật ký trở nên bằng nhau.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), dòng thứ hai chứa \(a_1,a_2,\ldots,a_N\). Dòng thứ ba chứa \(Q\), sau đó là \(Q\) dòng, mỗi dòng chứa một số nguyên \(q_i\), một ứng viên cho con số Bessie ít yêu thích nhất.

Dữ liệu ra

Với mỗi \(q_i\), hãy in số lần sửa ít nhất cần thiết để Elsie biến mọi phần tử trong nhật ký thành \(q_i\), hoặc \(-1\) nếu điều đó là không thể.

Phân nhóm

• Trong các test 2–4, \(N,Q\le 5000\).
• Trong các test 5–7, mọi \(a_i\) không vượt quá \(10^9\).
• Các test 8–26 không có ràng buộc bổ sung.

Ví dụ

6
1 2 3 1 1 4
7
1
2
3
4
5
6
12

6
6
4
5
-1
4
5

   1 2 3 1 1 4
-> 3 3 1 1 4
-> 3 3 1 5
-> 3 3 6
-> 3 3 3 3

Nguồn

USACO 2022 February Contest, Platinum — Sleeping in Class: https://usaco.org/index.php?page=viewproblem2&cpid=1213

Tác giả: Jesse Choe và Benjamin Qi.

Bessie có một chiếc điện thoại mới với chín nút được bố trí như sau:

123
456
789

Bessie đang vội nhập một số điện thoại cho trước, nên cô quyết định tiết kiệm thời gian bằng cách dùng một móng guốc nhấn nhiều nút cùng lúc. Cụ thể, móng guốc của Bessie có thể nhấn một chữ số; hai chữ số có chung một cạnh (tổng cộng có mười hai cặp như vậy); hoặc bốn chữ số tạo thành một hình vuông (1245, 2356, 4578 hoặc 5689).

Ví dụ, nếu số điện thoại Bessie muốn nhập là 123659874, cô có thể thử tiết kiệm thời gian bằng cách:

1. Nhấn đồng thời 1 và 2.
2. Nhấn 3.
3. Nhấn đồng thời 6, 5, 9 và 8.
4. Nhấn đồng thời 7 và 4.

Đáng tiếc, Bessie đã đánh giá quá cao khả năng thực hiện việc này của mình: nếu móng guốc của cô nhấn nhiều nút cùng lúc thì tất cả các chữ số đó sẽ được nhập theo một thứ tự tùy ý. Vì vậy, nếu Bessie thử chuỗi lần nhấn trên, cô có thể nhập thành 123596847 hoặc 213659874 (hay một trong rất nhiều khả năng khác).

Cho một dãy chữ số mà Bessie đã nhập, hãy đếm số lượng số điện thoại mà cô có thể đã định nhập, lấy modulo \(10^9+7\).

Lưu ý: giới hạn thời gian của bài này là 4 giây, gấp đôi mức mặc định.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\le T\le 10\)), số bộ test độc lập cần giải.

\(T\) dòng tiếp theo, mỗi dòng chứa một chuỗi không rỗng gồm các chữ số từ 1 đến 9. Bảo đảm tổng độ dài của các chuỗi không vượt quá \(10^5\).

Dữ liệu ra

Với mỗi bộ test, in số lượng số điện thoại Bessie có thể đã định nhập, lấy modulo \(10^9+7\).

Phân nhóm

• Trong các tệp test 2–3, mọi số điện thoại có độ dài không quá \(8\).
• Trong các tệp test 4–5, số điện thoại chỉ chứa 1, 2 và 3.
• Trong các tệp test 6–7, số điện thoại không chứa chữ số 5.
• Trong các tệp test 8–9, số điện thoại chỉ chứa 5, 6, 8 và 9.
• Trong các tệp test 10–12, tổng độ dài các chuỗi không vượt quá \(10^2\).
• Trong các tệp test 13–15, tổng độ dài các chuỗi không vượt quá \(10^3\).
• Trong các tệp test 16–18, tổng độ dài các chuỗi không vượt quá \(10^4\).
• Trong các tệp test 19–21, không có ràng buộc bổ sung.

Ví dụ

5
1478
4455
5968
31313211
123659874

5
2
24
3
255

1478
1487
4178
4187
1748

Nguồn

USACO 2022 February Contest, Platinum — Phone Numbers: https://usaco.org/index.php?page=viewproblem2&cpid=1214

Tác giả: Nick Wu.