USACO 2014 - Tháng 1 - Hạng Bạc

Cô bò Bessie đang thi đấu môn trượt tuyết băng đồng tại Thế vận hội Moolympic mùa đông. Ban đầu, cô di chuyển với vận tốc \(1\) mét mỗi giây. Tuy nhiên, theo thời gian cô ngày càng mệt và bắt đầu chậm lại. Mỗi lần Bessie chậm lại, vận tốc của cô giảm: sau lần đầu tiên, cô di chuyển với vận tốc \(1/2\) mét mỗi giây; sau hai lần, cô di chuyển với vận tốc \(1/3\) mét mỗi giây; và cứ tiếp tục như vậy.

Bạn được cho biết thời điểm và vị trí Bessie chậm lại dưới dạng một chuỗi sự kiện. Một sự kiện như

T 17

có nghĩa là Bessie chậm lại tại một thời điểm cụ thể, ở đây là sau khi cuộc đua bắt đầu \(17\) giây. Một sự kiện như

D 10

có nghĩa là Bessie chậm lại tại một khoảng cách cụ thể tính từ điểm xuất phát, trong trường hợp này là \(10\) mét.

Cho danh sách \(N\) sự kiện như vậy (\(1 \le N \le 10\,000\)), hãy tính thời gian tính bằng giây để Bessie đi hết một kilômét. Làm tròn đáp án đến số giây nguyên gần nhất; \(0{,}5\) được làm tròn lên \(1\).

Dữ liệu vào

• Dòng đầu tiên chứa \(N\).
• \(N\) dòng tiếp theo, mỗi dòng có dạng T x hoặc D x, lần lượt biểu thị một sự kiện theo thời gian hoặc theo khoảng cách. Trong cả hai trường hợp, \(x\) là một số nguyên và sự kiện được đảm bảo xảy ra trước khi Bessie đi đủ tổng quãng đường một kilômét. Nhiều sự kiện có thể xảy ra đồng thời, khiến Bessie chậm đi đáng kể cùng một lúc. Các sự kiện có thể không được liệt kê theo thứ tự.

Ràng buộc

• \(1 \le N \le 10\,000\).
• Mỗi \(x\) là một số nguyên và sự kiện tương ứng xảy ra trước khi Bessie đi được một kilômét.

Dữ liệu ra

In ra tổng thời gian cần thiết để Bessie đi được \(1\) kilômét, làm tròn đến số giây nguyên gần nhất với trường hợp đúng nửa giây được làm tròn lên.

Ví dụ

2
T 30
D 10

2970

Nguồn

USACO 2014 January Contest, Silver — Problem 1: Bessie Slows Down

Tác giả: Brian Dean, 2014.

Đường trượt tuyết băng đồng tại Thế vận hội Moolympic được mô tả bằng một lưới độ cao \(M \times N\) (\(1 \le M,N \le 500\)), trong đó mỗi độ cao nằm trong đoạn từ \(0\) đến \(1\,000\,000\,000\).

Một số ô trong lưới được chỉ định làm các điểm kiểm soát của đường trượt. Ban tổ chức Moolympic muốn gán độ khó \(D\) cho toàn bộ đường trượt sao cho một cô bò có thể đi từ bất kỳ điểm kiểm soát nào đến bất kỳ điểm kiểm soát nào khác bằng cách liên tục trượt từ một ô sang một ô kề có chênh lệch độ cao tuyệt đối không quá \(D\). Hai ô được coi là kề nhau nếu một ô nằm ngay phía bắc, nam, đông hoặc tây của ô kia. Độ khó của đường trượt là giá trị nhỏ nhất của \(D\) sao cho mọi điểm kiểm soát đều có thể đi đến lẫn nhau theo cách này.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(M\) và \(N\).
• \(M\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên là độ cao của các ô.
• \(M\) dòng cuối, mỗi dòng chứa \(N\) giá trị bằng \(0\) hoặc \(1\); giá trị \(1\) cho biết ô tương ứng là một điểm kiểm soát.

Ràng buộc

• \(1 \le M,N \le 500\).
• Mỗi độ cao nằm trong đoạn từ \(0\) đến \(1\,000\,000\,000\).

Dữ liệu ra

In ra độ khó của đường trượt, tức giá trị nhỏ nhất của \(D\) sao cho mọi điểm kiểm soát vẫn có thể đi đến lẫn nhau.

Ví dụ

3 5
20 21 18 99 5
19 22 20 16 26
18 17 40 60 80
1 0 0 0 1
0 0 0 0 0
0 0 0 0 1

21

Nguồn

USACO 2014 January Contest, Silver — Cross Country Skiing

Tác giả: William Hu và Brian Dean, 2014.

Là một người hâm mộ mọi môn thể thao mùa lạnh (đặc biệt là những môn có liên quan đến bò), Farmer John muốn ghi hình càng nhiều chương trình của kỳ Thế vận hội mùa đông Moolympics sắp tới càng tốt.

Lịch phát sóng Moolympics gồm \(N\) chương trình khác nhau (\(1 \le N \le 150\)), mỗi chương trình có thời điểm bắt đầu và kết thúc được xác định. FJ có một thiết bị ghi hình hai bộ thu, có thể ghi đồng thời hai chương trình. Hãy giúp ông xác định tổng số chương trình tối đa mà ông có thể ghi.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, mỗi dòng chứa thời điểm bắt đầu và kết thúc của một chương trình; các thời điểm là số nguyên trong đoạn từ \(0\) đến \(1\,000\,000\,000\).

Ràng buộc

• \(1 \le N \le 150\).
• Mỗi thời điểm bắt đầu và kết thúc là một số nguyên trong đoạn từ \(0\) đến \(1\,000\,000\,000\).

Dữ liệu ra

In ra số chương trình tối đa mà FJ có thể ghi.

Ví dụ

6
0 3
6 7
3 10
1 5
2 8
1 9

4

Nguồn

USACO 2014 January Contest, Silver — Recording the Moolympics

Tác giả: Brian Dean, 2014.