USACO 2014 - Tháng 2 - Hạng Vàng

Mỗi buổi sáng, FJ thức dậy và đi qua trang trại từ nhà đến chuồng. Trang trại gồm \(N\) cánh đồng (\(1 \le N \le 250\)) được nối với nhau bởi \(M\) con đường hai chiều (\(1 \le M \le 25\,000\)), mỗi con đường có một độ dài tương ứng. Nhà của FJ nằm ở cánh đồng \(1\), còn chuồng nằm ở cánh đồng \(N\). Không có cặp cánh đồng nào được nối bởi nhiều con đường trùng lặp, và có thể di chuyển giữa hai cánh đồng bất kỳ trong trang trại bằng cách đi theo một dãy đường thích hợp. Khi đi từ cánh đồng này đến cánh đồng khác, FJ luôn chọn một lộ trình gồm một dãy đường có tổng độ dài nhỏ nhất.

Những cô bò của Farmer John, vẫn luôn thích gây rắc rối, quyết định cản trở thói quen buổi sáng của ông. Chúng dự định chất một đống kiện cỏ khô trên đúng một trong \(M\) con đường của trang trại, khiến độ dài của con đường đó tăng gấp đôi. Những cô bò muốn chọn con đường để chặn sao cho mức tăng quãng đường từ nhà đến chuồng của FJ là lớn nhất. Hãy giúp chúng xác định có thể làm lộ trình của FJ dài thêm nhiều nhất bao nhiêu.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) cách nhau bởi một dấu cách.
• \(M\) dòng tiếp theo, dòng thứ \(j\) chứa ba số nguyên \(A_j\), \(B_j\) và \(L_j\) cách nhau bởi dấu cách, mô tả con đường hai chiều thứ \(j\). Trong đó, \(A_j\) và \(B_j\) là các chỉ số từ \(1\) đến \(N\) của hai cánh đồng được nối bởi con đường, còn \(L_j\) là độ dài con đường, nằm trong đoạn từ \(1\) đến \(1\,000\,000\).

Ràng buộc

• \(1 \le N \le 250\).
• \(1 \le M \le 25\,000\).
• \(1 \le A_j,B_j \le N\).
• \(1 \le L_j \le 1\,000\,000\).
• Không có hai con đường cùng nối một cặp cánh đồng, và mọi cặp cánh đồng đều có thể đi đến nhau.

Dữ liệu ra

In ra mức tăng lớn nhất có thể của tổng độ dài lộ trình ngắn nhất của FJ khi tăng gấp đôi độ dài của một con đường duy nhất.

Ví dụ

5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2

2

Nguồn

USACO 2014 February Contest, Gold — Roadblock

Tác giả: Brian Dean.

\(N\) cô bò của Farmer John (\(1 \le N \le 20\)), vẫn được đánh số thuận tiện từ \(1\) đến \(N\) như thường lệ, đang chuẩn bị cho một cuộc thi mười môn phối hợp gồm \(N\) nội dung khác nhau (vì thế có lẽ nên gọi đây là cuộc thi \(N\) môn phối hợp thay vì mười môn phối hợp, vốn theo truyền thống có đúng \(10\) nội dung).

Bò \(i\) có mức kỹ năng \(s_{ij}\) (\(1 \le s_{ij} \le 1\,000\)) khi thi đấu ở nội dung \(j\). Mỗi cô bò phải thi đấu ở đúng một nội dung và mỗi nội dung phải có một cô bò tham gia.

Tổng điểm của tất cả các cô bò là tổng mức kỹ năng của họ trong những nội dung họ tham gia. Tuy nhiên, ban giám khảo cũng có thể trao điểm thưởng nếu họ đặc biệt ấn tượng. Có \(B\) khoản thưởng (\(1 \le B \le 20\)) mà ban giám khảo có thể trao. Khoản thưởng \(i\) gồm ba phần: nếu các cô bò đạt ít nhất \(P_i\) điểm (\(1 \le P_i \le 40\,000\)) trong \(K_i\) nội dung đầu tiên, tính cả các khoản thưởng khác chỉ liên quan đến những nội dung đó, họ sẽ nhận thêm \(A_i\) điểm (\(1 \le A_i \le 1\,000\)).

Ví dụ, xét \(N=3\) cô bò với các mức kỹ năng sau:

