L-trominos
Limits: 2 sec., 512 MiB
We have a rectangular grid of \(2\) rows and \(n\) columns.
Also, you have an infinite supply of L-trominos:
You want to tile the grid with L-trominos to satisfy the following conditions.
When placing each tromino, rotation, and reflection are allowed.
Each tile must align with cells.
Each cell in the grid must be covered by at most one tromino.
No part of each tromino may be outside the grid.
Find the minimum number of uncovered cells in the grid.
Input
The single line contains an integer \(n\) – the number of columns in the grid.
Output
Print a single integer – the minimum number of uncovered cells in the grid.
Constraints
\(1 \le n \le 10^6\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 3 | 0 |
| Input (stdin) | Output (stdout) |
|---|---|
| 4 | 2 |
| Input (stdin) | Output (stdout) |
|---|---|
| 47 | 1 |
Notes
Source: Ukrainian National Programming Contest 2024 - Stage 2
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|