NOFTRI - Số lượng tam giác
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
0.005s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
- Cho tam giác ~ABC~. Trên cạnh ~BC~ lấy ~n~ điểm khác nhau (không trùng với ~B~ và ~C~). Nối ~A~ với các điểm đó. Hãy xác định xem ta có thể đếm được bao nhiêu hình tam giác.
Input
- Gồm ~1~ dòng ghi số nguyên dương ~n (1 \le n \le 10^9).~
Output
- Ghi ~1~ số nguyên duy nhất là số lượng tam giác đếm được sau khi chia dư cho ~10^9 + 7.~
Sample
Input #1
2
Output #1
6
Bình luận
Ý tưởng: time limit ngắn nên cần công thức tính nhanh. Câu hỏi là dùng công thức nào ?
Cứ n điểm trên BC sẽ chia tam giác ABC thành n + 1 phần. vậy ta chỉ cần đi tính cách ghép của (n + 1) tam giác đó với nhau.
Ví dụ n = 4, ta sẽ chia tam giác thành 5 phần (mình gọi là I, II, III, IV, V từ trái qua phải), gọi t = 0 là số lượng tam giác.
Do không vẽ được hình nên để dễ tưởng tượng các bạn vẽ ra nhé :>.
Khi đó ta bắt đầu từ tam giác I, bản thân nó làm tam giác nên t += 1. Sau đó ta ghép nó với tam giác II ta sẽ được tam giác (I, II), lại ghép thêm tam giác bên cạnh tiếp theo lại được 1 tam giác to hơn là tam giác (I, II, III) t += 1. Đến tam giác cuối cùng ta được t = 5. Quay về đầu bắt đầu từ tam giác II lại ghép với III, t += 1. Cứ như vậy, ta thấy ngay rằng số lượng tam giác sẽ là 5 + 4 + 3 + 2 + 1. Chính là tổng từ 1 -> (n + 1)
Cái này có công thức tính nhanh đó là (((n + 1) + 1) * (n + 1)) / 2. Đó là kết quả của bài toán.
CƯỜNG GIẢ HỌ ĐINH, VẠN CỔ TỐI CƯỜNG. CAO CAO TẠI THƯỢNG, DUY NGÃ ĐỘC TÔN
giới hạn thời gian có hơi quá không ad:<