SLIKAR - Slikar
English | Vietnamese |
Josip là một họa sĩ kỳ lạ. Anh muốn vẽ một bức tranh gồm N×N điểm ảnh, với N là một lũy thừa của 2 (1, 2, 4, 8, 16 v.v…). Mỗi điểm sẽ có màu đen hoặc màu trắng. Josip đã có một ý tưởng cho việc tô màu mỗi điểm ảnh.
Sẽ chẳng có vấn đề gì nếu như phương pháp tô màu của Josip không kỳ lạ. Anh ấy sử dụng quá trình đệ quy sau:
- Nếu như bức tranh chỉ có một điểm ảnh, anh tô nó theo cách đã dự định.
- Trường hợp còn lại, chia hình vuông thành 4 hình vuông nhỏ hơn và:
- 1. Chọn một trong số 4 hình vuông, tô nó bằng màu trắng.
- 2. Chọn một trong 3 hình vuông còn lại, tô nó màu đen.
- 3. Coi 2 hình vuông còn lại như những bức tranh mới và áp dụng quá trình trên với chúng.
Josip nhanh chóng thấy rằng không thể nào chuyển tải hết được ý tưởng của mình vào các bức tranh với phương pháp này. Nhiệm vụ của bạn là viết một chương trình tìm cách tô một bức tranh sao cho nó sai khác ít nhất so với bức tranh đã thiết kế sẵn. Sự sai khác giữa hai bức tranh là số cặp điểm ở vị trí tương ứng mà khác màu nhau.
Input
Dòng đầu tiên chứa số nguyên N (1 ≤ N ≤ 512), là kích thước của bức tranh mà Josip muốn vẽ. N là một lũy thừa của 2.
Mỗi dòng trong số N dòng tiếp theo chứa N chữ số 0 hoặc 1, thể hiện điểm ảnh màu trắng hoặc màu đen trong bức tranh cần vẽ.
Output
Dòng đầu tiên ghi ra số lượng sai khác nhỏ nhất tìm được.
Trên N dòng tiếp theo, in ra bức tranh có thể tô được theo phương pháp của Josip's mà có ít sai khác nhất so với bức tranh cần vẽ. Bức tranh phải được in ra theo cùng định dạng như trong input.
Lưu ý: Phần thứ 2 của output (bức tranh) có thể không duy nhất. Bất kỳ output đúng nào đều được chấp nhận.
Example
Input: 8 01010001 10100011 01010111 10101111 01010111 10100011 01010001 10100000 Output: 16 00000001 00000011 00000111 00001111 11110111 11110011 11110001 11110000
Added by: | Race with time |
Date: | 2009-01-18 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | COCI 2008/2009 |