Submit solution
Points:
0.96 (partial)
Time limit:
0.38s
Memory limit:
512M
Input:
stdin
Output:
stdout
Suggester:
Problem source:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Những chú bò của bác John rất thích chơi một phiên bản thú vị của trò chơi "Sudoku". Phiên bản này được chơi trên một bảng ~9 \times 9~ gồm các bảng ~3 \times 3~ con, như trò Sudoku thông thường. Phiên bản này của những chú bò, tuy nhiên, chỉ dùng các chữ số nhị phân:
000 000 000
001 000 100
000 000 000
000 110 000
000 111 000
000 000 000
000 000 000
000 000 000
000 000 000
Mục tiêu của Sudoku nhị phân là đảo ít bit nhất có thể sao cho mỗi hàng, mỗi cột và mỗi bảng con ~3 \times 3~ có số lượng chẵn bit ~1~. Trong ví dụ trên, tập hợp ~3~ lần đảo bit cho ta một giải pháp hợp lệ như sau:
000 000 000
001 000 100
001 000 100
000 110 000
000 110 000
000 000 000
000 000 000
000 000 000
000 000 000
Cho trạng thái ban đầu của bảng Sudoku nhị phân, hãy giúp những chú bò tìm số lần đảo bit thấp nhất để có thể giải trò chơi.
Input
- Dòng ~1 \ldots 9~: Mỗi dòng chứa một xâu nhị phân có độ dài là ~9~ thể hiện một dòng trạng thái ban đầu của bảng.
Output
- Dòng ~1~: Số lần đảo bit ít nhất sao cho mỗi hàng, mỗi cột và mỗi bảng con có số lượng chẵn bit ~1~.
Sample Input
000000000
001000100
000000000
000110000
000111000
000000000
000000000
000000000
000000000
Sample Output
3
Comments