Tháp (THT TP 2019)
Xem PDF
Điểm:
200 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Có một tháp các ô vuông bằng nhau có hình dạng giống một tam giác cân. Các hàng tính từ trên xuống dưới có số ô vuông lần lượt là \(1; 3; 5; 7; …\). Một tháp ô vuông có \(n\) hàng gọi là tháp ô vuông bậc \(n\) (\(n\) là số tự nhiên).
Ví dụ ở hình vẽ sau ta có một tháp ô vuông bậc \(3\):
Yêu cầu: Cho trước một tháp ô vuông bậc \(n\). Hãy tính xem trong tháp ô vuông này có tất cả mấy hình vuông tạo thành từ các ô vuông đó.
Input
- Chứa một số \(n\) (\(n \le 5 \times 10^5\)).
Output
- Ghi ra số nguyên \(m\) là số các hình vuông cần tìm.
Example
Test 1
Input
3Output
11
Bình luận
Mình xin đóng góp một cách giải :
Ta sẽ duyệt độ dài cạnh hình vuông, gọi là \(x\), lúc này cần đếm số hình vuông con cạnh \(x\) có trong tháp.
Xét ô góc trái trên của hình vuông con này. Dễ thấy : số hình vuông con = số lượng vị trí có thể cho ô góc trái trên
Hàng \(i\) chứa được ô góc trái trên khi và chỉ khi : \(2i-1 \ge x\) và \(i+x-1 \le n\). Chuyển vế đổi dấu có được \(i\) thuộc đoạn \([(x+1)/2, n-x+1]\).
Trên hàng \(i\), có \(2i-1 - x+1 = 2i-x\) ô trái trên. Suy ra cần tính \(sigma(2i-x) = sigma(2i) - sigma(x)\) . Ta được công thức O(1).
Tham khảo code mình ở đây : link
1 bình luận nữa