USACO 2011 - Nov - Gold - Binary Sudoku

View as PDF

Submit solution


Points: 0.96 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
http://www.usaco.org/index.php?page=viewproblem2&cpid=92
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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

Please read the guidelines before commenting.


There are no comments at the moment.