BOI 2010 - Ngày 1

Thành phố Vô Tận được chia thành những ô vuông đơn vị bởi vô số con đường hai chiều chạy theo hướng nam–bắc và tây–đông. Một đường nam–bắc được đánh số \(0\); số đường tăng dần về phía đông và giảm dần về phía tây. Tương tự, một đường tây–đông được đánh số \(0\); số đường tăng dần về phía bắc và giảm dần về phía nam.

Mỗi giao lộ được biểu diễn bằng cặp số có thứ tự của hai con đường đi qua nó, trong đó số thứ nhất là số của đường nam–bắc. Một số đoạn đường quan trọng hơn được gọi là đường chính.

Một hôm, cảnh sát trưởng Wolf, người bảo vệ nghiêm khắc nhất thành phố, đang tuần tra thì phát hiện tại giao lộ \((A,B)\) một chiếc xe chở vài thành viên của băng BEAR khét tiếng. Wolf nghe nói chúng định đột nhập Kho Mật Ong của thành phố nằm gần giao lộ \((0,0)\), nên quyết định ngăn chặn chúng.

Tuy nhiên, chúng chưa phạm tội nên Wolf không thể bắt giữ. Ông có quyền dừng xe tại một giao lộ và chặn đúng một trong bốn đoạn đường đơn vị tiếp giáp giao lộ đó, nhưng không được chặn đoạn thuộc đường chính.

Wolf quyết định đuổi theo băng BEAR. Ngay trước khi xe của chúng tới một giao lộ, ông có thể vượt lên và chặn một trong bốn đoạn đường đơn vị tại đó. Băng BEAR vẫn có thể đi vào giao lộ, nhưng không thể rời giao lộ theo đoạn bị xe cảnh sát chặn.

Wolf muốn giữ băng BEAR cách Kho Mật Ong càng xa càng tốt. Hãy tìm giá trị lớn nhất \(D\) mà ông có thể bảo đảm sao cho mọi giao lộ \((x,y)\) băng BEAR có thể tới đều thỏa mãn

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(A\) và \(B\), là vị trí ban đầu của băng BEAR. Dòng thứ hai chứa số nguyên \(N\), là số đoạn đường chính. Mỗi dòng trong \(N\) dòng tiếp theo chứa bốn số nguyên \(X_1,Y_1,X_2,Y_2\), cho biết đoạn đường nối \((X_1,Y_1)\) với \((X_2,Y_2)\) là đường chính. Mỗi đoạn đều có \(X_1=X_2\) hoặc \(Y_1=Y_2\).

Dữ liệu ra

In một số nguyên là giá trị lớn nhất của \(D\).

Ràng buộc

• \(|A|,|B| \le 10^6\).
• \(0 \le N \le 500\).
• \(|X_i|,|Y_i| \le 10^6\) với \(i \in \{1,2\}\).

Ví dụ

3 3
3
1 0 3 0
0 0 0 3
3 0 3 1

1

Bạn đang dùng các khối Lego để huấn luyện một hệ thống thị giác nhân tạo. Cho hai hình nhìn một mô hình Lego từ hai góc khác nhau, hãy tính số cách xây dựng mô hình đó.

Chỉ có một loại khối Lego với \(2 \times 2\) nút, nhưng có ba màu: trắng (W), xám (G) và đen (B). Số khối mỗi màu là không giới hạn. Bạn dùng một đế vuông có \(6 \times 6\) nút. Các cạnh của mỗi khối phải song song với các cạnh của đế và không khối nào được nhô ra ngoài đế. Mỗi khối đặt phía trên phải tựa lên ít nhất một khối bên dưới.

Hình bên trái là một cách đặt khối lên khối khác hợp lệ. Hình giữa không hợp lệ vì khối phía trên lơ lửng trong không khí. Hình bên phải cũng không hợp lệ vì khối phía trên nhô ra ngoài đế.

Dữ liệu vào

Dòng đầu chứa số nguyên \(H\), là chiều cao của mô hình. Tiếp theo là \(H\) dòng, mỗi dòng có \(6\) ký tự, mô tả hình nhìn từ phía A trong hình minh họa ở ví dụ. Ký tự thứ \(j\) trên dòng thứ \(i\) cho biết những gì nhìn thấy ở cột thứ \(j\) từ trái sang và hàng thứ \(i\) từ trên xuống. Mỗi ký tự là W, G, B hoặc ., lần lượt biểu thị màu trắng, xám, đen hoặc một khoảng trống.

Bạn không thể biết độ sâu từ hình nhìn: màu tại một vị trí có thể thuộc về một khối gần phía trước hoặc xa hơn phía sau, miễn là không có khối khác che khuất tầm nhìn.

Tiếp theo là \(H\) dòng nữa, mô tả hình nhìn khi người quan sát di chuyển quanh mô hình một góc \(90^\circ\) ngược chiều kim đồng hồ, tới phía B trong hình minh họa.

Dữ liệu ra

In một số nguyên là số mô hình Lego khác nhau phù hợp với cả hai hình nhìn. Hai mô hình vẫn được tính riêng ngay cả khi có thể thu được mô hình này bằng cách xoay hoặc lấy đối xứng mô hình kia.

Ràng buộc

• \(1 \le H \le 6\).
• Mỗi dòng của mỗi hình nhìn có đúng \(6\) ký tự thuộc tập W, G, B, ..
• Kết quả luôn biểu diễn được bằng một số nguyên có dấu \(64\) bit.

Ví dụ

2
WWGG..
.BB.WW
.WGG..
WWGG..

6

Trên một bảng mạch in, các dây dẫn được đặt trên một tấm vật liệu cách điện. Hai dây dẫn trong cùng một lớp không thể cắt nhau vì sẽ gây đoản mạch. Vì vậy, với các mạch phức tạp, người ta chia dây dẫn thành nhiều lớp, ngăn cách bởi vật liệu cách điện. Tuy nhiên, bảng mạch càng nhiều lớp thì càng đắt, nên nhà sản xuất muốn bố trí dây dẫn sao cho số lớp cần dùng là ít nhất.

Trong bài này, mỗi dây dẫn nối hai đầu nối nằm trên hai cạnh đối diện của bảng mạch.

Xét bảng mạch ở hình bên trái dưới đây. Nếu một dây nối A với B và dây còn lại nối D với C thì có thể đặt cả hai trong một lớp, như hình giữa. Ngược lại, dây nối A với C và dây nối D với B không thể nằm trong cùng một lớp, như hình bên phải.

Cho vị trí hai đầu của \(N\) dây dẫn trên bảng mạch kích thước \(W \times H\), hãy tìm số lớp ít nhất cần dùng để bố trí tất cả dây dẫn.

Có thể xem bề rộng dây dẫn là rất nhỏ so với khoảng cách giữa các đầu nối. Nói cách khác, giữa hai dây dẫn bất kỳ luôn có đủ chỗ để đặt thêm một dây dẫn nữa.

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\), là số dây dẫn. Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(X_{i1}\) và \(X_{i2}\), cho biết dây dẫn thứ \(i\) phải nối hai điểm \((X_{i1},0)\) và \((X_{i2},H)\).

Tất cả \(2N\) điểm đầu mút trong dữ liệu vào đều phân biệt.

Dữ liệu ra

In một số nguyên là số lớp ít nhất cần dùng để bố trí tất cả dây dẫn.

Ràng buộc

• \(1 \le N \le 10^5\).
• \(0 \le X_{ij} \le 10^6\) với \(1 \le i \le N\) và \(j \in \{1,2\}\).

Ví dụ

2
1 1
3 3

1

2
1 3
3 1

2