USACO 2022 - Tháng 1 - Hạng Vàng

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 USACO 2022 - Drought 100 (p) 4.0s 512M
2 USACO 2022 - Farm Updates 100 (p) 4.0s 512M
3 USACO 2022 - Tests for Haybales 100 (p) 4.0s 512M

1. USACO 2022 - Drought

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Do hạn hán, cỏ trên đồng của Nông dân John đã khô héo. Sau nhiều giờ tuyệt vọng và suy ngẫm, FJ nảy ra ý tưởng tuyệt vời là mua ngô để cho những chú bò quý giá của mình ăn.

\(N\) chú bò của FJ (\(1\le N\le 100\)) xếp thành một hàng, trong đó chú bò thứ \(i\) có mức đói là số nguyên không âm \(h_i\). Vì bò của FJ là động vật có tính xã hội và nhất quyết ăn cùng nhau, cách duy nhất để FJ giảm mức đói của đàn bò là chọn hai chú bò kề nhau \(i\) và \(i+1\), rồi cho mỗi con một túi ngô, khiến mức đói của mỗi con giảm đi một.

FJ muốn cho bò ăn đến khi tất cả có cùng một mức đói không âm. Mặc dù không biết chính xác mức đói của đàn bò, ông biết một cận trên cho mức đói của mỗi con; cụ thể, mức đói \(h_i\) của chú bò thứ \(i\) không vượt quá \(H_i\) (\(0\le H_i\le 1000\)).

Nhiệm vụ của bạn là đếm số bộ \(N\) mức đói \([h_1,h_2,\ldots,h_N]\) phù hợp với các cận trên này mà FJ có thể đạt được mục tiêu, lấy modulo \(10^9+7\).

Dữ liệu vào

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

Dòng thứ hai chứa \(H_1,H_2,\ldots,H_N\).

Dữ liệu ra

In số bộ \(N\) mức đói, lấy modulo \(10^9+7\).

Phân nhóm

\(N\) chẵn trong các test mang số chẵn và lẻ trong các test mang số lẻ.

  • Các test 3 và 4 thỏa mãn \(N\le 6\) và \(H_i\le 10\).
  • Các test 5 đến 10 thỏa mãn \(N\le 50\) và \(H_i\le 100\).
  • Các test 11 đến 20 không có thêm ràng buộc.

Ví dụ

Ví dụ 1

Input 
3
9 11 7
Output 
241
Giải thích

Có \((9+1)\cdot(11+1)\cdot(7+1)\) bộ \(3\) mức đói \(h\) phù hợp với \(H\).

Một trong các bộ đó là \(h=[8,10,5]\). Trong trường hợp này, có thể làm cho mọi chú bò có mức đói bằng nhau: cho cả bò \(2\) và bò \(3\) hai túi ngô, sau đó cho cả bò \(1\) và bò \(2\) năm túi ngô, khiến mỗi con có mức đói \(3\).

Một bộ khác là \(h=[0,1,0]\). Trong trường hợp này, không thể làm cho mức đói của đàn bò bằng nhau.

Ví dụ 2

Input 
4
6 8 5 9
Output 
137

Nguồn

USACO 2022 January Contest, Gold — Drought: https://usaco.org/index.php?page=viewproblem2&cpid=1185

Tác giả: Arpan Banerjee và Benjamin Qi.

2. USACO 2022 - Farm Updates

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Nông dân John quản lý một tập hợp \(N\) trang trại (\(1\le N\le 10^5\)), được đánh số thuận tiện từ \(1\ldots N\). Ban đầu, không có con đường nào nối các trang trại với nhau, và mỗi trang trại đều đang tích cực sản xuất sữa.

Do nền kinh tế luôn biến động, Nông dân John cần thay đổi các trang trại của mình theo một chuỗi \(Q\) thao tác cập nhật (\(0\le Q\le 2\cdot 10^5\)). Các thao tác cập nhật có thể thuộc một trong ba dạng:

  • (D x) Ngừng hoạt động một trang trại \(x\) đang hoạt động, khiến nó không còn sản xuất sữa.
  • (A x y) Thêm một con đường giữa hai trang trại đang hoạt động \(x\) và \(y\).
  • (R e) Xóa con đường thứ \(e\) đã được thêm trước đó (\(e=1\) là con đường đầu tiên được thêm).

Một trang trại \(x\) đang tích cực sản xuất sữa, hoặc có thể đi đến một trang trại đang hoạt động khác qua một chuỗi các con đường, được gọi là trang trại “có liên quan”. Với mỗi trang trại \(x\), hãy tính giá trị \(i\) lớn nhất (\(0\le i\le Q\)) sao cho \(x\) có liên quan sau lần cập nhật thứ \(i\).

Dữ liệu vào

Dòng đầu chứa \(N\) và \(Q\). Mỗi dòng trong \(Q\) dòng tiếp theo chứa một cập nhật thuộc một trong các dạng sau:

D x
A x y
R e