Chẳng hạn, bò \(1\) sẽ mang về cho đội \(7\) điểm nếu tham gia nội dung \(3\).

Giả sử ban giám khảo đưa ra một khoản thưởng (\(B=1\)): nếu các cô bò đạt ít nhất \(7\) điểm trong hai nội dung đầu tiên, họ sẽ nhận thêm \(6\) điểm. Khi đó, cách phân công tối ưu là xếp bò \(1\) thi nội dung \(1\), bò \(2\) thi nội dung \(3\) và bò \(3\) thi nội dung \(2\). Trong hai nội dung đầu tiên, bò \(1\) đạt \(5\) điểm và bò \(3\) đạt \(2\) điểm, tổng cộng là \(7\) điểm, đủ để nhận khoản thưởng \(1\). Do đó, tổng điểm họ đạt được là \(5+2+4+6=17\).

Hãy giúp xác định các nội dung mà những cô bò nên tham gia để tối đa hóa tổng điểm.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(B\) cách nhau bởi một dấu cách.
• \(B\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(K_i\), \(P_i\) và \(A_i\) cách nhau bởi dấu cách, mô tả khoản thưởng thứ \(i\).
• \(N\) dòng cuối, dòng thứ \(j\) chứa \(N\) số nguyên cách nhau bởi dấu cách là \(s_{j1},\ldots,s_{jN}\), mô tả mức kỹ năng của bò \(j\) trong từng nội dung.

Ràng buộc

• \(1 \le N \le 20\).
• \(1 \le B \le 20\).
• \(1 \le s_{ij} \le 1\,000\).
• \(1 \le P_i \le 40\,000\).
• \(1 \le A_i \le 1\,000\).

Dữ liệu ra

In ra tổng điểm lớn nhất mà các cô bò có thể nhận được, bao gồm cả điểm thưởng.

Ví dụ

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

17

Nguồn

USACO 2014 February Contest, Gold — Cow Decathlon

Tác giả: Lewin Gan.

\(N\) cô bò của FJ đã quyết định đi nghỉ và, thật kỳ diệu, tìm được một hãng hàng không sẵn lòng bán vé cho chúng. Tuy nhiên, khi đến sân bay và bắt đầu lên máy bay, chúng phải đối mặt với một vấn đề thú vị.

Máy bay có \(N\) ghế, được mô hình hóa thành các điểm từ \(x=1\) đến \(x=N\) trên trục số. Cả \(N\) cô bò (\(1 \le N \le 200\,000\)) đang xếp hàng chờ đi đến ghế của mình. Bò \(N\) ở vị trí \(x=0\), bò \(N-1\) ở vị trí \(x=-1\), và cứ tiếp tục như vậy. Bò \(i\) được xếp vào ghế \(S_i\), trong đó \(S_1,\ldots,S_N\) là một hoán vị của \(1,\ldots,N\).

Ở mỗi bước thời gian, mỗi cô bò bước sang phải nếu có thể. Khi bò \(i\) đến ghế \(S_i\) của mình, cô sẽ dừng lại để cất hành lý vào ngăn phía trên; việc này mất \(T_i\) giây, sau đó cô mới ngồi xuống. Trong \(T_i\) bước ấy, cô bò đứng ngay sau (nếu có) bị chặn và không thể tiến lên. Nếu phía sau cô là cả một hàng bò thì toàn bộ hàng đó cũng bị chặn.

Hỏi cần bao lâu để tất cả các cô bò ngồi xuống?

Tổng \(T_i\) của tất cả các cô bò nhỏ hơn \(1\,000\,000\,000\).

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(S_i\) và \(T_i\) cách nhau bởi dấu cách.

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(S_1,\ldots,S_N\) là một hoán vị của \(1,\ldots,N\).
• Tổng \(T_i\) của tất cả các cô bò nhỏ hơn \(1\,000\,000\,000\).

Dữ liệu ra

In ra thời gian cần thiết để tất cả các cô bò ngồi vào ghế.

Ví dụ

3
2 5
3 10
1 5

19

cows -> 123
           123 <- seats

 123
   123

 12
   123

    12
   123

Nguồn

USACO 2014 February Contest, Gold — Airplane Boarding

Tác giả: Travis Hance.