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
Mình xin chia sẻ lời giải bài toán này như sau:
Gọi \(f(m)\) là số hình vuông cần tìm, khi đó ta có: \(f(m)=f(m-1)+\sum\limits_{i=0}^{\left \lfloor{\frac{2m-1}{3}}\right \rfloor}2(m-i)-1-i\) với \(f(1)=1\) và \(m\ge 2\)
Trong đó \(2(m-i)-1-i\) chính là số hình vuông có cạnh là \(i+1\).
Từ công thức trên ta có: \(f(m)=f(m-1)+2m*(k(m)+1)-\frac{3k(m)(k(m)+1)}{2}-(k(m)+1)\) với \(k(m)=\left\lfloor{\frac{2m-1}{3}}\right\rfloor,f(1)=1,m\ge 2\).
Từ đây ta dễ dàng duyệt một for để xây dựng mảng \(f(m)\) với \(1\le m\le 5.10^5\)
Như vậy bài toán đã được chứng minh.
Các bạn có thể tham khảo code của mình tại \(\href{https://ideone.com/cMOxeY}{đây}\)