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

Thuyền trưởng Bovidian đang phiêu lưu để giải cứu thành viên trong thủy thủ đoàn của mình, Tiến sĩ Beefalo. Giống như mọi cuộc phiêu lưu vĩ đại, câu chuyện này diễn ra trên một lưới hai chiều \(N \times M\) (\(1 \le N, M \le 500\)), biểu diễn góc nhìn từ bên hông thế giới của thuyền trưởng. Một số ô lưới trống, còn những ô khác bị chặn và không thể đi qua.

Không may, Thuyền trưởng Bovidian không thể nhảy. Cô phải tuân theo các quy luật vật lý sau khi di chuyển trong thế giới của mình:

1. Nếu không có ô nào ngay bên dưới Thuyền trưởng Bovidian (nghĩa là nếu cô đang ở mép lưới), cô sẽ bay ra ngoài không gian và thất bại trong nhiệm vụ.
2. Nếu ô ngay bên dưới Thuyền trưởng Bovidian trống, cô sẽ rơi vào ô đó.
3. Nếu không:
   • a) Thuyền trưởng Bovidian có thể di chuyển sang trái hoặc sang phải nếu ô tương ứng tồn tại và trống.
   • b) Hoặc Thuyền trưởng Bovidian có thể đảo chiều trọng lực.

Khi Thuyền trưởng Bovidian đổi chiều trọng lực, ô “bên dưới” cô (như được nhắc đến trong quy tắc 1 và 2) chuyển đổi qua lại giữa ô có chỉ số hàng lớn hơn một và ô có chỉ số hàng nhỏ hơn một (hàng đầu tiên trong dữ liệu vào có chỉ số 1 và hàng cuối cùng có chỉ số \(N\)). Ban đầu, các ô có chỉ số hàng lớn hơn một nằm bên dưới Thuyền trưởng Bovidian.

Tiến sĩ Beefalo bị lạc đâu đó trong thế giới này. Hãy giúp Thuyền trưởng Bovidian đến ô của cô ấy với số lần đảo chiều trọng lực ít nhất có thể. Nếu không thể đến được chỗ Tiến sĩ Beefalo, hãy in ra -1.

Dữ liệu vào

• Dòng 1 chứa hai số nguyên \(N\) và \(M\), cách nhau bởi một dấu cách.
• Các dòng từ 2 đến \(1+N\): dòng \(i+1\) mô tả hàng thứ \(i\) trong thế giới của Thuyền trưởng Bovidian; . biểu thị một ô trống, # biểu thị một ô bị chặn, C biểu thị vị trí ban đầu của Thuyền trưởng Bovidian và D biểu thị vị trí ban đầu của Tiến sĩ Beefalo.

Dữ liệu ra

• Dòng 1 chứa một số nguyên duy nhất là số lần ít nhất Thuyền trưởng Bovidian phải đảo chiều trọng lực để đến chỗ Tiến sĩ Beefalo, hoặc -1 nếu không thể đến chỗ Tiến sĩ Beefalo.

Ví dụ

5 5
#####
#...#
#...D
#C...
##.##

3

Nguồn

USACO 2013 US Open, Silver — Problem 1: What's Up With Gravity

Tác giả đề: Mark Gordon, 2013.

Farmer John đã quyết định thực hiện một chuyến nghỉ dưỡng xuyên quốc gia. Tuy nhiên, vì không muốn những cô bò cảm thấy bị bỏ lại, ông đã quyết định thuê một chiếc xe tải lớn và đưa cả đàn bò đi cùng!

Chiếc xe tải có một bình nhiên liệu lớn chứa được tối đa \(G\) đơn vị nhiên liệu (\(1 \le G \le 1\,000\,000\)). Không may, xe tiêu thụ nhiên liệu rất tốn: cứ đi một đơn vị khoảng cách thì tiêu thụ một đơn vị nhiên liệu, và FJ phải đi tổng cộng \(D\) đơn vị khoảng cách trên hành trình của mình (\(1 \le D \le 1\,000\,000\,000\)).

