Nhảy mái nhà bắt tội phạm
Đề bài
Mô tả
Bạn của bạn, Robin, là một siêu anh hùng. Khi mới biết chuyện này, bạn nghĩ "ai mà chẳng cần một sở thích, và việc này nghe còn thú vị hơn sưu tầm tem", nhưng giờ bạn thật sự biết ơn vì có người đang làm gì đó với tình trạng tội phạm ở thành phố quê hương bạn.
Mỗi đêm, Robin tuần tra thành phố bằng cách nhảy từ mái nhà này sang mái nhà khác và quan sát những gì diễn ra bên dưới. Dĩ nhiên siêu anh hùng cần phản ứng ngay lập tức với mọi sự cố, nên Robin nhờ bạn giúp tìm cách di chuyển nhanh trong thành phố.
Thành phố được xây trên một lưới ô vuông, mỗi ô (khu nhà) có kích thước mét. Mỗi ô được lấp đầy bởi đúng một tòa nhà. Các tòa nhà có thể có chiều cao khác nhau (xem hình dưới). Để đi từ một tòa nhà tới một tòa nhà khác (không nhất thiết kề nhau), Robin thực hiện một cú nhảy duy nhất từ tâm mái của tòa nhà thứ nhất tới tâm mái của tòa nhà thứ hai. Robin không thể đổi hướng khi đang ở trên không, nhưng có thể chọn góc bật nhảy.

Hình: mặt cắt các tòa nhà ứng với ví dụ thứ nhất (trục ngang: khoảng cách theo mét, trục đứng: độ cao theo mét). Các tòa nhà vẽ bằng nét đen, cú nhảy từ mái nhà tới mái nhà vẽ bằng nét xanh lá.
Tất nhiên Robin chỉ muốn thực hiện những cú nhảy không va vào tòa nhà nào. Va chạm như vậy chẳng gây hại gì mấy cho một siêu anh hùng, nhưng chủ các tòa nhà thường khó chịu khi có người lao xuyên qua cửa sổ nhà mình. Bạn giải thích phần vật lý cho Robin: "Mọi cú nhảy của cậu đều có cùng vận tốc ban đầu , gồm thành phần ngang hướng về đích và thành phần đứng hướng lên trên, sao cho . Trong khi bay, vận tốc ngang không đổi (), còn vận tốc đứng chịu tác dụng của trọng lực (), với m/s² ở thành phố của bạn. Đương nhiên chiếc áo choàng giúp cậu bỏ qua sức cản không khí. Từ đó có thể xác định quỹ đạo bay và ..." đến đây thì bạn nhận ra Robin đã ngủ gật: bớt toán đi, làm siêu anh hùng nhiều hơn!
Vậy việc này đến tay bạn: cho bản đồ thành phố và vị trí căn cứ bí mật của Robin, hãy xác định Robin có thể tới được những mái nhà nào, và số cú nhảy ít nhất để tới mỗi mái nhà.
Lưu ý rằng nếu cú nhảy của Robin bay qua một góc của các tòa nhà (nơi bốn tòa nhà gặp nhau), thì cú nhảy phải cao hơn cả bốn tòa nhà kề góc đó.
Dữ liệu vào
Dòng đầu tiên chứa sáu số nguyên , , , , , : kích thước lưới thành phố (tính theo số khu nhà), chiều rộng (mét) của mỗi tòa nhà, vận tốc bật nhảy (mét/giây) của Robin, và tọa độ của căn cứ bí mật.
Tiếp theo là chiều cao các tòa nhà, gồm dòng, mỗi dòng chứa số nguyên không âm. Dòng thứ chứa chiều cao của các tòa nhà . Mọi chiều cao tính bằng mét.
Dữ liệu ra
In ra số cú nhảy ít nhất Robin cần để đi từ căn cứ bí mật tới mái của mỗi tòa nhà. Nếu không có cách nào tới được mái một tòa nhà, in X thay cho số cú nhảy. In các tòa nhà theo đúng thứ tự như trong dữ liệu vào, gồm dòng, mỗi dòng giá trị.
Dữ liệu đảm bảo rằng thay đổi chiều cao của bất kỳ tòa nhà nào đi không quá mét sẽ không làm thay đổi đáp án.
Ràng buộc
- .
- , .
- , .
- Chiều cao mỗi tòa nhà là số nguyên trong đoạn .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 1 100 55 1 1 10 40 60 10 |
0 1 1 1 | Đây là thành phố trong hình: từ mái nhà Robin nhảy thẳng một lần tới được mỗi mái nhà còn lại, kể cả mái nhà (cú nhảy vượt qua hai tòa nhà cao và mét). |
| 4 4 100 55 1 1 0 10 20 30 10 20 30 40 20 30 200 50 30 40 50 60 |
0 1 1 2 1 1 1 2 1 1 X 2 2 2 2 3 |
Tòa nhà cao mét, không cú nhảy nào lên tới mái của nó. Mái nhà cần ít nhất cú nhảy. |
Bình luận