Bầu trời là giới hạn
Đề bài
Mô tả
Thành phố Banff thuê một công ty quảng cáo để giới thiệu các điểm tham quan của thành phố tới du khách. Một trong các khẩu hiệu dự kiến nói rằng những dãy núi quanh thành phố tạo nên đường chân trời đẹp nhất Canada. Nhưng Viện Bảo vệ Người tiêu dùng Canada (ICPC) cho rằng "đường chân trời đẹp nhất" là một khẳng định chủ quan, không kiểm chứng được, nên có thể bị coi là gây hiểu lầm.
Công ty quảng cáo bèn nghĩ ra khẩu hiệu "Banff, đường chân trời dài nhất Canada". Dù không hấp dẫn bằng, khẩu hiệu này hy vọng là kiểm chứng được, nên được chấp nhận theo luật quảng cáo khắt khe của Canada.
Đây là lúc bạn xuất hiện. Công ty quảng cáo cần một chương trình tính độ dài của một đường chân trời. Coi mỗi ngọn núi là một tam giác hai chiều có hai cạnh phía trên dài bằng nhau. Đường chân trời là đường viền phía trên của một hay nhiều ngọn núi. Độ dài đường chân trời là tổng độ dài của đường viền đó. Hình bên trái dưới đây vẽ ba ngọn núi. Hình bên phải vẽ đường chân trời (nét đậm) và phần các cạnh trên của các ngọn núi không thuộc đường chân trời (nét đứt). Lưu ý rằng các phần của đường nằm ngang (mặt đất) nằm giữa các ngọn núi không được tính là một phần của đường chân trời.

Ba ngọn núi

Đường chân trời (nét đậm) và phần các cạnh trên của các ngọn núi không thuộc đường chân trời (nét đứt)
Dữ liệu vào
Dữ liệu gồm một hoặc nhiều bộ test, mỗi bộ test mô tả một dãy núi. Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên dương là số ngọn núi trong dãy. Mỗi dòng trong dòng tiếp theo mô tả một ngọn núi bằng ba số nguyên , và : lần lượt là vị trí theo phương ngang của đỉnh núi (so với một điểm mốc cố định), chiều cao của đỉnh núi và độ rộng của chân núi. Chân của mọi ngọn núi nằm trên cùng một đường nằm ngang.
Sau bộ test cuối cùng là một dòng chứa số .
Dữ liệu ra
Với mỗi bộ test, in số thứ tự bộ test (bắt đầu từ ) và độ dài đường chân trời, làm tròn tới số nguyên gần nhất ( được làm tròn lên), theo định dạng của ví dụ. In một dòng trống sau kết quả của mỗi bộ test.
Ràng buộc
- .
- , , .
- Mỗi file có không quá bộ test và tổng trong một file không quá .
- Trong mọi bộ test, độ dài chính xác của đường chân trời cách mọi giá trị ( nguyên) ít nhất .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 100 50 100 3 20 30 35 37 24 29 60 20 13 0 |
Case 1: 141 Case 2: 138 |
Bộ 1: một ngọn núi, mỗi cạnh dài . Bộ 2: dãy núi có cả phần bị che khuất. |
| 2 0 10 20 0 10 20 2 0 100 100 5 10 10 2 0 3 8 8 3 8 2 0 4 6 10 4 6 0 |
Case 1: 28 Case 2: 224 Case 3: 20 Case 4: 20 |
Bộ 1: hai ngọn núi trùng nhau, đường viền chỉ tính một lần: . Bộ 2: ngọn núi nhỏ nằm hoàn toàn bên trong ngọn núi lớn: . Bộ 3: hai ngọn núi chỉ chạm nhau tại chân, mỗi cạnh dài . Bộ 4: đoạn mặt đất giữa hai ngọn núi không được tính. |
Bình luận