Hướng dẫn cho Restangles

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame

`Spoiler Alert`

Hint 1

Duyệt qua các hình chữ nhật, tăng biến đếm nếu chu vi thỏa mãn điều kiện

Hint 2

Dùng toán học, với vị trí (i, j) thì có bao nhiêu vị trí (i', j') để tạo thành hình chữ nhật ((i, i'), (j, j')) thỏa mãn điều kiện

Hint 3

Formula: Tại (i, j) thỏa điều kiện 2 * (i + j) ≥ k có (n - i + 1) * (m - j + 1) cách chọn hình chữ nhật

Reference AC code | O(n) time | O(n) auxiliary space |

C++

int main()
{
    int n = readInt();
    int m = readInt();
    int k = readInt();

    ll res = 0;
    for (int a = 1; a <= n; ++a)
        for (int b = 1; b <= m; ++b)
            if (2 * (a + b) >= k) 
                res += 1LL * (n - a + 1) * (m - b + 1); 

    cout << res;
    return 0;
}

Bình luận

int main()
{
int n = readInt();
int m = readInt();
int k = readInt();

ll res = 0;
for (int a = 1; a <= n; ++a)
    for (int b = 1; b <= m; ++b)
        if (2 * (a + b) >= k) 
            res += 1LL * (n - a + 1) * (m - b + 1);

cout << res;
return 0;

}

2 bình luận nữa