JOI 2012 Final Camp - Ngày 2

Quốc gia JOI sắp bắt đầu phát sóng truyền hình. Trong nước có \(N\) ngôi nhà, và cần xây các tháp phát sóng để mọi ngôi nhà đều xem được truyền hình.

Nhà vua quyết định xây đúng \(K\) tháp. Nếu tháp thứ \(i\) được đặt tại tọa độ \((X_i,Y_i)\) và có mức công suất \(E_i\), mọi ngôi nhà cách tháp không quá \(\sqrt{E_i}\) đều nhận được tín hiệu của tháp đó. Khoảng cách giữa hai điểm \((a,b)\) và \((c,d)\) là

Tháp có mức công suất \(E_i\) tiêu thụ \(E_i\) đơn vị năng lượng. Mục tiêu là phủ sóng tất cả các ngôi nhà và làm tổng năng lượng tiêu thụ của \(K\) tháp nhỏ nhất có thể. Được phép xây tháp ngay tại vị trí của một ngôi nhà và đặt nhiều tháp tại cùng một tọa độ.

Yêu cầu

Đây là bài chỉ nộp kết quả (output-only). Bạn được cung cấp các bộ dữ liệu chứa tọa độ các ngôi nhà và số tháp cần xây. Với mỗi bộ dữ liệu, hãy tạo và nộp kết quả mô tả vị trí, mức công suất của các tháp. Năng lượng tiêu thụ càng ít thì điểm càng cao.

Dữ liệu vào

Có \(5\) bộ dữ liệu được cung cấp trong tệp đính kèm của bài toán. Các tệp dữ liệu vào là:

• 01.txt: \(N=200\), \(K=20\).
• 02.txt: \(N=500\), \(K=10\).
• 03.txt: \(N=500\), \(K=20\).
• 04.txt: \(N=500\), \(K=15\).
• 05.txt: \(N=500\), \(K=30\).

Mỗi tệp đầu vào có định dạng:

• Dòng đầu chứa hai số nguyên \(N,K\) cách nhau bởi dấu cách, lần lượt là số ngôi nhà và số tháp cần xây.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(A_i,B_i\) cách nhau bởi dấu cách, là tọa độ ngôi nhà thứ \(i\).

Không có hai ngôi nhà trùng tọa độ.

Dữ liệu ra

Với mỗi bộ dữ liệu, chuẩn bị một kết quả gồm đúng \(K\) dòng. Dòng thứ \(i\) (\(1\le i\le K\)) chứa ba số nguyên \(X_i,Y_i,E_i\) cách nhau bởi dấu cách, mô tả tọa độ và mức công suất của tháp thứ \(i\).

Kết quả hợp lệ phải tuân thủ các giới hạn bên dưới và phủ sóng tất cả các ngôi nhà. Cụ thể, với mỗi ngôi nhà thứ \(j\), phải tồn tại ít nhất một tháp thứ \(i\) sao cho

Ràng buộc

• \(1\le N\le500\).
• \(1\le K\le30\).
• \(0\le A_i,B_i\le1\,000\,000\) với \(1\le i\le N\).
• \(0\le X_i,Y_i\le1\,000\,000\) với \(1\le i\le K\).
• \(0\le E_i\le1\,000\,000\,000\,000=10^{12}\) với \(1\le i\le K\).
• Tất cả các giá trị trong tệp đầu vào và kết quả đều phải là số nguyên.

Cách nộp bài

Nộp kết quả tương ứng với từng bộ dữ liệu đầu vào. Khi nộp, hệ thống kiểm tra kết quả có khớp với định dạng quy định trong phần Dữ liệu ra hay không; phản hồi lúc nộp chỉ là kiểm tra định dạng. Thí sinh không cần nộp chương trình tạo kết quả.

Chấm điểm

Mỗi bộ dữ liệu có tối đa \(20\) điểm; tổng điểm của \(5\) bộ dữ liệu là \(100\) điểm. Điểm cho từng bộ dữ liệu được tính riêng như sau.

Gọi \(E_0\) là tổng năng lượng tiêu thụ nhỏ nhất trong các kết quả do các thí sinh nộp cho bộ dữ liệu đó. Nếu kết quả của bạn không thỏa mãn các điều kiện của bài toán, bạn nhận \(0\) điểm cho bộ dữ liệu này. Nếu kết quả hợp lệ, gọi tổng năng lượng tiêu thụ của bạn là

• Nếu \(E/E_0>1.5\), bạn nhận \(0\) điểm.
• Nếu \(E/E_0\le1.5\), điểm của bạn là giá trị sau được làm tròn đến số nguyên gần nhất, xét chữ số đầu tiên sau dấu thập phân (từ \(5\) trở lên thì làm tròn lên):

Ví dụ

10 3
0 300000
500000 800000
700000 200000
100000 500000
400000 900000
200000 1000000
300000 500000
300000 200000
500000 100000
1000000 0

200000 700000 160000000000
300000 300000 90000000000
750000 0 62500000000

JOI rất thích quan sát bầu trời đêm. Gần như mỗi tối, cậu đều ngắm sao và tìm hiểu mỗi ngôi sao thuộc chòm sao nào.

Một tối nọ, JOI phát hiện \(N\) ngôi sao mà cậu chưa từng thấy. Cậu chụp ảnh bầu trời rồi đến thư viện tìm hiểu vào ngày hôm sau. JOI biết rằng tất cả các ngôi sao này đều thuộc một trong hai chòm sao \(A\) và \(B\), đồng thời xác định được chòm sao của một số ngôi sao. Với những ngôi sao còn lại, cậu chưa biết chúng thuộc chòm sao nào.

