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(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


  • 0
    THOANGLQDT    6:00 p.m. 29 Tháng 10, 2020

    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