| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2019 - Cow Dating | 100 (p) | 4.0s | 512M |
| 2 | USACO 2019 - Moorio Kart | 100 (p) | 4.0s | 512M |
| 3 | USACO 2019 - Mowing Mischief | 100 (p) | 4.0s | 512M |
Không ấn tượng với những trang web hẹn hò tẻ nhạt hiện dành cho bò (chẳng hạn eHarmoony, Moosk, Plenty of Cows), Farmer John quyết định ra mắt một trang hẹn hò mới dành cho bò, sử dụng một thuật toán ghép đôi độc quyền tinh vi để ghép bò cái và bò đực dựa trên rất nhiều sở thích chung của chúng.
Trong lúc tìm bạn nhảy cho Vũ hội Chuồng bò ngày Valentine, Bessie quyết định dùng thử trang web này. Sau khi cô tạo tài khoản, thuật toán của FJ cung cấp một danh sách gồm \(N\) đối tượng có thể ghép đôi (\(1\leq N \leq 10^6\)). Xem qua danh sách, Bessie kết luận rằng mỗi con bò đực có xác suất \(p_i\) (\(0<p_i<1\)) chấp nhận lời mời dự vũ hội của cô.
Bessie quyết định gửi lời mời cho mỗi con bò đực thuộc một đoạn liên tiếp trong danh sách. Vốn luôn đoan chính, cô muốn có đúng một bạn nhảy. Hãy giúp Bessie tìm xác suất lớn nhất để nhận được đúng một lời chấp nhận, nếu cô chọn đoạn thích hợp.
Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 10^6\)). Mỗi dòng trong \(N\) dòng còn lại chứa \(10^6\) lần \(p_i\); giá trị này là một số nguyên.
Trong ít nhất 25% số test, dữ liệu còn bảo đảm \(N \leq 4000\).
In ra \(10^6\) lần xác suất lớn nhất để nhận được đúng một lời chấp nhận, làm tròn xuống số nguyên gần nhất.
Ví dụ 1
3
300000
400000
350000470000Xác suất lớn nhất đạt được khi chọn đoạn từ con bò thứ 2 đến con bò thứ 3.
Lưu ý rằng bạn nên cẩn thận đôi chút với độ chính xác số thực khi giải bài này. Ban tổ chức khuyên dùng ít nhất kiểu double (số thực dấu phẩy động 64 bit), không nên dùng kiểu float (số thực dấu phẩy động 32 bit).
USACO 2019 February Contest, Platinum — Cow Dating
Tác giả: Ethan Guo.
Bessie và Farmer John thích đua xe dê kéo. Ý tưởng rất giống với đua Go-Kart mà những người khác yêu thích, chỉ khác là xe được dê kéo và đường đua được tạo từ vùng đất nông nghiệp gần đó. Vùng đất này gồm \(N\) đồng cỏ và \(M\) con đường, mỗi con đường nối một cặp đồng cỏ.
Bessie muốn tạo một đường đua từ các trang trại gần đó. Một trang trại là một tập con gồm ít nhất hai đồng cỏ, trong đó từ mỗi đồng cỏ đều có thể đến mọi đồng cỏ khác theo một dãy đường duy nhất.
Vùng đất nông nghiệp gần đó có thể chứa nhiều trang trại. Giả sử có \(K\) trang trại. Bessie muốn tạo một vòng đua xe dê kéo bằng cách kết nối cả \(K\) trang trại, bổ sung \(K\) con đường có độ dài \(X\). Mỗi trang trại phải được ghé thăm đúng một lần và phải đi qua ít nhất một con đường bên trong mỗi trang trại.
Để đường đua thú vị đối với các tay đua, tổng chiều dài đường đua phải ít nhất là \(Y\). Bessie muốn biết tổng chiều dài của tất cả các đường đua thú vị như vậy. Hai đường đua được xem là khác nhau nếu tồn tại hai đồng cỏ kề nhau (sau khi bổ sung các con đường giữa những trang trại) trong một đường đua nhưng không kề nhau trong đường đua kia. Lưu ý rằng chỉ những con đường được chọn mới quan trọng, không quan trọng hướng mà xe dê kéo sẽ di chuyển trên các con đường đó.
Dòng đầu tiên chứa \(N\), \(M\), \(X\) và \(Y\), trong đó \(1 \leq N \leq 1500\), \(1 \leq M \leq N-1\) và \(0 \leq X, Y \leq 2500\).
Mỗi dòng trong \(M\) dòng tiếp theo mô tả một con đường. Các dòng có dạng \(A_i\) \(B_i\) \(D_i\), nghĩa là đồng cỏ \(A_i\) và đồng cỏ \(B_i\) được nối bởi một con đường có độ dài nguyên \(D_i\) (\(1 \leq A_i, B_i \leq N\), \(0 \leq D_i \leq 2500\)). Mỗi đồng cỏ là đầu mút của ít nhất một con đường, và hệ thống đường không có chu trình.
Trong ít nhất 70% số test, dữ liệu còn bảo đảm \(N \leq 1000\) và \(Y \leq 1000\).
In ra một số nguyên duy nhất là tổng chiều dài của tất cả các đường đua thú vị. Vì tổng chiều dài có thể rất lớn, hãy in tổng này theo modulo \(10^9+7\).
Ví dụ 1
5 3 1 12
1 2 3
2 3 4
4 5 654Ví dụ này có 6 đường đua có thể tạo:
Đáp án là \(12+12+15+15=54\), vì chỉ cộng các đường đua có độ dài ít nhất là \(12\).
Lưu ý rằng đối với bài này, giới hạn thời gian tiêu chuẩn được tăng lên 3 giây cho mỗi test (6 giây cho mỗi test đối với Java và Python).
USACO 2019 February Contest, Platinum — Moorio Kart
Tác giả: Matt Fontaine.
Hai cô em họ của Bessie là Ella và Bella đang đến thăm trang trại. Đáng tiếc, kể từ khi tới đây, chúng chẳng làm gì ngoài việc nghịch ngợm.
Trong trò quậy phá mới nhất, chúng quyết định cắt càng nhiều cỏ càng tốt. Vùng đồng cỏ tốt nhất của trang trại có dạng một hình vuông lớn kích thước \(T \times T\). Góc dưới bên trái là \((0,0)\) và góc trên bên phải là \((T,T)\). Do đó, hình vuông chứa \((T+1)^2\) điểm nguyên (các điểm có tọa độ nguyên).
Ella và Bella dự định cùng bắt đầu tại \((0,0)\) rồi chạy với tốc độ đơn vị đến \((T,T)\), mỗi cô giữ một đầu của một sợi dây rất sắc và có khả năng co giãn rất lớn. Cỏ trong bất kỳ vùng nào mà sợi dây quét qua đều sẽ bị cắt. Ella và Bella có thể đi theo những đường khác nhau, nhưng mỗi đường chỉ gồm các bước đi lên trên và sang phải, từ một điểm nguyên đến một điểm nguyên khác.
Bessie khá lo rằng quá nhiều cỏ sẽ bị cắt, nên cô nghĩ ra một kế hoạch khéo léo để ràng buộc các đường đi của Ella và Bella. Có \(N\) bông hoa ngon lành (\(1 \leq N \leq 2 \cdot 10^5\)) nằm rải rác trên đồng cỏ, mỗi bông ở một điểm nguyên khác nhau. Bessie sẽ chọn một tập \(S\) gồm các bông hoa mà cả Ella và Bella bắt buộc phải ghé thăm (tức là đường đi của Ella phải đi qua tất cả các bông hoa trong \(S\), và đường đi của Bella cũng vậy). Để thêm nhiều điểm trung gian nhất có thể vào các đường đi này, Bessie sẽ chọn \(S\) có kích thước lớn nhất trong số các tập con của các bông hoa mà một con bò di chuyển lên trên và sang phải từ \((0,0)\) đến \((T,T)\) có thể ghé thăm.
Ella và Bella sẽ cố gắng tối đa hóa lượng cỏ chúng cắt, với ràng buộc phải ghé thăm các bông hoa trong \(S\). Hãy giúp Bessie chọn \(S\) sao cho lượng cỏ bị cắt nhỏ nhất có thể.
Dòng đầu tiên chứa \(N\) và \(T\) (\(1 \leq T \leq 10^6\)). Mỗi dòng trong \(N\) dòng tiếp theo chứa tọa độ nguyên \((x_i, y_i)\) của một bông hoa. Dữ liệu bảo đảm \(1 \leq x_i, y_i \leq T-1\) với mọi \(i\), và không có hai bông hoa nào nằm trên cùng một đường ngang hoặc đường dọc.
Trong ít nhất 20% số test, dữ liệu còn bảo đảm \(N \leq 3200\).
In ra một số nguyên duy nhất là lượng cỏ bị cắt nhỏ nhất có thể.
Ví dụ 1
5 20
19 1
2 6
9 15
10 3
13 11117Trong ví dụ trên, lựa chọn tối ưu của Bessie là các bông hoa tại \((10,3)\) và \((13,11)\). Khi đó, trong trường hợp xấu nhất, Ella và Bella sẽ cắt ba hình chữ nhật cỏ có tổng diện tích là \(117\).
USACO 2019 February Contest, Platinum — Mowing Mischief
Tác giả: Dhruv Rohatgi.