結果

問題 No.1213 sio
ユーザー qwewe
提出日時 2025-05-14 12:57:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,161 bytes
コンパイル時間 570 ms
コンパイル使用メモリ 70,048 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-14 12:59:10
合計ジャッジ時間 1,883 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 13 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm> // Not strictly necessary for this code, but includes useful functions like std::max

// Using long long for potentially large inputs N, M, up to 10^8
using ll = long long;

int main() {
    // Faster I/O operations for competitive programming
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    ll N, M; // Declare N and M as long long to handle values up to 10^8
    std::cin >> N >> M;
    
    // The problem asks us to tile an N x M grid using S, I, and O tetrominoes.
    // We want to minimize the number of uncovered cells first. Since each tetromino covers 4 cells,
    // the minimum number of uncovered cells is (N * M) % 4.
    // Among all ways to achieve this minimum uncovered area, we want to minimize the number of I-tetrominoes used.

    // Case 1: One of the dimensions is 1.
    // If N = 1, the grid is 1xM. The only tetromino that can fit is the 1x4 I-tetromino.
    // To minimize uncovered cells, we should place as many 1x4 blocks as possible.
    // The maximum number of 1x4 blocks we can place is floor(M/4).
    // This covers 4 * floor(M/4) cells, leaving M % 4 cells uncovered, which is the minimum possible.
    // All tetrominoes used must be I-type. Thus, the minimum number of I-tetrominoes is M / 4 (integer division).
    if (N == 1) {
        std::cout << M / 4 << "\n"; 
    } 
    // Similarly, if M = 1, the grid is Nx1. The only tetromino that can fit is the 4x1 I-tetromino.
    // The maximum number of 4x1 blocks is floor(N/4).
    // This covers 4 * floor(N/4) cells, leaving N % 4 cells uncovered, the minimum possible.
    // All tetrominoes must be I-type. Minimum I-tetrominoes is N / 4.
    else if (M == 1) {
        std::cout << N / 4 << "\n";
    } 
    // Case 2: Both dimensions are 2 or greater.
    // If N >= 2 and M >= 2.
    // Extensive analysis based on tiling theory and decomposition arguments suggests that
    // for any grid with both dimensions at least 2, it's always possible to achieve the minimum
    // number of uncovered cells using only S-type tetrominoes (which includes Z-type due to reflections being allowed)
    // and O-type tetrominoes (2x2 blocks). 
    // For example:
    // - If N and M are both even, the grid can be perfectly tiled with O-tetrominoes (2x2 blocks).
    // - If N is even and M is odd (or vice versa), the grid area NM might be divisible by 4 or leave a remainder of 2.
    //   It can be shown through decomposition (e.g., splitting into smaller known-tileable rectangles like 4xM or 2xM)
    //   that the minimal uncovered cells can be achieved without I-tetrominoes.
    // - If N and M are both odd, the grid area NM is odd. It leaves a remainder of 1 or 3 when divided by 4.
    //   Again, decomposition arguments (e.g., using 3x3 base cases and extending) suggest that minimal uncovered cells
    //   can be achieved without I-tetrominoes.
    // Since S and O tetrominoes are sufficient to achieve the goal of minimizing uncovered cells when N, M >= 2,
    // the minimum required number of I-tetrominoes is 0.
    else {
        std::cout << 0 << "\n";
    }
    
    return 0;
}
0