Máy sinh địa hình
Đề bài
Mô tả
Interactive Creative Players Collective (ICPC) đang phát triển một trò chơi máy tính mới và muốn sinh ra các địa hình trông thật tự nhiên. Một kỹ sư của ICPC đề xuất một thuật toán lấy cảm hứng từ các quá trình địa chất. Thuật toán bắt đầu từ một địa hình phẳng rồi liên tục biến đổi nó bằng cách nâng lên hoặc hạ xuống các khối liền nhau, tạo thành các địa lũy (khối được nâng lên) và địa hào (khối bị hạ xuống). Các khối được nâng hoặc hạ được chọn ngẫu nhiên. ICPC hy vọng cách này sẽ cho ra những địa hình giống thật.
Nhiệm vụ của bạn là thực hiện một dãy biến đổi bất kỳ như vậy và in ra địa hình thu được. Địa hình được biểu diễn bởi một dãy độ cao nguyên, mỗi độ cao ứng với một điểm nguyên từ tới trên trục hoành. Hình 1 minh họa một ví dụ bằng cách nối các độ cao bằng các đoạn thẳng.

Hình 1: Địa hình sinh ra bởi ví dụ 1.
Ban đầu độ cao bằng tại cả điểm. Địa hình phẳng này lần lượt chịu một dãy biến đổi. Mỗi biến đổi là một trong bốn thao tác sau, với hai tham số nguyên :
R(Raise, nâng): tăng độ cao thêm tại mọi điểm từ tới (tính cả hai đầu).D(Depress, hạ): giảm độ cao đi tại mọi điểm từ tới (tính cả hai đầu).H(Hill, đồi): thêm một ngọn đồi hình tuyến tính trong đoạn từ tới .V(Valley, thung lũng): thêm một thung lũng hình tuyến tính trong đoạn từ tới .
Thêm một ngọn đồi vào địa hình hiện tại được thực hiện như sau. Độ cao tại các điểm và được tăng thêm . Nếu , độ cao tại các điểm và được tăng thêm . Nếu , độ cao tại các điểm và được tăng thêm , và cứ thế tiếp tục. Hình 2 là một ví dụ. Thêm một thung lũng được thực hiện theo cùng cách, chỉ khác là độ cao bị giảm đi thay vì được tăng lên. Mức thay đổi độ cao lớn nhất xảy ra ở chính giữa và . Nếu lẻ thì có hai điểm kề nhau cùng có mức thay đổi lớn nhất, ngược lại chỉ có một điểm.

Hình 2: Địa hình sinh ra bởi ví dụ 2.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và : là số điểm và là số biến đổi. Các điểm trên trục hoành được đánh số từ tới .
Mỗi dòng trong dòng tiếp theo mô tả một biến đổi, gồm một ký tự và hai số nguyên , : (một trong các ký tự R, D, H, V) cho biết thao tác, còn và là các tham số của thao tác.
Dữ liệu ra
In ra dòng, dòng thứ chứa độ cao tại điểm sau khi thực hiện tất cả các biến đổi theo thứ tự đã cho.
Ràng buộc
- , .
R,D,H,V, .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 20 13 H 12 13 D 5 18 R 13 14 R 8 16 H 2 3 V 10 19 V 3 13 R 8 13 V 3 10 D 5 18 V 11 12 R 1 6 R 14 19 |
1 2 0 -3 -7 -9 -11 -9 -7 -6 -6 -5 -3 -4 -5 -4 -4 -3 0 0 |
Địa hình thu được là Hình 1. |
| 7 1 H 1 6 |
1 2 3 3 2 1 0 |
Ngọn đồi trên đoạn : lẻ nên hai điểm và cùng cao nhất (). Điểm nằm ngoài đoạn nên vẫn cao (Hình 2). |
Bình luận