Restangles

Xem PDF
Tác giả:
admin
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Có bao nhiêu hình chữ nhật trong hình dưới đây?

Chúng ta có \(6\) hình chữ nhật \(1 \times 1\), \(4\) hình \(2 \times 1\), \(3\) hình \(1 \times 2\), \(2\) hình \(2 \times 2\), \(2\) hình \(3 \times 1\) và \(1\) hình \(3 \times 2\), tổng cộng là \(18\)
hình. Rõ ràng chúng ta quan tâm đến các hình chữ nhật có các đỉnh nằm ở các đỉnh lưới, tức là các điểm nằm ở giao của các đường thẳng ngang và dọc, và nằm trọng vẹn trong lưới. Lưới trên có kích thước \(3 \times 2\).

Yêu cầu: Có bao nhiêu hình chữ nhật có chu vi ít nhất là \(6\) ở hình trên? Có thể tham khảo phần Ví dụ để biết câu trả lời.

Input

  • Một dòng chứa 3 số nguyên \(n, m, p\) (\(1 \leq n, m \leq 5000, 4 \leq p \leq 2 \times (n+m)\)) cho biết kích thước của lưới và giới hạn dưới của chu vi các hình chữ nhật.

Output

  • Một dòng in một số nguyên: số các hình chữ nhật có đỉnh nằm tại các điểm của lưới \(n \times m\), nằm trọn vẹn trong lưới và chu vi ít nhất là \(p\).

Example

Test 1

Input 
3 2 4
Output 
18

Test 2

Input 
3 2 6
Output 
12

Bình luận


  • 1
    SPyofgame    12:08 a.m. 13 Tháng 6, 2020

    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;
}