QUAD - Xây hàng rào
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Nông dân John muốn xây một cái hàng rào có 4 mặt vây lấy đàn bò. Ông ta có một thanh gỗ có độ dài là 1 số nguyên N (4 <= N <= 2,500), ông ta muốn cắt thanh gỗ này tại 3 điểm để chia thành 4 miếng nhỏ hơn, mỗi miếng có độ dài là 1 số nguyên.
4 miếng này dài ngắn thế nào cũng được miễn là có thể giúp nông dân John đóng được 1 cái hàng rào hình tứ giác là được. Hỏi có bao nhiêu cách khác nhau cắt thanh gỗ ban đầu để tạo thành được hàng rào ?
CHÚ Ý
- Hai cách cắt gọi là khác nhau nếu một cách có 1 nhát cắt tại 1 điểm mà cách kia không có.
- Đảm bảo rằng hàng rào này xây dựng có diện tích lớn hơn 0.
- Chú ý đáp án luôn nằm trong phạm vi 1 số nguyên 32 bit có dấu.
Dữ liệu
- Dòng 1: 1 số nguyên duy nhất: N
Kết quả
- Dòng 1: Một số nguyên duy nhất là số cách mà nông dân John có thể cắt thanh gỗ thành 4 miếng nhỏ hơn mà có thể tạo được 1 tứ giác.
Ví dụ
Dữ liệu 6 Kết quả 6
GIẢI THÍCH
Nông dân John có thể cắt thanh gỗ theo 10 cách: (1, 1, 1, 3); (1, 1, 2, 2); (1, 1, 3, 1); (1, 2, 1, 2); (1, 2, 2, 1); (1, 3, 1, 1); (2, 1, 1, 2); (2, 1, 2, 1); (2, 2, 1, 1); or (3, 1, 1, 1). Trong đó 4 cách -- (1, 1, 1, 3), (1, 1, 3, 1), (1, 3, 1, 1), và (3, 1, 1, 1) -- không thể sử dụng để tạo thành 1 tứ giác.
- Người up: paulmcvn
- Nguồn bài: USACO October 2008 - Qualifying Round