Hình Vuông (VUONG) (Tin học trẻ Đà Nẵng 2017-2018, bảng B)

Nguồn: Tin học trẻ TP Đà Nẵng 2017-2018 · Bảng B Độ khó: Dễ Toán học Tìm quy luật Mô phỏng

Đề bài

Bài 3. Hình vuông (Hội thi Tin học trẻ cấp thành phố Đà Nẵng, năm học 2017-2018 – Đề thi bảng B, khối THCS)

Từ một hình vuông cho trước, ta vẽ các đoạn thẳng nối trung điểm hai cạnh kề của nó thì được một hình vuông mới nhỏ hơn. Tiếp tục, vẽ các đoạn thẳng nối trung điểm hai cạnh kề của hình vuông được tạo thành này thì được một hình vuông mới nhỏ hơn nữa. Cứ làm như vậy cho đến khi được tất cả $N$ hình vuông.

Các hình vuông theo thứ tự tăng dần về độ dài của các cạnh ta đánh số thứ tự từ $1$ đến $N$.

Ở hình vuông thứ nhất ta ghi 4 số tự nhiên $a, b, c, d$ trên 4 đỉnh của nó.

Mỗi số trên 4 đỉnh của hình vuông thứ hai được xác định bằng tổng của 2 số trên 2 đỉnh gần với nó nhất của hình vuông thứ nhất.

Mỗi số trên 4 đỉnh của hình vuông thứ ba được xác định bằng tổng của 2 số trên 2 đỉnh gần với nó nhất của hình vuông thứ hai. Cứ làm như vậy cho hết $N$ hình vuông.

Yêu cầu: Tính tổng các số trên 4 đỉnh của hình vuông thứ $N$.

Dữ liệu vào: Đọc từ file văn bản VUONG.INP

• Dòng đầu là số $N$ $(1 \le N \le 50)$.
• Dòng thứ 2 chứa 4 số $a, b, c, d$, mỗi số cách nhau 1 dấu cách $(1 \le a, b, c, d \le 500)$.

Dữ liệu ra: Ghi ra file văn bản VUONG.OUT một số nguyên duy nhất theo yêu cầu trên.

Thời gian chạy chương trình không quá 2 giây. (Trên hệ thống chấm online thì đọc/ghi chuẩn – bàn phím/màn hình, code trong bài cũng vậy.)

Minh hoạ bằng hình vẽ với $N = 3$, $a = 1$, $b = 3$, $c = 5$, $d = 7$:

Hình vuông 1 (trong cùng): 1, 3, 5, 7 · hình vuông 2: 4, 8, 12, 8 · hình vuông 3 (ngoài cùng): 12, 12, 20, 20.

VUONG.INP

3
1 3 5 7

VUONG.OUT

64

Lời mở đầu

Bài này nằm trong đề thi Tin học trẻ bảng B (bảng của cấp 2 – THCS) thành phố Đà Nẵng, mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Mình cũng hơi bất ngờ khi đọc đề, vì bài này nằm ở cuối đề thi, mà theo nguyên tắc bài cuối thường là bài khó nhất, vậy mà đọc vào thấy nó như bài dễ nhất đề luôn, kiểu cho điểm vậy :)). Cái đề dài dòng làm ta bị rối, nào là nối trung điểm các cạnh tạo thành hình vuông mới các kiểu, dễ làm ta lầm tưởng về cách xử lý. Các bạn cứ bám theo đúng ví dụ đề đưa ra, nhìn kỹ hình vẽ và tính tổng của từng hình vuông từ trong ra ngoài là sẽ thấy ngay quy luật.

Giải thích ví dụ cho bạn nào chưa hiểu đề: hình vuông 1 (trong cùng) có các đỉnh $a = 1$ (trên trái), $b = 3$ (trên phải), $c = 5$ (dưới phải), $d = 7$ (dưới trái). Mỗi đỉnh của hình vuông 2 nằm "giữa" hai đỉnh kề nhau của hình vuông 1, nên nó bằng tổng hai đỉnh đó: $1 + 3 = 4$, $3 + 5 = 8$, $5 + 7 = 12$, $7 + 1 = 8$. Tương tự hình vuông 3 có các đỉnh $4 + 8 = 12$, $8 + 12 = 20$, $12 + 8 = 20$, $8 + 4 = 12$. Tổng 4 đỉnh của hình vuông thứ $N = 3$ là $12 + 20 + 20 + 12 = 64$.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Mô phỏng từng hình vuông · O(N)Cách 2Quy luật nhân đôi · công thức

Cách 1Làm đúng như đề mô tả – O(N)

