I. Grid Game
constructive algorithms; games; graph matchings; greedy; interactive
This is an interactive problem.You are given a grid with \(n\) rows and \(m\) columns. You need to fill each cell with a unique integer from \(1\) to \(n \cdot m\).After filling the grid, you will play a game on this grid against the interactor. Players take turns selecting one of the previously unselected cells from the grid, with the interactor going first.On the first turn, the interactor can choose any cell from the grid. After that, any chosen cell must be orthogonally adjacent to at least one previously selected cell. Two cells are considered orthogonally adjacent if they share an edge. The game continues until all cells have been selected.Your goal is to let the sum of numbers in the cells selected by you be strictly less than the sum of numbers in the cells selected by the interactor.
Each test contains multiple test cases. The first line contains a single integer \(t\) (\(1 \le t \le 100\)) — the number of test cases. The description of test cases follows.The only line of each test case contains two integers \(n\) and \(m\) (\(4 \le n, m \le 10\)) — the number of rows and columns in the grid.
Note that this is an example game and does not necessarily represent the optimal strategy for both players.First, we fill a \(4 \times 4\) grid with unique integers from \(1\) to \(16\) in the following way: \(2\)\(3\)\(4\)\(10\)\(12\)\(6\)\(11\)\(15\)\(5\)\(13\)\(16\)\(8\)\(9\)\(7\)\(1\)\(14\) Next, the game begins. The interactor first selects \((3, 4)\), which is the number \(8\). For this selection, the interactor could choose any number. From the next selection onwards, each chosen number has to be adjacent to any previously selected number. We select \((2, 4)\), which is the number \(15\), adjacent to \((3, 4)\). The interactor selects \((4, 4)\), which is the number \(14\), adjacent to \((3, 4)\). We select \((4, 3)\), which is the number \(1\), adjacent to \((4, 4)\). \(\ldots\) This is continued until all numbers are selected. In the end, the numbers we selected were \([15, 1, 16, 5, 4, 2, 11, 13]\), and the numbers selected by the interactor were \([8, 14, 7, 9, 10, 3, 6, 12]\). The sum of the numbers we selected is \(67\), which is less than the sum of the numbers selected by the interactor \(69\). Therefore, we have won this game.