Ram & Shyam

0

0 votes
Medium
Problem

Ram and Shyam are bored. So they decide to play a game. The game description is as follows. Given n grids of size 3X3 with each cell of each grid being 1 or 0. Each player move in turns, Ram moves first. On each step the game proceeds as follows :

1. Choose a grid from one of the n grids which has atleast one nonzero character in it.

2. Choose a cell with 1 on it and turn it 0. Now, for all the cells whose Manhattan distance from the chosen cell is exactly k and have 1 in it are considered in the range of this cell. The player may(or may not) turn any of these cells in the range to 0.(See sample explanation for more details.)

3. If a player can't make a move, he loses.

 

They will play the game on all subarrays(3X3 grids) of the array of size n. If both players play optimally, find the number of cases where Ram wins and the number of cases where Shyam wins.

 

Note: A player can only choose a cell with a 1 on it.

 

Constraints :
1 <= t <= 500

1 <= n <= 512

0 <= k <= 4

Each cell of each grid can be 0 or 1.

 

Input Format

First line contains t denoting the number of test cases.

Second line contains n and k separated by a space in between.

n grids follow where each grid has the dimensions of 3X3.

 

Output format

Output 2 integers separated by space where the first integer denotes the number of games Ram wins and the second integer denoting the number of games Shyam wins.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

GIven n=2.

So the possible subarrays are with index {1},{2},{1,2}.

For subarray {1}:

Ram changes the only 1 to 0

For subarray {2}:

Ram changes the first 1 to 0 and since the second 1 is at manhattan distance = k,he turns it to 0 as well.

For subarray {1,2}:

Ram changes the first 1 to 0 from the second grid. Now whatever move Shyam makes, he is in a losing state.

Editor Image

?