Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

RBULL - VOI 2016 - Trại bò tót

Ông Bảo là chủ của một trang trại, đang nuôi một đàn bò trên khu đất hình chữ nhật chia thành lưới mxn ô vuông đơn vị. Các hàng của lưới được đánh số từ 1 tới m từ trên xuống, và các cột của lưới được đánh số từ 1 tới n từ trái qua phải. Ô nằm trên giao điểm của hàng i và cột j được gọi là ô (i, j). Tại tâm của một số ô đã cắm cọc, mỗi cọc để buộc một con bò. Để bảo vệ đàn bò tót quý của mình khỏi những tên trộm, ông Bảo thuê Hùng tìm một thửa đất có dạng hình thoi (mà theo quan niệm của ông Bảo là biểu tượng cho may mắn) trong khu đất để nhốt đàn bò của mình. Thửa đất hình thoi có tâm tại ô (x0, y0) và bán kính là r là tập hợp tất cả các ô có tọa độ (x, y) thỏa mãn |x – x0| + |y – y0| <= r. Do bò tót là các con vật rất hung dữ, nên ông Bảo yêu cầu trong thửa đất tìm được không có hai ô có cọc nào lại có cạnh chung.

Yêu cầu: Giúp Hùng xác định thửa đất có dạng hình thoi nằm trọng vẹn trong khu đất với số cọc cột bò là nhiều nhất đáp ứng yêu cầu của ông Bảo.

Dữ liệu:

-        Dòng đầu tiên chứa 2 số nguyên m và n xác định kích thước của khu đất của ông Bảo.

-        Dòng  thứ i trong m dòng sau chứa n kí tự liền nhau, mỗi kí tự xác định trạng thái của một thửa đất: ‘*’ nếu ô đất có cắm cọc và ‘.’ nếu ô đất đó không cắm cọc.

Kết quả: Đưa ra 4 số nguyên S, x0, y0, r được ghi cách nhau một dấu cách, trong đó: S là tổng số cọc trong thửa đất được chọn; x0, y0 là tọa độ tâm và r là bán kính của thửa đất đó. Nếu có nhiều lời giải hãy đưa ra một lời giải bất kỳ.

Ví dụ:

INPUT

OUTPUT

2 3

...

..*

1 2 3 0

3 3

*.*

...

*.*

1 1 1 0

3 3

.*.

*.*

.*.

4 2 2 1

 

Ràng buộc:

-        Có 40% số test ứng với 40% số điểm của bài có 1 <= m,n <= 100

-        Có 40% số test khác ứng với 40% số điểm của bài có 1 <= m,n <= 500

-        Có 20% số test còn lại ứng với 20% số điểm của bài có 1 <= m,n <= 1000


Được gửi lên bởi:Le Anh Duc - A2K42 PBC
Ngày:2016-01-08
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:VOI 2016 Day 2, task 4 - unofficial testdata

hide comments
2018-12-05 18:17:51
Sử dụng QHĐ bth
chuyên LTV vô địch :D
Tham khảo: https://ideone.com/MDRJgQ

Last edit: 2018-12-05 18:27:08
2018-12-05 18:08:21
Trình chấm CPP14 nộp lên sẽ ko full, C++ full ?? hong hiểu ??


Last edit: 2018-12-05 18:15:31
2016-09-04 10:45:36
http://vn.spoj.com/problems/RBULL/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.