Trong trường hợp chưa nhìn ra quy luật thì ta vẫn giải được theo cách đơn giản nhất là làm đúng như đề mô tả: từ hình vuông trong cùng (hình vuông thứ 1), tổng 2 đỉnh kề nhau của nó cho ra một đỉnh của hình vuông thứ 2 bên ngoài, cứ thế tính đủ 4 đỉnh. Rồi từ hình vuông thứ 2 lại lặp lại quy trình để ra hình vuông thứ 3... Sau cùng có 4 đỉnh của hình vuông thứ $N$ thì đáp án là tổng 4 số đó.

Công thức chuyển từ hình vuông này sang hình vuông kế tiếp

Nếu hình vuông hiện tại có 4 đỉnh $a, b, c, d$ (theo chiều kim đồng hồ) thì hình vuông kế tiếp có 4 đỉnh:
$a_1 = a + b,\quad b_1 = b + c,\quad c_1 = c + d,\quad d_1 = d + a$.

Minh hoạ

Em nhập $N$ và 4 số $a, b, c, d$ rồi bấm Tiếp để xem từng hình vuông mới được vẽ ra bên ngoài: mỗi đỉnh mới (xanh lá) bằng tổng 2 đỉnh gần nó nhất (cam) của hình vuông trước. Bảng bên dưới ghi lại tổng 4 đỉnh của từng hình vuông – để ý cột tổng nhé 😉.

N a b c d

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main(){
    long long n, a, b, c, d, a1, b1, c1, d1;
    cin >> n >> a >> b >> c >> d;
    for(int i = 2; i <= n; ++i){
        a1 = a + b;
        b1 = b + c;
        c1 = c + d;
        d1 = d + a;
        a = a1;
        b = b1;
        c = c1;
        d = d1;
    }
    cout << a + b + c + d;
    return 0;
}

n = int(input())
a, b, c, d = map(int, input().split())
for i in range(2, n + 1):
    a, b, c, d = a + b, b + c, c + d, d + a
print(a + b + c + d)

Giải thích một số chỗ trong code:

1. Ở bước nhập dữ liệu coi như đã có thông tin của hình vuông thứ 1, ta chỉ bắt đầu tìm từ hình vuông thứ 2 trở đi, vì thế vòng lặp for i bắt đầu từ 2. a1, b1, c1, d1 chính là 4 đỉnh của hình vuông mới, bằng tổng 2 đỉnh liền kề của hình vuông đã có. Tạo xong thì gán ngược lại cho a, b, c, d để lần lặp sau tiếp tục sinh hình vuông mới. Sau lần lặp i = n thì a, b, c, d chính là 4 đỉnh của hình vuông lớn nhất ngoài cùng, ta xuất tổng 4 số ra.
2. Phải dùng 4 biến tạm a1, b1, c1, d1 chứ không gán thẳng a = a + b; b = b + c; ... được, vì đến dòng d = d + a thì a đã bị đổi thành giá trị mới mất rồi. (Python thì gán đồng thời a, b, c, d = a + b, b + c, c + d, d + a nên không cần biến tạm.)
3. Các số được cộng dồn liên tục nên kết quả có thể rất lớn, vì thế dùng kiểu long long (số nguyên 8 byte) để tránh tràn số.

C++▶ Chạy tay từng dòng codeCách 1: lặp i = 2..n, mỗi lần tính 4 đỉnh mới bằng tổng 2 đỉnh kề rồi gán lại.

Dữ liệu vào (stdin) – sửa thoải mái3 1 3 5 7

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 long long n, a, b, c, d, a1, b1, c1, d1;

6 cin >> n >> a >> b >> c >> d;

7 for(int i = 2; i <= n; ++i){

8 a1 = a + b;

9 b1 = b + c;

10 c1 = c + d;

11 d1 = d + a;

12 a = a1;

13 b = b1;

14 c = c1;

15 d = d1;

16 }

17 cout << a + b + c + d;

18 return 0;

19}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: chỉ vài biến ⇒ $O(1)$.
• Thời gian: $O(N)$ với $N$ là số thứ tự hình vuông cần tìm. Đề cho $N$ tối đa $50$ nên chỉ lặp tối đa 49 lần, quá nhỏ, yên tâm không thể nào bị TLE.

Không gian$O(1)$

Thời gian$O(N)$

Cách 2Nhìn ra quy luật nhân đôi – công thức

Thực ra cách ở trên chưa phải là cách tối ưu nhất đâu các bạn. Như mình có nói hồi đầu, các bạn thử tính tổng của từng hình vuông từ trong cùng ra xem có thấy quy luật không? Với ví dụ mẫu, tổng các hình vuông 1, 2, 3 lần lượt là $16, 32, 64$:

$32 = 16 \cdot 2,\qquad 64 = 32 \cdot 2$