Đảm bảo rằng với các cập nhật loại R, \(e\) không vượt quá số con đường đã được thêm cho đến thời điểm đó, và không có hai cập nhật loại R nào có cùng giá trị \(e\).

Dữ liệu ra

In \(N\) dòng, mỗi dòng chứa một số nguyên trong khoảng \(0\ldots Q\).

Phân nhóm

  • Các test 2 đến 5 thỏa mãn \(N\le 10^3\), \(Q\le 2\cdot 10^3\).
  • Các test 6 đến 20 không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
5 9
A 1 2
A 2 3
D 1
D 3
A 2 4
D 2
R 2
R 1
R 3
Output 
7
8
6
9
9
Giải thích

Trong ví dụ này, các con đường được xóa theo thứ tự \((2,3)\), \((1,2)\), \((2,4)\).

  • Trang trại \(1\) có liên quan ngay trước khi \((1,2)\) bị xóa.
  • Trang trại \(2\) có liên quan ngay trước khi \((2,4)\) bị xóa.
  • Trang trại \(3\) có liên quan ngay trước khi \((2,3)\) bị xóa.
  • Trang trại \(4\) và \(5\) vẫn hoạt động sau tất cả các truy vấn. Vì vậy, cả hai vẫn có liên quan và kết quả cho cả hai phải là \(Q\).

Nguồn

USACO 2022 January Contest, Gold — Farm Updates: https://usaco.org/index.php?page=viewproblem2&cpid=1186

Tác giả: Benjamin Qi.

3. USACO 2022 - Tests for Haybales

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Những chú bò của Nông dân John đã quyết định tổ chức một cuộc thi lập trình cho những chú bò ở trang trại của Nông dân Nhoj. Để các bài toán vui nhất có thể, chúng đã dành rất nhiều thời gian nghĩ ra những bộ dữ liệu vào đầy thử thách. Riêng với một bài toán tên “Haybales”, những chú bò cần bạn giúp thiết kế các dữ liệu vào khó. Việc này đòi hỏi giải bài toán khá thú vị sau:

Có một mảng số nguyên đã sắp xếp \(x_1\le x_2\le\dotsb\le x_N\) (\(1\le N\le 10^5\)), và một số nguyên \(K\). Bạn không biết mảng hay \(K\), nhưng với mỗi chỉ số \(i\), bạn biết chỉ số lớn nhất \(j_i\) sao cho \(x_{j_i}\le x_i+K\). Đảm bảo rằng \(i\le j_i\) và \(j_1\le j_2\le\cdots\le j_N\le N\).

Từ thông tin này, những chú bò của Nông dân John cần dựng một mảng bất kỳ cùng với một số nguyên \(K\) khớp với thông tin đã cho. Kết quả dựng phải thỏa mãn \(0\le x_i\le 10^{18}\) với mọi \(i\) và \(1\le K\le 10^{18}\).

Có thể chứng minh rằng điều này luôn khả thi. Hãy giúp những chú bò của Nông dân John giải bài toán!

Dữ liệu vào

Dòng đầu chứa \(N\). Dòng tiếp theo chứa \(j_1,j_2,\ldots,j_N\).

Dữ liệu ra

In \(K\), sau đó in \(x_1,\ldots,x_N\) trên các dòng riêng biệt. Mọi kết quả hợp lệ đều được chấp nhận.

Phân nhóm

  • Với 50% số dữ liệu vào, \(N\le 5000\).
  • Với số dữ liệu vào còn lại, không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
6
2 2 4 5 6 6
Output 
6
1
6
17
22
27
32
Giải thích

Kết quả mẫu là mảng \(a=[1,6,17,22,27,32]\) với \(K=6\). \(j_1=2\) được thỏa mãn vì \(a_2=6\le 1+6=a_1+K\) nhưng \(a_3=17>1+6=a_1+K\), nên \(a_2\) là phần tử lớn nhất không vượt quá \(a_1+K\). Tương tự:

  • \(j_2=2\) được thỏa mãn vì \(a_2=6\le 6+6\) nhưng \(a_3=17>6+6\).
  • \(j_3=4\) được thỏa mãn vì \(a_4=22\le 17+6\) nhưng \(a_5=27>17+6\).
  • \(j_4=5\) được thỏa mãn vì \(a_5=27\le 22+6\) nhưng \(a_6=32>22+6\).
  • \(j_5=6\) được thỏa mãn vì \(a_6=32\le 27+6\) và \(a_6\) là phần tử cuối cùng của mảng.
  • \(j_6=6\) được thỏa mãn vì \(a_6=32\le 32+6\) và \(a_6\) là phần tử cuối cùng của mảng.

Đây không phải kết quả đúng duy nhất cho dữ liệu vào mẫu. Chẳng hạn, bạn có thể in mảng \([1,2,4,5,6,7]\) với \(K=1\).

Nguồn

USACO 2022 January Contest, Gold — Tests for Haybales: https://usaco.org/index.php?page=viewproblem2&cpid=1187

Tác giả: Danny Mittal.