Tháp (THT TP 2019)

Xem PDF
Tác giả:
Small
Dạng bài
Đ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 
3
Output 
11

Bình luận


  • 5
    jumptozero    8:46 a.m. 14 Tháng 7, 2020 ← chỉnh sửa 3

    • 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}\)


    • 30
      NgJaBach    5:52 p.m. 12 Tháng 8, 2020

      Em 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 :<

    1 bình luận nữa