Nghĩa là tổng hình vuông 2 bằng 2 lần tổng hình vuông 1, tổng hình vuông 3 bằng 2 lần tổng hình vuông 2. Tổng quát: tổng hình vuông $i$ = 2 × tổng hình vuông $i - 1$.

Vì sao lại nhân đôi?

Tổng 4 đỉnh mới là $(a + b) + (b + c) + (c + d) + (d + a) = 2(a + b + c + d)$: mỗi đỉnh cũ được cộng vào đúng 2 đỉnh mới (2 đỉnh mới gần nó nhất). Vậy sau $N - 1$ lần nhân đôi:
$S_N = (a + b + c + d) \cdot 2^{N-1}$

Nhìn ra điều này thì không cần 4 biến a1, b1, c1, d1 gán qua gán lại nữa, chỉ cần tính tổng 4 đỉnh ban đầu rồi nhân 2 liên tục $N - 1$ lần. Và nhìn kỹ hơn nữa thì cũng chẳng cần vòng lặp: nhân 2 đủ $N - 1$ lần chính là nhân với $2^{N-1}$. Vậy ta làm đơn giản thế này thôi:

#include <bits/stdc++.h>
using namespace std;

int main(){
    long long n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;
    cout << (long long)pow(2, n - 1) * (a + b + c + d);
    return 0;
}

n = int(input())
a, b, c, d = map(int, input().split())
print(2 ** (n - 1) * (a + b + c + d))

Nhớ ép kiểu (long long)

Hàm pow trả về số thực; nhân số thực với tổng 4 đỉnh thì kết quả cũng là số thực, in ra có thể sai định dạng (ví dụ printf("%f") ra 64.000000, còn cout với số lớn thì ra dạng khoa học 1.1259e+18). Vì vậy phải ép kiểu (long long) ở chỗ pow(2, n - 1) (hoặc ép kết quả cuối). Và phải là long long chứ quen tay ép (int) là toang nha :)) – với $N = 50$ thì $2^{49} = 562\,949\,953\,421\,312$ đã vượt xa giới hạn 4 byte, nhân thêm tổng 4 đỉnh (tối đa $2000$) còn lớn nữa: tối đa $2000 \cdot 2^{49} \approx 1.13 \cdot 10^{18}$, vẫn vừa trong long long (khoảng $9.2 \cdot 10^{18}$).

Muốn chắc ăn tuyệt đối

$2^{49}$ biểu diễn chính xác được bằng số thực double nên pow ở đây không bị sai số. Nhưng nếu muốn tránh hẳn số thực thì có thể viết (1LL << (n - 1)) – dịch bit trái $n - 1$ lần cũng chính là $2^{n-1}$, hoàn toàn tính bằng số nguyên.

C++▶ Chạy tay từng dòng codeCách 2: in thẳng 2^(n−1) · (a + b + c + d).

Dữ liệu vào (stdin) – sửa thoải mái3 1 3 5 7

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 long long n, a, b, c, d;

6 cin >> n >> a >> b >> c >> d;

7 cout << (long long)pow(2, n - 1) * (a + b + c + d);

8 return 0;

9}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: vẫn là $O(1)$.
• Thời gian: các bạn đừng nghĩ pow(2, n - 1) là phải lặp $N - 1$ lần nhân 2 nha. Lũy thừa tính bằng thuật toán lũy thừa nhanh chỉ tốn $O(\log N)$ (log cơ số 2); với dịch bit 1LL << (n - 1) thì còn là $O(1)$. Code vừa gọn hơn nhiều mà độ phức tạp cũng tốt hơn cách trước.

Không gian$O(1)$

Thời gian$O(\log N)$

Thực ra với $N$ tối đa $50$ như bài này thì $O(N)$ hay $O(\log N)$ cũng chẳng khác biệt mấy. Nhưng giả sử $N$ cho tới $10^9$ (và đề hỏi kết quả chia lấy dư cho một số nào đó để khỏi tràn số) thì cách 1 phải lặp 1 tỷ lần, vượt ngưỡng 2 giây (cỡ $10^8$, cao lắm $2 \cdot 10^8$) ⇒ TLE, trong khi lũy thừa nhanh chỉ lặp khoảng 30 lần. Các bạn thấy kinh khủng chưa? 1 tỷ lần so với 30 lần 😍.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 300 bộ test (mọi $N$ từ 1 đến 50, mỗi $N$ 6 bộ $a, b, c, d$ ngẫu nhiên, có cả bộ $a = b = c = d = 500$), so với code mô phỏng bằng số nguyên lớn của Python – khớp hết. Trường hợp lớn nhất $N = 50$, $a = b = c = d = 500$ cho đáp án $1\,125\,899\,906\,842\,624\,000$, vừa trong long long.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