Vì biết rằng có lẽ sẽ phải dừng lại đổ đầy bình vài lần trong chuyến đi, FJ lập danh sách tất cả \(N\) trạm nhiên liệu dọc đường (\(1 \le N \le 50\,000\)). Với mỗi trạm \(i\), ông ghi lại khoảng cách \(X_i\) từ điểm đầu hành trình đến trạm (\(0 \le X_i \le D\)), cũng như giá \(Y_i\) cho mỗi đơn vị nhiên liệu mà trạm bán (\(1 \le Y_i \le 1\,000\,000\)).

Cho các thông tin này và biết rằng FJ bắt đầu hành trình với đúng \(B\) đơn vị nhiên liệu (\(0 \le B \le D\)), hãy xác định số tiền ít nhất FJ cần trả cho nhiên liệu để đến đích. Nếu ông không thể đến đích, hãy in ra -1. Lưu ý rằng đáp án của bài toán này có thể không vừa trong một số nguyên 32 bit tiêu chuẩn.

Dữ liệu vào

• Dòng 1 chứa bốn số nguyên \(N\), \(G\), \(B\) và \(D\), cách nhau bởi dấu cách.
• Các dòng từ 2 đến \(1+N\): mỗi dòng chứa hai số nguyên \(X_i\) và \(Y_i\) mô tả trạm nhiên liệu \(i\).

Dữ liệu ra

• Dòng 1 chứa chi phí ít nhất FJ phải trả để đến đích, hoặc -1 nếu không có cách khả thi nào để ông đến đích.

Ví dụ

4 10 3 17
2 40
9 15
5 7
10 12

174

Nguồn

USACO 2013 US Open, Silver — Problem 2: Fuel Economy

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

Khu du lịch Tam Chúc (Ba Sao Hà Nam) được mệnh danh là “Vịnh Hạ Long trên cạn”, nơi khoác lên mình vẻ đẹp ngút ngàn và đẹp như cõi mộng, nơi mà du khách sẽ cảm nhận được sự thuần khiết, thanh bình và yên ả. Quanh khu du lịch có rất nhiều địa điểm có thể khám phá như: Chùa Ngọc, Điện Tam Thế, Điện Pháp Chủ, Điện Quan Âm, Cổng Tam Quan, Phòng họp Quốc tế,… Giả sử có \(N\) điểm du lịch, tại một điểm bất kì có thể đi đến 2 địa điểm khác theo hướng trái L hoặc hướng phải R). Một tour du lịch cho khách sẽ xuất phát từ điểm 1, đi theo \(M\) chỉ dẫn chỉ gồm các ký tự L và R. Bé Bông lần đầu được đi du lịch ở Tam Chúc nên rất thích, mỗi tour du lịch bé muốn khám phá \(K\) lần. Vậy bạn hãy giúp mẹ bé tìm ra điểm dừng cuối cùng theo lộ trình bé Bông đã đi

Input

• Dòng đầu tiên ghi ba số nguyên dương \(N, M, K\) (\(N \le 10^3, M \le 5 \times 10^2, K \le 10^9\))
• \(N\) dòng tiếp theo, mỗi dòng ghi hai số nguyên là số hiệu của điểm tiếp theo nếu xuất phát từ điểm \(i\) đi theo hướng trái hoặc hướng phải.
• Dòng cuối cùng chứa \(M\) ký tự cách nhau bởi dấu trống chỉ gồm hai ký tự L và R là các chỉ dẫn của tour du lịch

Output

• Một số nguyên duy nhất là số hiệu của điểm dừng cuối cùng.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(K \le 10^2\).
• Subtask \(2\) (\(40\%\) số điểm): \(K \le 10^5\);
• Subtask \(3\) (\(40\%\) số điểm): \(K \le 10^9\).

Example

4 3 3
2 4
3 1
4 2
1 3
L L R

4

4 3 3
2 4
3 1
4 2
1 3
L R R

2