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

Farmer John và đàn bò đang chơi ném đĩa. Bessie ném chiếc đĩa xuống cánh đồng, nhưng nó đang bay thẳng về phía Mark, người làm công thuộc đội đối thủ! Mark cao \(H\) (\(1 \le H \le 1\,000\,000\,000\)), nhưng có \(N\) cô bò thuộc đội Bessie đang tụ tập quanh Mark (\(2 \le N \le 20\)). Họ chỉ có thể bắt được chiếc đĩa nếu chồng lên nhau để đạt độ cao ít nhất bằng Mark. Mỗi cô bò trong số \(N\) cô bò có một chiều cao, khối lượng và sức chịu đựng. Sức chịu đựng của một cô bò cho biết tổng khối lượng tối đa của những cô bò có thể được xếp phía trên cô ấy.

Với các điều kiện này, Bessie muốn biết đội của mình có thể dựng một chồng bò đủ cao để bắt chiếc đĩa hay không; nếu có, hệ số an toàn lớn nhất của một chồng như vậy là bao nhiêu. Hệ số an toàn của một chồng bò là khối lượng có thể đặt thêm lên đỉnh chồng mà không vượt quá sức chịu đựng của bất kỳ cô bò nào.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(H\).

\(N\) dòng tiếp theo, mỗi dòng mô tả một cô bò bằng chiều cao, khối lượng và sức chịu đựng của cô ấy. Tất cả đều là các số nguyên dương không vượt quá 1 tỷ.

Dữ liệu ra

Nếu đội của Bessie có thể dựng một chồng bò đủ cao để bắt chiếc đĩa, hãy in ra hệ số an toàn lớn nhất có thể đạt được của một chồng như vậy. Nếu không, in ra Mark is too tall (không gồm dấu ngoặc kép).

Ví dụ

4 10
9 4 1
3 3 5
5 5 10
4 4 5

2

Nguồn

USACO 2014 December Contest, Gold — Guard Mark. Tác giả đề: Bill Cooperman, 2014.

https://usaco.org/index.php?page=viewproblem2&cpid=494

Là một người rất mê chạy marathon, Bessie thích tạo ra các đường chạy marathon cho những cô bò khác. Gần đây nhất, cô đã thiết kế một đường chạy gồm \(N\) checkpoint (\(1 \le N \le 100\,000\)) phải được ghé thăm theo thứ tự.

Không may, Bessie nhận ra rằng những cô bò khác có thể không đủ sức bền để chạy toàn bộ đường chạy. Vì vậy, cô muốn biết một số đường chạy con cần bao lâu để hoàn thành, trong đó một đường chạy con là một dãy con liên tiếp của các checkpoint trên toàn bộ đường chạy. Mọi chuyện còn phức tạp hơn vì Bessie biết rằng những cô bò khác vốn lười biếng có thể chọn bỏ qua một checkpoint mỗi khi chạy một đường chạy con — checkpoint nào giúp tổng thời gian di chuyển nhỏ nhất. Tuy nhiên, họ không được phép bỏ qua checkpoint đầu tiên hoặc cuối cùng của một đường chạy con.

Để xây dựng đường chạy marathon tốt nhất có thể, Bessie muốn nghiên cứu hệ quả của việc thay đổi vị trí các checkpoint trên đường chạy hiện tại. Hãy giúp cô xác định những thay đổi nhất định đối với vị trí checkpoint sẽ ảnh hưởng thế nào đến thời gian cần thiết để chạy các đường chạy con khác nhau, có tính đến việc các cô bò có thể chọn bỏ qua một checkpoint mỗi khi chạy một đường chạy con.

Vì đường chạy nằm trong khu trung tâm với mạng lưới đường phố dạng ô vuông, khoảng cách giữa hai checkpoint tại \((x_1,y_1)\) và \((x_2,y_2)\) được tính bằng \(|x_1-x_2|+|y_1-y_2|\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(Q\) (\(1 \le Q \le 100\,000\)).

\(N\) dòng tiếp theo chứa các vị trí \((x,y)\) của \(N\) checkpoint theo thứ tự phải ghé thăm trên đường chạy. Tất cả các tọa độ đều nằm trong khoảng từ \(-1000\) đến \(1000\).

\(Q\) dòng tiếp theo gồm các thao tác cập nhật và truy vấn, mỗi dòng một thao tác, được xử lý theo đúng thứ tự xuất hiện. Mỗi dòng có dạng U I X Y hoặc Q I J. Dòng có dạng U I X Y cho biết vị trí của checkpoint \(I\) (\(1 \le I \le N\)) được đổi thành \((X,Y)\). Dòng có dạng Q I J yêu cầu thời gian di chuyển nhỏ nhất của đường chạy con từ checkpoint \(I\) đến checkpoint \(J\) (\(I \le J\)), với điều kiện các cô bò chọn bỏ qua một checkpoint trên đường chạy con này, nhưng không bỏ qua hai đầu mút \(I\) và \(J\).

Dữ liệu ra

Với mỗi yêu cầu tính độ dài đường chạy con, in độ dài cần tìm trên một dòng riêng.

Ví dụ

5 5
-4 4
-5 -3
-1 5
-3 4
0 5
Q 1 5
U 4 0 1
U 4 -1 1
Q 2 4
Q 1 4

11
8
8

Nguồn

USACO 2014 December Contest, Gold — Marathon. Tác giả đề: Nick Wu, 2014.

https://usaco.org/index.php?page=viewproblem2&cpid=495

\(N\) con bò của Farmer John (\(1 \le N \le 100\,000\)) lại ra ngoài vận động móng guốc, chạy bộ dọc theo một đường đua dài vô hạn. Mỗi con bò xuất phát tại một vị trí khác nhau trên đường đua, và một số con chạy với tốc độ khác nhau.

Đường đua được chia thành nhiều làn để các con bò có thể vượt qua nhau. Hai con bò trong cùng một làn không bao giờ được chiếm cùng một vị trí. Farmer John không muốn bất kỳ con bò nào phải đổi làn hay điều chỉnh tốc độ, và ông muốn biết cần bao nhiêu làn để đáp ứng điều này nếu đàn bò sẽ chạy trong \(T\) phút (\(1 \le T \le 1\,000\,000\,000\)).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(T\).

\(N\) dòng tiếp theo, mỗi dòng chứa vị trí ban đầu và tốc độ của một con bò. Vị trí là một số nguyên không âm và tốc độ là một số nguyên dương; cả hai số đều không vượt quá 1 tỷ. Tất cả các con bò xuất phát tại những vị trí khác nhau, và các vị trí này được cho theo thứ tự tăng dần trong dữ liệu vào.

Dữ liệu ra

In một số nguyên duy nhất cho biết số làn tối thiểu cần thiết để không có hai con bò nào trong cùng một làn từng chiếm cùng một vị trí (kể cả tại thời điểm \(T\)).

Ví dụ

5 3
0 1
1 2
2 3
3 2
6 1

3

Nguồn

USACO 2014 December Contest, Gold - Cow Jog: https://usaco.org/index.php?page=viewproblem2&cpid=496

Tác giả: Mark Gordon, 2014.