Board Trick

시간 제한2초메모리 제한512 MB

요약

8x8 이진 표에서 한 칸만 뒤집어 1부터 64까지의 비밀 수를 마술사에게 전달하는 전략을 설계한다.

난이도: 보통10점 중 7점
유형: 비트 연산, 수학, 조합론
정답자: 아직 제출이 없습니다

문제

Danila the Magician and Mia the Assistant are showing a trick with a board.

First, Danila secludes himself, while Mia asks the audience to fill the $8 \times 8$ square table drawn on the board: each cell can contain either zero or one.

Next, another member of the audience chooses the secret number: an integer from $1$ to $64$ . The number is announced to Mia but not to Danila.

After that, Mia comes to the board and changes exactly one number on it: either a zero into one, or a one into zero.

Finally, Danila returns, looks at the board for a while, and happily announces the secret number he did not know.

How do they perform the trick? Help Danila and Mia to prepare and then show it.

예제2

예제 1

입력

Mia
2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1
0 1 1 0 1 0 0 1
1 0 0 1 0 1 1 0
1 0 0 1 0 1 1 0
0 1 1 0 1 0 0 1
0 1 1 0 1 0 0 1
1 0 0 1 0 1 1 0
1 0 0 1 0 1 1 0
0 1 1 0 1 0 0 1
31

예상 출력

1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
---
0 0 1 0 1 0 0 1
1 0 0 1 0 1 1 0
1 0 0 1 0 1 1 0
0 1 1 0 1 0 0 1
0 1 1 0 1 0 0 1
1 0 0 1 0 1 1 0
1 0 0 1 0 1 1 0
0 1 1 0 1 0 0 1
---

예제 2

입력

Danila
2
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
---
0 0 1 0 1 0 0 1
1 0 0 1 0 1 1 0
1 0 0 1 0 1 1 0
0 1 1 0 1 0 0 1
0 1 1 0 1 0 0 1
1 0 0 1 0 1 1 0
1 0 0 1 0 1 1 0
0 1 1 0 1 0 0 1
---

예상 출력

1
31