Có thể coi mỗi ngôi sao là một điểm trên ảnh. Một chòm sao gồm ít nhất một ngôi sao cùng một số đoạn thẳng nối các cặp sao của chòm sao đó, sao cho:

• Từ bất kỳ ngôi sao nào của một chòm sao, có thể đi đến bất kỳ ngôi sao nào khác của cùng chòm sao bằng cách đi theo các đoạn thẳng của chòm sao đó.
• Một đoạn thẳng của chòm sao này không được giao với một đoạn thẳng của chòm sao kia.

Một ngôi sao đứng riêng cũng được coi là một chòm sao. Không có ba ngôi sao nào thẳng hàng trên ảnh. Mỗi ngôi sao trong \(N\) ngôi sao thuộc đúng một trong hai chòm sao \(A\) và \(B\), và hai chòm sao này không chứa ngôi sao nào khác ngoài \(N\) ngôi sao đã cho.

Yêu cầu

Hãy tính số cách chọn hai tập hợp sao tạo thành chòm sao \(A\) và chòm sao \(B\), phù hợp với những thông tin đã biết và có thể nối các sao để thỏa mãn các điều kiện trên. Cả hai chòm sao đều phải không rỗng. Chỉ phân biệt các cách theo tập hợp sao của mỗi chòm sao; các cách vẽ đoạn thẳng khác nhau trên cùng hai tập hợp chỉ được tính một lần. In ra phần dư của số cách khi chia cho \(1\,000\,000\,007=10^9+7\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(N\), là số ngôi sao JOI phát hiện.
• Dòng thứ \(i+1\) (\(1\le i\le N\)) chứa ba số nguyên \(X_i,Y_i,C_i\) cách nhau bởi dấu cách. \((X_i,Y_i)\) là tọa độ ngôi sao thứ \(i\) trên ảnh.

Giá trị \(C_i\) có ý nghĩa như sau:

• \(C_i=0\): chưa biết ngôi sao thứ \(i\) thuộc chòm sao nào.
• \(C_i=1\): ngôi sao thứ \(i\) thuộc chòm sao \(A\).
• \(C_i=2\): ngôi sao thứ \(i\) thuộc chòm sao \(B\).

Dữ liệu ra

In ra trên một dòng phần dư của số cách chọn hai tập hợp sao khi chia cho \(1\,000\,000\,007\). Nếu không có cách nào thỏa mãn, in ra 0.

Ràng buộc

• \(2\le N\le100\,000\).
• \(0\le X_i\le10^9\) và \(0\le Y_i\le10^9\) với \(1\le i\le N\).
• \(C_i\in\{0,1,2\}\) với \(1\le i\le N\).
• Không có ba ngôi sao nào nằm trên cùng một đường thẳng.
• Mọi giá trị trong đầu vào đều là số nguyên.

Phân nhóm

• Các bộ dữ liệu chiếm \(10\%\) tổng số điểm thỏa mãn \(N\le10\).
• Các bộ dữ liệu chiếm \(50\%\) tổng số điểm thỏa mãn \(N\le300\).

Ví dụ

4
1 1 1
2 1 1
1 2 0
2 2 2

2

Có một bảng gồm \(N\times N\) ô vuông, xếp thành \(N\) hàng và \(N\) cột. Ô ở hàng thứ \(i\) từ trên xuống và cột thứ \(j\) từ trái sang được gọi là ô \((i,j)\). Ban đầu, ô \((i,j)\) chứa ký tự \(A_{ij}\).

Thực hiện lần lượt \(Q\) thao tác. Ở thao tác thứ \(k\), quay vùng vuông gồm \(S_k\times S_k\) ô, có ô trên cùng bên trái là \((I_k,J_k)\), một góc \(90^\circ\) ngược chiều kim đồng hồ.

Yêu cầu

Hãy xác định và in ra bảng sau khi thực hiện tất cả các thao tác.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(N,Q\) cách nhau bởi dấu cách, lần lượt là kích thước bảng và số thao tác quay.
• \(N\) dòng tiếp theo mô tả bảng ban đầu. Dòng thứ \(i\) chứa một chuỗi dài \(N\), chỉ gồm các chữ cái tiếng Anh viết thường; ký tự thứ \(j\) của chuỗi là \(A_{ij}\).
• \(Q\) dòng tiếp theo mô tả các thao tác theo thứ tự thực hiện. Dòng thứ \(k\) chứa ba số nguyên \(I_k,J_k,S_k\) cách nhau bởi dấu cách, xác định vùng vuông được quay trong thao tác thứ \(k\).

Dữ liệu ra

In ra đầu ra chuẩn \(N\) dòng mô tả bảng cuối cùng. Dòng thứ \(i\) là một chuỗi dài \(N\), có ký tự thứ \(j\) bằng ký tự trong ô \((i,j)\) sau tất cả các thao tác.

Ràng buộc

• \(2\le N\le1\,000\).
• \(1\le Q\le2\,000\).
• \(2\le S_k\le N\) với \(1\le k\le Q\).
• \(1\le I_k\le N-S_k+1\) và \(1\le J_k\le N-S_k+1\) với \(1\le k\le Q\).
• Mỗi \(A_{ij}\) là một chữ cái tiếng Anh viết thường.
• \(N,Q,I_k,J_k,S_k\) đều là số nguyên.

Phân nhóm

• Các bộ dữ liệu chiếm \(10\%\) tổng số điểm thỏa mãn đồng thời \(N\le100\) và \(Q\le100\).

Ví dụ

4 1
abcd
efgh
ijkl
mnop
2 2 2

abcd
egkh
ifjl
mnop

abcd
efgh
ijkl
mnop

fg
jk

abcd
egkh
ifjl
mnop