khôngtên
18-11-2002, 19:24
Các bác cao thủ ơi giúp em giải bài này được không !
Phiếu đục lỗ: (Bài thi quốc gia năm 2001)
Có N phiếu đục lỗ hình vuông. Trên mỗi phiếu đục lỗ có K*K hình tròn được bố trí thành K hành ngang, K hàng dọc, mỗi hàng K hình tròn, sao cho nếu tất cả các hình tròn được đục thủng thì vị trí các lỗ đục là trùng nhau khi xếp các phiếu này thành một chồng, cho dù có một phiếu đã xoay 90o, 180o, 270o.
Trên mỗi phiếu có một số hình tròn được đục thủng.
Khi xếp các phiếu thành một chồng, thì trên mỗi cột đều có ít nhất một hình tròn ở cùng một vị trí tạo thành một cột.
Yêu cầu: Hãy hỉ ra một số ít nhất các phiếu cần xoay sao cho nếu xếp chúng thành một chồng, thì trên mỗi cột đều có ít nhất một hình tròn được đục thủng, hoặc cho biết điều này không thể thực hiện được.
Dữ liệu: vào từ file văn bản BL4.INP, có cấu trúc như sau:
Dòng đầu là hai số nguyên N, K (1<=N<=20, 2<=K<=10).
Dòng thứ i trong N dòng tiếp theo chứa K*K số 0, 1 cho biết trạng thái các hình tròn của phiếu thứ i, liệt kê theo hàng ngang, từ trái sang phải và từ trên xuống dưới, trong đó số 1 (0) chỉ ra vị trí tương ứng là lỗ đục (không đục).
Các số trên 1 dòng cách nhau ít nhất 1 dấu cách.
Kết quả:
Dòng đầu tiên chứa số nguyên M là số phiếu cần xoay, M = -1 là không có cách xoay.
Trong trường hợp M>=0 thì dòng thứ 2 chứa N số nguyên R1, R2,…, Rn, với Ri bằng 0, 1, 2, hoặc 3, cho biết bìa thứ i cần xoay Ri*90 theo chiều kim đồng hồ. Nếu có nhiều cách chọn M phiếu để xoay, thì cần nêu một trong số đó.
Ví dụ:
BL4.INP
5 3
1 0 0 0 1 0 0 0 0
0 1 0 1 0 0 0 0 0
1 0 0 0 1 0 0 0 1
0 1 0 0 0 0 1 0 0
1 0 0 1 0 0 0 0 0
BL4.OUT
3
0 0 1 1 3
Cuộc đời mang kiếp "không tên"
Lênh đênh rồi mãi lênh đênh một đời
Phiếu đục lỗ: (Bài thi quốc gia năm 2001)
Có N phiếu đục lỗ hình vuông. Trên mỗi phiếu đục lỗ có K*K hình tròn được bố trí thành K hành ngang, K hàng dọc, mỗi hàng K hình tròn, sao cho nếu tất cả các hình tròn được đục thủng thì vị trí các lỗ đục là trùng nhau khi xếp các phiếu này thành một chồng, cho dù có một phiếu đã xoay 90o, 180o, 270o.
Trên mỗi phiếu có một số hình tròn được đục thủng.
Khi xếp các phiếu thành một chồng, thì trên mỗi cột đều có ít nhất một hình tròn ở cùng một vị trí tạo thành một cột.
Yêu cầu: Hãy hỉ ra một số ít nhất các phiếu cần xoay sao cho nếu xếp chúng thành một chồng, thì trên mỗi cột đều có ít nhất một hình tròn được đục thủng, hoặc cho biết điều này không thể thực hiện được.
Dữ liệu: vào từ file văn bản BL4.INP, có cấu trúc như sau:
Dòng đầu là hai số nguyên N, K (1<=N<=20, 2<=K<=10).
Dòng thứ i trong N dòng tiếp theo chứa K*K số 0, 1 cho biết trạng thái các hình tròn của phiếu thứ i, liệt kê theo hàng ngang, từ trái sang phải và từ trên xuống dưới, trong đó số 1 (0) chỉ ra vị trí tương ứng là lỗ đục (không đục).
Các số trên 1 dòng cách nhau ít nhất 1 dấu cách.
Kết quả:
Dòng đầu tiên chứa số nguyên M là số phiếu cần xoay, M = -1 là không có cách xoay.
Trong trường hợp M>=0 thì dòng thứ 2 chứa N số nguyên R1, R2,…, Rn, với Ri bằng 0, 1, 2, hoặc 3, cho biết bìa thứ i cần xoay Ri*90 theo chiều kim đồng hồ. Nếu có nhiều cách chọn M phiếu để xoay, thì cần nêu một trong số đó.
Ví dụ:
BL4.INP
5 3
1 0 0 0 1 0 0 0 0
0 1 0 1 0 0 0 0 0
1 0 0 0 1 0 0 0 1
0 1 0 0 0 0 1 0 0
1 0 0 1 0 0 0 0 0
BL4.OUT
3
0 0 1 1 3
Cuộc đời mang kiếp "không tên"
Lênh đênh rồi mãi lênh đênh một đời