Hướng dẫn giải của Hình vuông
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Gọi S là tổng 4 số trên 4 đỉnh. Mỗi hình vuông mới có đỉnh là tổng của hai đỉnh kề cũ, nên mỗi số cũ được cộng vào hai đỉnh mới, và tổng S tăng đúng gấp đôi sau mỗi bước. Do đó tổng ở hình vuông thứ N là 2^(N-1)·(a+b+c+d).
Sub 1: Mô phỏng từng bước — ~O(N)~
Mô phỏng đúng quy tắc: với mỗi hình vuông mới, đỉnh i = đỉnh i cũ + đỉnh (i+1) cũ, lặp N-1 lần rồi cộng 4 đỉnh. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
long long v[4];
for (int i = 0; i < 4; i++) cin >> v[i];
// Mô phỏng từng hình vuông: đỉnh i của hình mới = v[i] + v[(i+1)%4]
for (int step = 1; step < N; step++) {
long long w[4];
for (int i = 0; i < 4; i++) w[i] = v[i] + v[(i + 1) % 4];
for (int i = 0; i < 4; i++) v[i] = w[i];
}
cout << v[0] + v[1] + v[2] + v[3] << "\n";
return 0;
}
Sub 2: Công thức nhân đôi — ~O(1)~
Tổng ở hình thứ N là (a+b+c+d)·2^(N-1), tính bằng dịch bit. Với N ≤ 50 và a..d ≤ 500 giá trị tối đa khoảng 10^18 nên vừa khít kiểu long long. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
long long a, b, c, d;
cin >> a >> b >> c >> d;
// Mỗi cạnh mới được tạo từ hai đỉnh cũ, nên tổng 4 đỉnh tăng gấp đôi sau mỗi bước.
// Tổng sau N hình vuông = 2^(N-1) * (a+b+c+d). Với N <= 50, a..d <= 500, giá trị < 2^63.
long long s = a + b + c + d;
cout << (s << (N - 1)) << "\n";
return 0;
}
Bình luận