USACO 2013 - Tháng 12 - Hạng Vàng

Air Bovinia khai thác các chuyến bay kết nối \(N\) trang trại nơi các cô bò sinh sống (\(1 \le N \le 20\,000\)). Giống như mọi hãng hàng không khác, \(K\) trang trại trong số đó được chỉ định làm trung tâm (\(1 \le K \le 200\), \(K \le N\)).

Hiện tại, Air Bovinia cung cấp \(M\) chuyến bay một chiều (\(1 \le M \le 20\,000\)), trong đó chuyến bay thứ \(i\) đi từ trang trại \(u_i\) đến trang trại \(v_i\) và có giá \(d_i\) đô la (\(1 \le d_i \le 10\,000\)). Như mọi hãng hàng không hợp lý khác, đối với mỗi chuyến bay, ít nhất một trong hai trang trại \(u_i\) và \(v_i\) là một trung tâm. Giữa hai trang trại có nhiều nhất một chuyến bay thẳng theo mỗi hướng, và không chuyến bay nào bắt đầu rồi kết thúc tại cùng một trang trại.

Bessie phụ trách dịch vụ bán vé của Air Bovinia. Không may, trong lúc cô đi nhai cỏ khô ngon lành suốt vài giờ, hãng đã nhận được \(Q\) yêu cầu di chuyển một chiều cho kỳ nghỉ của các cô bò (\(1 \le Q \le 50\,000\)), trong đó yêu cầu thứ \(i\) là đi từ trang trại \(a_i\) đến trang trại \(b_i\).

Vì Bessie đang quá tải với việc xử lý những tấm vé này, hãy giúp cô xác định xem từng yêu cầu có thể được đáp ứng hay không và chi phí nhỏ nhất nếu có thể.

Để giảm kích thước dữ liệu ra, bạn chỉ cần in tổng số yêu cầu vé có thể đáp ứng và tổng các chi phí nhỏ nhất của chúng. Lưu ý rằng tổng chi phí này có thể không vừa trong một số nguyên \(32\) bit.

Dữ liệu vào

