| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 146 | 83 | 59 | 57.282% |
Albert는 2ドル^K \times 2^K$ 크기의 쿠키를 구워 각 칸에 0-9 사이의 숫자를 적어두었다 - 이 문제에서 편의상 $r$ 행 $c$열에 적힌 숫자는 $A[r, c]$로 나타내자 (0ドル \le A[r, c] \le 9$).
예를 들어 아래 그림은 $K = 2$ 이고 $A = [ [1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6], [0, 9, 8, 7]]$ 인 쿠키의 모습을 보여준다.
구워진 쿠키를 감상하던 Bob은 Albert에게 아래와 같은 놀이를 제안했다.
위의 예제의 경우 우선 4ドル \times 4$ 크기의 쿠키를 아래 왼쪽 그림과 같이 4등분 한다.
입력으로 $N = 2^K,ドル 그리고 쿠키에 적힌 숫자를 나타내는 2차원 배열 $A$가 주어졌을 때, 두 어린이가 먹고 남은 쿠키 조각에 적힌 숫자의 총합을 구해보자.
입력의 첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $N$이 주어진다. 다음 $N$줄에 걸쳐 각 줄에 $A$ 배열의 $i$ 번째 행의 $N$개의 숫자가 공백없이 주어진다.
각 테스트 케이스의 정답을 각 줄에 출력한다.
3 2 20 24 4 1212 1212 1111 1122 4 1234 2345 3456 0987
6 14 38
예제 1: 이 경우 쿠키에 적힌 숫자의 총합이 8이므로 좌측 상단의 0번 쿠키 조각 ($A[1, 1]$)을 먹는다. 남은 쿠키 조각에 적힌 숫자는 0 + 2 + 4 = 6이다.
예제 2: 처음 4ドル \times 4$ 크기의 쿠키에 적힌 숫자의 총합이 22 이므로 좌측 하단의 2번 쿠키 조각을 먹는다. 이후, 나머지 3개의 2ドル \times 2$ 크키의 쿠키에 적힌 숫자의 총합은 모두 6이므로 또 2번 쿠키 조각을 먹는다. 남은 쿠키 조각에 적힌 숫자의 총합은 14이다.
예제 3: 본문에서 다루었다.