USACO 2014 - US Open - Hạng Bạc

\(N\) con bò của Farmer John (\(2 \le N \le 100\,000\)) đang đứng tại nhiều vị trí khác nhau dọc theo một hàng rào dài một chiều. Con bò thứ \(i\) đứng tại vị trí \(x_i\) (một số nguyên trong đoạn từ \(0\) đến \(1\,000\,000\,000\)) và là bò trắng trơn hoặc bò đốm. Không có hai con bò nào đứng cùng một vị trí, và có ít nhất một con bò trắng.

Farmer John muốn chụp ảnh một đoạn liên tiếp gồm các con bò để mang đến hội chợ hạt. Để công bằng với những con bò khác nhau của mình, ông muốn trong ảnh có số bò trắng bằng số bò đốm. Farmer John muốn xác định kích thước lớn nhất của một bức ảnh công bằng như vậy, trong đó kích thước của bức ảnh là hiệu giữa vị trí lớn nhất và vị trí nhỏ nhất của các con bò trong ảnh.

Để có cơ hội chụp được một bức ảnh lớn hơn nữa, Farmer John mang theo một thùng sơn và có thể tùy ý chọn một tập con các con bò trắng để sơn đốm lên chúng, qua đó biến chúng thành bò đốm. Hãy xác định kích thước lớn nhất của một bức ảnh công bằng mà Farmer John có thể chụp khi ông được phép sơn một số con bò trắng; tất nhiên, nếu thấy tốt hơn thì ông không cần sơn con nào.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(x_i\) và ký tự W nếu đó là bò trắng hoặc S nếu đó là bò đốm.

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(0 \le x_i \le 1\,000\,000\,000\).
• Không có hai con bò nào đứng cùng một vị trí.
• Có ít nhất một con bò trắng.

Dữ liệu ra

• In ra kích thước lớn nhất của một bức ảnh công bằng mà Farmer John có thể chụp sau khi có thể đã sơn một số con bò trắng thành bò đốm.

Ví dụ

5
8 W
11 S
3 W
10 W
5 S

7

Nguồn

USACO 2014 US Open, Silver — Problem 1: Fair Photography

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

Farmer John vừa mua một chiếc ô tô mới trên mạng. Vì quá vội, khi chọn các tính năng bổ sung cho xe, ông vô tình nhấn nút "Submit" hai lần; kết quả là chiếc xe được trang bị tới hai hệ thống định vị GPS! Tệ hơn nữa, hai hệ thống này thường đưa ra những quyết định trái ngược nhau về lộ trình Farmer John nên đi.

Bản đồ khu vực Farmer John sinh sống gồm \(N\) giao lộ (\(2 \le N \le 10\,000\)) và \(M\) con đường có hướng (\(1 \le M \le 50\,000\)). Đường thứ \(i\) nối từ giao lộ \(A_i\) (\(1 \le A_i \le N\)) đến giao lộ \(B_i\) (\(1 \le B_i \le N\)). Có thể có nhiều con đường nối cùng một cặp giao lộ. Một con đường hai chiều được biểu diễn bằng hai con đường có hướng riêng biệt theo hai hướng ngược nhau. Nhà của Farmer John nằm tại giao lộ \(1\), còn trang trại của ông nằm tại giao lộ \(N\). Bảo đảm có thể đi từ nhà đến trang trại theo một dãy các con đường có hướng.

Cả hai thiết bị GPS đều dùng cùng bản đồ nói trên, nhưng chúng đánh giá thời gian đi trên mỗi con đường khác nhau. Theo thiết bị GPS thứ nhất, cần \(P_i\) đơn vị thời gian để đi qua đường thứ \(i\); theo thiết bị thứ hai, cần \(Q_i\) đơn vị thời gian. Mỗi thời gian là một số nguyên trong đoạn từ \(1\) đến \(100\,000\).

Farmer John muốn đi từ nhà đến trang trại. Tuy nhiên, mỗi thiết bị GPS sẽ lớn tiếng phàn nàn bất cứ khi nào ông đi theo một con đường, chẳng hạn từ giao lộ \(X\) đến giao lộ \(Y\), mà thiết bị đó cho rằng không thuộc một đường đi ngắn nhất từ \(X\) đến trang trại. Cả hai thiết bị đều có thể cùng phàn nàn nếu Farmer John đi trên một con đường mà không thiết bị nào thích.

Hãy giúp Farmer John xác định tổng số lời phàn nàn nhỏ nhất có thể nhận được nếu ông chọn lộ trình thích hợp. Nếu cả hai thiết bị cùng phàn nàn khi ông đi qua một con đường, tổng số lời phàn nàn tăng thêm \(2\).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\).
• \(M\) dòng tiếp theo, dòng mô tả đường thứ \(i\) chứa bốn số nguyên \(A_i\), \(B_i\), \(P_i\), \(Q_i\).

Ràng buộc

• \(2 \le N \le 10\,000\).
• \(1 \le M \le 50\,000\).
• \(1 \le A_i,B_i \le N\).
• \(1 \le P_i,Q_i \le 100\,000\).
• Có thể có nhiều con đường nối cùng một cặp giao lộ; đường hai chiều được biểu diễn bằng hai đường có hướng ngược nhau.
• Bảo đảm có đường đi từ giao lộ \(1\) đến giao lộ \(N\).

Dữ liệu ra

• In ra tổng số lời phàn nàn nhỏ nhất Farmer John có thể nhận được nếu chọn tối ưu lộ trình từ nhà đến trang trại.

Ví dụ

5 7
3 4 7 1
1 3 2 20
1 4 17 18
4 5 25 3
1 2 10 1
3 5 4 14
2 4 6 5

1

Nguồn

USACO 2014 US Open, Silver — Problem 2: Dueling GPSs

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

Những cô bò của Farmer John đang đi du lịch bằng ô tô! Đồng hồ đo quãng đường trên xe hiển thị một giá trị nguyên, bắt đầu ở \(X\) dặm (\(100 \le X \le 10^{18}\)) khi chuyến đi bắt đầu và kết thúc ở \(Y\) dặm (\(X \le Y \le 10^{18}\)) khi chuyến đi kết thúc. Mỗi khi đồng hồ hiển thị một số "thú vị" (kể cả tại thời điểm bắt đầu và kết thúc chuyến đi), những cô bò sẽ rống lên. Một số được gọi là "thú vị" nếu, khi xét tất cả các chữ số của nó ngoại trừ các số \(0\) vô nghĩa ở đầu, có ít nhất một nửa số chữ số giống nhau. Ví dụ, các số \(3223\) và \(110\) là thú vị, còn các số \(97791\) và \(123\) thì không.

Hãy giúp Farmer John đếm số lần những cô bò sẽ rống trong chuyến đi.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(X\) và \(Y\), cách nhau bởi một dấu cách.

Ràng buộc

• \(100 \le X \le Y \le 10^{18}\).

Dữ liệu ra

• In ra một số nguyên duy nhất là số lần những cô bò sẽ rống trong chuyến đi.

Ví dụ

110 133

14

Nguồn

USACO 2014 US Open, Silver — Problem 3: Odometer

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