• Dòng đầu tiên chứa bốn số nguyên \(N\), \(M\), \(K\) và \(Q\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa \(u_i\), \(v_i\) và \(d_i\).
• \(K\) dòng tiếp theo, mỗi dòng chứa mã số của một trung tâm.
• \(Q\) dòng cuối, dòng thứ \(i\) chứa hai số \(a_i\) và \(b_i\), biểu thị một yêu cầu vé từ trang trại \(a_i\) đến trang trại \(b_i\).

Ràng buộc

• \(1 \le N \le 20\,000\).
• \(1 \le K \le 200\) và \(K \le N\).
• \(1 \le M \le 20\,000\).
• \(1 \le u_i,v_i \le N\) và \(u_i \ne v_i\).
• \(1 \le d_i \le 10\,000\).
• Mỗi chuyến bay có ít nhất một đầu mút là trung tâm; giữa hai trang trại có nhiều nhất một chuyến bay thẳng theo mỗi hướng.
• Mỗi mã số trung tâm nằm trong đoạn từ \(1\) đến \(N\).
• \(1 \le Q \le 50\,000\).
• \(1 \le a_i,b_i \le N\) và \(a_i \ne b_i\).

Dữ liệu ra

• Dòng đầu tiên chứa số yêu cầu vé có thể được đáp ứng.
• Dòng thứ hai chứa tổng các chi phí nhỏ nhất để đáp ứng những yêu cầu vé có thể thực hiện được.

Ví dụ

3 3 1 2
1 2 10
2 3 10
2 1 5
2
1 3
3 1

1
20

Nguồn

USACO 2013 December Contest, Gold — Problem 1: Vacation Planning (gold)

Tác giả: Kalki Seksaria và Richard Peng, 2013.

Farmer John vừa mua một chuồng bò mới có \(N\) máy vắt sữa (\(1 \le N \le 40\,000\)), được đánh số thuận tiện từ \(1\) đến \(N\) và xếp thành một hàng.

Máy vắt sữa \(i\) có thể lấy được \(M(i)\) đơn vị sữa mỗi ngày (\(1 \le M(i) \le 100\,000\)). Không may, các máy được lắp quá sát nhau nên nếu máy \(i\) được sử dụng trong một ngày nào đó thì hai máy kề nó không thể được sử dụng trong ngày ấy; dĩ nhiên, các máy ở hai đầu chỉ có một máy kề. Farmer John có thể chọn các tập máy khác nhau để vận hành vào những ngày khác nhau.

Farmer John muốn tính lượng sữa lớn nhất có thể lấy được trong \(D\) ngày (\(1 \le D \le 50\,000\)). Vào đầu mỗi ngày, ông có đủ thời gian để bảo trì một máy vắt sữa \(i\) được chọn, qua đó thay đổi sản lượng sữa hằng ngày \(M(i)\) của máy kể từ ngày đó trở đi. Với danh sách các thay đổi hằng ngày này, hãy cho Farmer John biết ông có thể sản xuất bao nhiêu sữa trong \(D\) ngày. Lưu ý rằng kết quả có thể không vừa trong một số nguyên \(32\) bit.

Dữ liệu vào

• Dòng đầu tiên chứa \(N\) và \(D\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa giá trị ban đầu của \(M(i)\).
• \(D\) dòng cuối, dòng thứ \(d\) chứa hai số nguyên \(i\) và \(m\), cho biết Farmer John cập nhật \(M(i)\) thành \(m\) vào đầu ngày \(d\).

Ràng buộc

• \(1 \le N \le 40\,000\).
• \(1 \le M(i) \le 100\,000\).
• \(1 \le D \le 50\,000\).

Dữ liệu ra

In ra tổng lượng sữa lớn nhất Farmer John có thể sản xuất trong \(D\) ngày.

Ví dụ

5 3
1
2
3
4
5
5 2
2 7
1 10

32

Nguồn

USACO 2013 December Contest, Gold — Problem 2: Optimal Milking

Tác giả: Brian Dean, 2013.

Bessie đang luyện các màn ảo thuật với bài. Cô đã thành thạo phép xáo bài Bessie: một phép xáo trên \(M\) lá bài (\(2 \le M \le 100\,000\)), sắp xếp lại sao cho lá bài thứ \(i\) tính từ trên xuống chuyển đến vị trí thứ \(P[i]\) tính từ trên xuống.

Giờ đây, Bessie đang luyện xáo những bộ bài lớn hơn. Cô có một bộ gồm \(N\) lá bài (\(M \le N \le 1\,000\,000\,000\)), được đánh số thuận tiện từ \(1\) đến \(N\). Cô xáo bộ bài này bằng cách lấy \(M\) lá đầu tiên, thực hiện phép xáo Bessie trên chúng, rồi đặt các lá đã xáo trở lại trên cùng bộ bài. Sau đó, cô lấy lá trên cùng ra và đặt úp xuống. Cô lặp lại quá trình này, lần lượt đặt các lá trên cùng chồng lên nhau, cho đến khi không còn lá nào. Khi còn ít hơn \(M\) lá, Bessie không thực hiện phép xáo Bessie nữa nhưng vẫn tiếp tục đặt lá trên cùng lên trên các lá còn lại.

Bessie biết rằng ban đầu bộ bài được sắp theo thứ tự, với lá \(1\) ở trên cùng, tiếp theo là lá \(2\), và lá \(N\) ở dưới cùng. Cho mô tả của phép xáo Bessie, hãy giúp Bessie xác định những lá bài nằm tại \(Q\) vị trí được chỉ định khác nhau (\(1 \le Q \le N\), \(Q \le 5\,000\)) trong bộ bài cuối cùng.

Dữ liệu vào

• Dòng đầu tiên chứa ba số \(N\), \(M\) và \(Q\), cách nhau bởi dấu cách.
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa \(P[i]\), là vị trí tính từ trên xuống của lá bài thứ \(i\) sau phép xáo Bessie.
• \(Q\) dòng cuối, dòng thứ \(i\) chứa một số nguyên \(q_i\). Bạn cần xác định nhãn của lá bài nằm ở vị trí \(q_i\) tính từ trên xuống.

Ràng buộc

• \(2 \le M \le 100\,000\).
• \(M \le N \le 1\,000\,000\,000\).
• \(1 \le Q \le N\) và \(Q \le 5\,000\); các vị trí được truy vấn đôi một khác nhau.
• \(1 \le P[i] \le M\).
• \(1 \le q_i \le N\).

Phân nhóm

• \(50\%\) số bộ kiểm thử có \(N \le 100\,000\).

Dữ liệu ra

Với mỗi truy vấn \(i\), in ra trên dòng thứ \(i\) một số nguyên là nhãn của lá bài tại vị trí \(q_i\) tính từ trên xuống.

Ví dụ

5 3 5
3
1
2
1
2
3
4
5

4
5
3
1
2

Nguồn

USACO 2013 December Contest, Gold — Problem 3: The Bessie Shuffle (gold)

Tác giả: Mark Gordon, 2013.