To solve this problem, we need to maximize the number of 1x2 dominoes placed on an NxN grid such that the number of horizontal dominoes equals the number of vertical dominoes.

Approach

The solution can be broken down into three main cases based on the value of N:

1. Case N = 2: The 2x2 grid can only be covered by either two horizontal dominoes or two vertical dominoes, so it's impossible to have an equal number of horizontal and vertical dominoes. Thus, the answer is 0.
2. Case N is odd: For an odd-sized grid, the maximum number of dominoes that can be placed is ((N^2 -1)/2) (since one cell will remain uncovered). This value is even, so it can be split equally into horizontal and vertical dominoes.
3. Case N is even (N >=4): For even-sized grids larger than 2x2, the maximum number of dominoes is (N^2/2) (all cells are covered). This value is even, so it can be split equally into horizontal and vertical dominoes.

Solution Code

n = int(input())
if n == 2:
    print(0)
elif n % 2 == 1:
    print((n * n - 1) // 2)
else:
    print(n * n // 2)

Explanation

• N=2: The grid size is too small to have an equal number of horizontal and vertical dominoes, so the result is 0.
• Odd N: The total number of cells is odd, so one cell remains uncovered. The number of dominoes is ((N^2 -1)/2), which is even and can be split into equal horizontal and vertical dominoes.
• Even N >=4: The total number of cells is even, so all cells are covered. The number of dominoes is (N^2/2), which is even and can be split into equal horizontal and vertical dominoes.

This approach efficiently computes the result in constant time (O(1)) for any given N. It handles all possible values of N correctly and provides the optimal solution.

作者声明:本文包含人工智能生成内容。