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

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 2014 - Milk Scheduling 100 (p) 4.0s 512M
2 USACO 2014 - Vacation Planning 100 (p) 4.0s 512M
3 USACO 2014 - The Bessie Shuffle (gold) 100 (p) 4.0s 512M

1. USACO 2014 - Milk Scheduling

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

Farmer John có \(N\) con bò cần được vắt sữa (\(1 \le N \le 10\,000\)), và mỗi con chỉ cần đúng một đơn vị thời gian để vắt sữa.

Vì thiếu kiên nhẫn, một số con bò sẽ từ chối cho vắt sữa nếu Farmer John chờ quá lâu. Cụ thể hơn, bò \(i\) cho \(g_i\) gallon sữa (\(1 \le g_i \le 1000\)), nhưng chỉ khi nó được vắt sữa trước thời hạn tại thời điểm \(d_i\) (\(1 \le d_i \le 10\,000\)). Thời gian bắt đầu tại \(t=0\), vì vậy tổng cộng nhiều nhất \(x\) con bò có thể được vắt sữa trước thời hạn tại thời điểm \(t=x\).

Hãy giúp Farmer John xác định lượng sữa lớn nhất ông có thể thu được nếu sắp xếp việc vắt sữa một cách tối ưu.

Dữ liệu vào

  • Dòng đầu tiên chứa \(N\).
  • \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(g_i\) và \(d_i\).

Ràng buộc

  • \(1 \le N \le 10\,000\).
  • \(1 \le g_i \le 1000\).
  • \(1 \le d_i \le 10\,000\).

Dữ liệu ra

In ra số gallon sữa lớn nhất Farmer John có thể thu được.

Ví dụ

Ví dụ 1

Input 
4
10 3
7 5
8 1
2 1
Output 
25
Giải thích

Có \(4\) con bò. Con thứ nhất cho \(10\) gallon sữa nếu được vắt trước thời hạn tại thời điểm \(3\), và các con còn lại cũng được mô tả tương tự.

Farmer John vắt sữa bò \(3\) trước tiên và bỏ qua bò \(4\), vì do xung đột với bò \(3\) nên không thể vắt sữa bò \(4\) trước thời hạn của nó. Sau đó, Farmer John vắt sữa bò \(1\) và bò \(2\).

Nguồn

USACO 2013 December Contest, Silver — Problem 1: Milk Scheduling

Tác giả: Traditional, 2011.

2. USACO 2014 - Vacation Planning

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

Air Bovinia đang lên kế hoạch kết nối \(N\) trang trại nơi các cô bò sinh sống (\(1 \le N \le 200\)). Giống như mọi hãng hàng không khác, \(K\) trong số các trang trại này (\(1 \le K \le 100\), \(K \le N\)) đã được chọn làm trung tâm. Các trang trại được đánh số thuận tiện từ \(1\) đến \(N\), trong đó các trang trại từ \(1\) đến \(K\) là các trung tâm.

Hiện có \(M\) chuyến bay một chiều (\(1 \le M \le 10\,000\)) kết nối các trang trại. 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 1\,000\,000\)).

Gần đây, hãng hàng không nhận được yêu cầu cho \(Q\) hành trình một chiều (\(1 \le Q \le 10\,000\)). Hành trình thứ \(i\) đi từ trang trại \(a_i\) đến trang trại \(b_i\). Để đi từ \(a_i\) đến \(b_i\), hành trình có thể gồm một dãy bất kỳ các chuyến bay thẳng, thậm chí có thể ghé cùng một trang trại nhiều lần, nhưng phải đi qua ít nhất một trung tâm; trung tâm đó có thể là điểm xuất phát, điểm đến hoặc không phải cả hai. Điều kiện này có thể khiến một số yêu cầu không có lộ trình hợp lệ. Với mọi yêu cầu còn lại, hãy giúp Air Bovinia xác định chi phí nhỏ nhất của một lộ trình hợp lệ.

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\), mô tả chuyến bay thứ \(i\).
  • \(Q\) dòng cuối, dòng thứ \(i\) chứa \(a_i\) và \(b_i\), mô tả hành trình thứ \(i\).

Ràng buộc

  • \(1 \le N \le 200\).
  • \(1 \le K \le 100\) và \(K \le N\); các trang trại \(1,2,\ldots,K\) là các trung tâm.
  • \(1 \le M \le 10\,000\).
  • \(1 \le d_i \le 1\,000\,000\).
  • \(1 \le Q \le 10\,000\).

Dữ liệu ra

  • Dòng đầu tiên chứa số hành trình trong \(Q\) yêu cầu có tồn tại lộ trình hợp lệ.
  • Dòng thứ hai chứa tổng chi phí nhỏ nhất của tất cả các hành trình có lộ trình hợp lệ, trong đó mỗi hành trình được tính theo chi phí nhỏ nhất có thể của nó.

Ví dụ

Ví dụ 1

Input 
3 3 1 3
3 1 10
1 3 10
1 2 7
3 2
2 3
1 2
Output 
2
24
Giải thích

Có ba trang trại, được đánh số từ \(1\) đến \(3\); trang trại \(1\) là một trung tâm. Có một chuyến bay giá \(10\) đô la từ trang trại \(3\) đến trang trại \(1\), và các chuyến bay khác cũng được mô tả tương tự. Các hành trình cần xét lần lượt là từ \(3\) đến \(2\), từ \(2\) đến \(3\) và từ \(1\) đến \(2\).

Hành trình từ \(3\) đến \(2\) chỉ có một lộ trình, với chi phí \(10+7\). Hành trình từ \(2\) đến \(3\) không có lộ trình hợp lệ vì không có chuyến bay nào rời trang trại \(2\). Hành trình từ \(1\) đến \(2\) cũng chỉ có một lộ trình hợp lệ, với chi phí \(7\).

Nguồn

USACO 2013 December Contest, Silver — Problem 2: Vacation Planning

Tác giả: Kalki Seksaria, 2013.

3. USACO 2014 - The Bessie Shuffle (gold)

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

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ụ

Ví dụ 1

Input 
5 3 5
3
1
2
1
2
3
4
5
Output 
4
5
3
1
2
Giải thích

Bessie có một bộ \(5\) lá ban đầu theo thứ tự \([1,2,3,4,5]\). Phép xáo của cô tác động lên \(3\) lá và có hiệu ứng chuyển lá trên cùng xuống cuối nhóm. Có \(5\) truy vấn, lần lượt hỏi mọi vị trí trong bộ bài.

Quá trình xáo diễn ra như sau:

  • \([1,2,3,4,5] \to [2,3,1,4,5]\) (đặt úp lá \(2\) xuống).
  • \([3,1,4,5] \to [1,4,3,5]\) (đặt úp lá \(1\) xuống).
  • \([4,3,5] \to [3,5,4]\) (đặt úp lá \(3\) xuống).
  • \([5,4]\) (đặt úp lá \(5\) xuống).
  • \([4]\) (đặt úp lá \(4\) xuống).

Quá trình này tạo ra thứ tự cuối cùng \([4,5,3,1,2]\).

Nguồn

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

Tác giả: Mark Gordon, 2013.