BOI 2005 - Ngày 1

Chỉ huy một tiểu đội đang tìm vị trí dựng một khu trại ngụy trang có kích thước cho trước. Bản đồ địa hình số là một lưới chữ nhật; mỗi ô cho biết độ cao tại tọa độ hàng và cột tương ứng.

Khu trại phải là một hình chữ nhật nằm hoàn toàn trong bản đồ và được đánh giá theo một số đặc trưng. Mỗi đặc trưng gồm hai hình chữ nhật bằng nhau, kề nhau và một yêu cầu về độ cao:

• tọa độ hàng, cột của góc trên trái hình chữ nhật thứ nhất (hình bên trái hoặc phía trên), tính tương đối so với khu trại;
• số hàng và số cột của mỗi hình chữ nhật;
• cờ sắp xếp: 0 nếu hai hình nằm ngang và chung cạnh dọc, 1 nếu hai hình nằm dọc và chung cạnh ngang;
• cờ độ cao: 0 nếu độ cao trung bình của hình thứ nhất phải nhỏ hơn nghiêm ngặt độ cao trung bình của hình thứ hai; 1 nếu độ cao trung bình của hình thứ nhất phải lớn hơn hoặc bằng độ cao trung bình của hình thứ hai.

Một vị trí thỏa mãn đặc trưng khi yêu cầu độ cao tương ứng được thỏa mãn. Hãy tìm vị trí khu trại thỏa mãn nhiều đặc trưng nhất. Nếu có nhiều vị trí như vậy, được phép in ra bất kỳ vị trí nào.

Hình trên là bản đồ địa hình \(5 \times 6\) và một khu trại kích thước \(3 \times 5\) đặt tại vị trí \((3,2)\).

Trong hình bên trái, đặc trưng có vị trí \((1,1)\), kích thước \((1,3)\), cờ sắp xếp 1 và cờ độ cao 0; vị trí khu trại đã chọn thỏa mãn đặc trưng này. Trong hình bên phải, các giá trị tương ứng là \((2,2)\), \((2,2)\), 0 và 0; vị trí đã chọn không thỏa mãn đặc trưng.

Dữ liệu vào

Dòng đầu gồm hai số nguyên \(R, C\) (\(2 \le R,C \le 1000\)), là số hàng và số cột của bản đồ. Mỗi dòng trong \(R\) dòng tiếp theo gồm \(C\) số nguyên không âm mô tả độ cao; mọi độ cao không vượt quá \(255\).

Dòng tiếp theo gồm hai số nguyên \(L, W\) (\(1 \le L,W \le 1000\), \(L \le R\), \(W \le C\)), là số hàng và số cột của khu trại.

Dòng tiếp theo chứa \(H\) (\(1 \le H \le 1000\)), số đặc trưng. Mỗi dòng trong \(H\) dòng cuối gồm sáu số nguyên: hàng và cột của góc trên trái, số hàng và số cột của hình chữ nhật thứ nhất, cờ sắp xếp và cờ độ cao. Mọi đặc trưng đều nằm hoàn toàn trong khu trại.

Dữ liệu ra

In hai số nguyên là hàng và cột của góc trên trái một vị trí khu trại tối ưu.

Ví dụ

5 6
2 2 2 2 2 2
2 6 6 4 3 2
3 5 8 7 7 4
4 6 8 9 8 6
5 7 8 8 8 7
3 5
3
1 1 1 3 1 0
2 2 2 2 0 0
2 4 1 1 1 1

3 1

Trong ngôn ngữ lập trình LISP, mọi thứ được viết bên trong các cặp ngoặc cân bằng. Vì vậy mã LISP đôi khi có những đoạn rất dài chỉ gồm dấu ngoặc đóng ), và việc viết đúng số lượng dấu ngoặc này khá phiền toái.

Để tránh lỗi cú pháp, một số phương ngữ LISP có dấu ngoặc đóng ma thuật ], thay cho một hoặc nhiều dấu ) sao cho các dấu ( được cân bằng đúng. Hãy xác định số dấu ) mà mỗi dấu ] thay thế. Nếu có nhiều đáp án, được phép in bất kỳ đáp án nào.

Dữ liệu vào

Dòng đầu gồm hai số nguyên \(N, M\) (\(0 \le N \le 10\,000\,000\), \(0 \le M \le 5\,000\,000\)), lần lượt là độ dài xâu và số dấu ngoặc ma thuật.

Phần còn lại của tệp, bắt đầu từ dòng thứ hai, là một xâu dài \(N\) chỉ gồm (, ) và ]; ký tự ] xuất hiện đúng \(M\) lần. Để dễ đọc, xâu được chia thành các dòng, mỗi dòng không quá \(72\) ký tự.

Dữ liệu ra

Dòng đầu in 0 hoặc 1.

Nếu không thể cân bằng xâu, in 0 và không in thêm gì.

Nếu có thể cân bằng, in 1, sau đó in thêm đúng \(M\) dòng. Dòng thứ \(i\) chứa số nguyên \(C_i \ge 1\), là số dấu ) mà dấu ] thứ \(i\) trong xâu thay thế.

Ví dụ

8 2
(((((])]

1
3
1

Xét một mê cung tạo bởi các tam giác đều. Mỗi đỉnh được mô tả bởi hai tọa độ \(x,y\) như trong hình. Một số cạnh có một vòng tròn trắng hoặc đen.

Việc di chuyển tuân theo hai quy tắc:

• chỉ được đi qua cạnh có vòng tròn;
• màu các vòng tròn đi qua phải xen kẽ trắng, đen. Ở bước đầu tiên có thể đi qua vòng tròn thuộc một trong hai màu.

Hãy tìm độ dài đường đi ngắn nhất từ lối vào đến lối ra. Độ dài là số cạnh (hay số vòng tròn) đã đi qua. Dữ liệu bảo đảm luôn tồn tại một đường đi như vậy.

Dữ liệu vào

Dòng đầu gồm hai số nguyên \(W,H\) (\(1 \le W,H \le 500\)), là chiều rộng và chiều cao của mê cung.

Dòng thứ hai gồm \(X_1,Y_1,X_2,Y_2\) (\(0 \le X_1,X_2 \le W\), \(0 \le Y_1,Y_2 \le H\)). \((X_1,Y_1)\) là lối vào và \((X_2,Y_2)\) là lối ra.

\(2H+1\) dòng tiếp theo mô tả các cạnh. Các dòng lẻ trong phần này mô tả cạnh nằm ngang và có đúng \(W\) ký tự; các dòng chẵn mô tả cạnh không nằm ngang và có đúng \(2W+1\) ký tự. Không có khoảng trắng giữa các ký tự. Ký tự n nghĩa là cạnh không có vòng tròn, w là vòng tròn trắng và b là vòng tròn đen.

Dữ liệu ra

In một số nguyên duy nhất: độ dài đường đi ngắn nhất từ lối vào đến lối ra.

Ví dụ

2 1
0 0 2 1
bb
nwwnw
bn

6

5 4
0 2 5 2
nnbnn
nnnwwbwnnnn
nbbbn
nnwbwwbwwnn
bwwww
nnbwbbwwbnn
nwwwn
nnnnbwbbnnn
nnwnn

22