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 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}\)
-
33
NgJaBach
5:52 p.m. 12 Tháng 8, 2020
-
4
thangdeptraidonghuong
5:51 p.m. 11 Tháng 10, 2022
-
0
mdtung
8:55 p.m. 1 Tháng 9, 2024
1 bình luận nữaEm không thích có lời giải ở ngay dưới comment cho lắm, em muốn thử tự làm sau đó bí quá mới đọc giải. Chứ vừa nhìn đề kéo xuống đã nhìn thấy ngay spoiler cảm thấy mất hứng thế nào ấy :<
bạn đừng đọc comment nữa, làm xong rồi đọc
brilliant move!!!