USACO 2011 - Tháng 12 - Hạng Bạc

Hôm nay những chú bò đặc biệt tinh nghịch! Nông dân John chỉ muốn chụp một bức ảnh những chú bò đang đứng thành hàng, nhưng chúng cứ di chuyển ngay trước khi ông kịp bấm máy.

Cụ thể, mỗi chú trong số \(N\) (\(1 \le N \le 20\,000\)) chú bò của FJ có một số hiệu nguyên duy nhất. FJ muốn chụp những chú bò đứng thành hàng theo một thứ tự rất cụ thể, được biểu diễn bởi nội dung của mảng \(A[1..N]\), trong đó \(A[j]\) là số hiệu của chú bò thứ \(j\) trong thứ tự này. Ông xếp những chú bò theo đúng thứ tự đó, nhưng ngay trước khi ông kịp nhấn nút chụp ảnh, một nhóm gồm không hoặc nhiều chú bò (không nhất thiết liên tiếp) chuyển đến một tập hợp vị trí mới trong hàng. Chính xác hơn, một nhóm gồm không hoặc nhiều chú bò bước ra khỏi hàng, còn những chú bò ở lại dịch chuyển để lấp các khoảng trống vừa tạo ra. Sau đó, những chú bò đã bước ra chen trở lại vào các vị trí khác trong hàng (không nhất thiết là vị trí ban đầu của chúng). Dù bực mình nhưng không nản chí, FJ lại xếp đàn bò theo thứ tự trong \(A\); tuy nhiên, ngay trước lúc ông kịp chụp, một nhóm khác gồm không hoặc nhiều chú bò lại chuyển đến một tập hợp vị trí mới trong hàng.

Quá trình trên lặp lại cho đến khi FJ chụp tổng cộng năm bức ảnh rồi bỏ cuộc. Cho biết nội dung của từng bức ảnh, hãy khôi phục thứ tự dự định ban đầu \(A\). Mỗi bức ảnh cho thấy một thứ tự của đàn bò khác với \(A\) ở chỗ một nhóm gồm không hoặc nhiều chú bò đã di chuyển. Tuy nhiên, mỗi chú bò chỉ di chuyển trong nhiều nhất một bức ảnh: nếu một chú bò thuộc nhóm di chuyển trong một bức ảnh thì nó sẽ không chủ động di chuyển trong bất kỳ bức ảnh nào trong bốn bức còn lại (tất nhiên, chỉ số vị trí của nó vẫn có thể thay đổi do những chú bò xung quanh di chuyển).

Dữ liệu vào

• Dòng đầu tiên chứa số lượng bò \(N\) (\(1 \le N \le 20\,000\)).
• \(5N\) dòng tiếp theo mô tả năm thứ tự, mỗi thứ tự là một khối gồm \(N\) dòng liên tiếp. Mỗi dòng chứa số hiệu của một chú bò, là một số nguyên trong đoạn từ \(0\) đến \(1\,000\,000\,000\).

Dữ liệu ra

• Gồm \(N\) dòng mô tả thứ tự dự định \(A\), mỗi dòng chứa một số hiệu.

Ví dụ

5
10
20
30
40
50
20
10
30
40
50
30
10
20
40
50
40
10
20
30
50
50
10
20
30
40

10
20
30
40
50

Nguồn

USACO 2011 December Contest, Silver Division — Cow Photography

Tác giả đề: Brian Dean, 2011.

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.

Hôm nay trời mưa! \(N\) (\(1 \le N \le 5\,000\)) chú bò của Nông dân John, được đánh số từ \(1\) đến \(N\), đặc biệt không thích bị ướt. Những chú bò đang đứng trong các ô chuồng không có mái che, được sắp xếp trên một trục số. Các ô chuồng có tọa độ \(X\) từ \(1\) đến \(M\) (\(1 \le M \le 100\,000\)). Chú bò \(i\) đứng trong ô chuồng tại tọa độ \(X_i\) (\(1 \le X_i \le M\)). Không có hai chú bò nào đứng chung một ô chuồng.

Để bảo vệ đàn bò khỏi mưa, Nông dân John muốn mua ô cho chúng. Một chiếc ô phủ từ tọa độ \(X_i\) đến \(X_j\) (\(X_i \le X_j\)) có chiều rộng \(X_j-X_i+1\). Chi phí để mua một chiếc ô có chiều rộng \(W\) là \(C_W\) (\(1 \le C_W \le 1\,000\,000\)). Ô lớn hơn không nhất thiết đắt hơn ô nhỏ hơn.

Hãy giúp Nông dân John tìm chi phí nhỏ nhất để mua một tập hợp ô che mưa cho mọi chú bò. Lưu ý rằng các chiếc ô trong một phương án tối ưu có thể chồng lấn lên nhau một phần.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách: \(N\) và \(M\).
• \(N\) dòng tiếp theo; dòng thứ \(i\) chứa một số nguyên duy nhất \(X_i\).
• \(M\) dòng tiếp theo; dòng thứ \(j\) chứa một số nguyên duy nhất \(C_j\).

Dữ liệu ra

• Dòng đầu tiên chứa một số nguyên duy nhất là chi phí nhỏ nhất cần thiết để mua ô cho tất cả những chú bò.

Ví dụ

6 12
1
2
11
8
4
12
2
3
4
4
8
9
15
16
17
18
19
19

9

UUUUUUUUUU           U        UUUU
C  C     C           C        C  C
|--|--|--|--|--|--|--|--|--|--|--|
1  2  3  4  5  6  7  8  9  10 11 12

Nguồn

USACO 2011 December Contest, Silver Division — Umbrellas for Cows

Tác giả đề: Alex Chen, 2011.