trang chủ / đề bài / icpcwf18_e

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 w×w 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à (1,1) tới mái nhà (4,1) 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 v, gồm thành phần ngang vd hướng về đích và thành phần đứng vh hướng lên trên, sao cho vd2+vh2=v2. Trong khi bay, vận tốc ngang không đổi (vd(t)=vd), còn vận tốc đứng chịu tác dụng của trọng lực (vh(t)=vh−t·g), với g=9.80665 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 dx, dy, w, v, ℓx, ℓy: kích thước lưới thành phố dx×dy (tính theo số khu nhà), chiều rộng w (mét) của mỗi tòa nhà, vận tốc bật nhảy v (mét/giây) của Robin, và tọa độ (ℓx,ℓy) của căn cứ bí mật.

Tiếp theo là chiều cao các tòa nhà, gồm dy dòng, mỗi dòng chứa dx số nguyên không âm. Dòng thứ j chứa chiều cao của các tòa nhà (1,j),(2,j),…,(dx,j). 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 dy dòng, mỗi dòng dx 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á 10−6 mét sẽ không làm thay đổi đáp án.

Ràng buộc

  • 1≤dx,dy≤20.
  • 1≤w≤103, 1≤v≤103.
  • 1≤ℓx≤dx, 1≤ℓy≤dy.
  • Chiều cao mỗi tòa nhà là số nguyên trong đoạn [0,103].

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à (1,1) 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à (4,1) (cú nhảy vượt qua hai tòa nhà cao 40 và 60 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à (3,3) cao 200 mét, không cú nhảy nào lên tới mái của nó. Mái nhà (4,4) cần ít nhất 3 cú nhảy.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0