Hướng dẫn giải của [200 đề thầy Đức] Bài 55: Cấp số cộng
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
Cho ba số của một cấp số cộng 4 số (công sai $d \ge 0$, các số có thể xếp theo thứ tự tăng dần), tìm số còn thiếu sao cho có đáp án và in ra số lớn nhất. Đầu vào luôn có đáp án, nên có thể có nhiều đáp án và ta chọn số lớn nhất.
Sub 1: Vét cạn theo công sai — ~O(2001 · 16)~
Sắp xếp ba số thành $p \le q \le s$. Thử mọi công sai $d$ từ $0$ đến $2000$ (vì hiệu của hai số đã cho nhỏ hơn 2000 nên $d$ không cần lớn hơn), và mọi vị trí của $p$ trong dãy $t, t+d, t+2d, t+3d$. Với mỗi cách, kiểm tra ba số đã cho có đều nằm trong dãy không; nếu có thì số còn lại là một đáp án. Lấy số lớn nhất trong các đáp án. Đạt 19/19 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long v[3];
cin >> v[0] >> v[1] >> v[2];
sort(v, v + 3); // v[0] < v[1] < v[2]
long long p = v[0], q = v[1], s = v[2];
// Vét cạn: thử mọi công sai d >= 0 (d không vượt 2000 vì hiệu hai số đã cho < 2000),
// thử mọi vị trí p trong cấp số cộng 4 số t, t+d, t+2d, t+3d, rồi kiểm tra
// ba số đã cho có nằm trong dãy không. Số còn lại là đáp án; lấy số lớn nhất.
long long best = LLONG_MIN;
for (long long d = 0; d <= 2000; d++) {
for (int k = 0; k < 4; k++) { // p là số thứ k trong dãy
long long t = p - k * d; // số đầu tiên của dãy
long long term[4];
for (int i = 0; i < 4; i++) term[i] = t + i * d;
int matched = 0, missing = 0;
bool has[3] = {false, false, false};
for (int i = 0; i < 4; i++) {
if (term[i] == p && !has[0]) { has[0] = true; matched++; }
else if (term[i] == q && !has[1]) { has[1] = true; matched++; }
else if (term[i] == s && !has[2]) { has[2] = true; matched++; }
else missing = i; // số không thuộc ba số đã cho
}
if (matched == 3) best = max(best, term[missing]);
}
}
cout << best << "\n";
return 0;
}
Sub 2: Công thức theo khoảng cách — ~O(1)~
Gọi $p \le q \le s$ là ba số đã cho. Có bốn vị trí có thể của số thiếu trong dãy, và mỗi vị trí cho một công thức:
- Số thiếu là số đầu: $q - p = s - q = d$, đáp án $p - d$.
- Số thiếu là số cuối: $q - p = s - q = d$, đáp án $s + d$.
- Số thiếu là số thứ hai: $q - p = 2d$, $s - q = d$, đáp án $p + d$.
- Số thiếu là số thứ ba: $q - p = d$, $s - q = 2d$, đáp án $q + d$.
Ta thử cả bốn trường hợp, trường hợp nào thỏa điều kiện thì ghi nhận đáp án, cuối cùng in ra số lớn nhất. Ví dụ $4, 6, 8$: cách đều $d=2$, đáp án $10$ hoặc $2$, in $10$. Ví dụ $10, 1, 7$: sắp xếp $1, 7, 10$ với $q-p=6=2(s-q)$, đáp án $p+3=4$.
Bẫy cần chú ý: trường hợp ba số bằng nhau ($d = 0$) cũng là cấp số cộng hợp lệ, đáp án chính là số đó, và công thức đầu tiên xử lý đúng trường hợp này.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long v[3];
cin >> v[0] >> v[1] >> v[2];
sort(v, v + 3);
long long p = v[0], q = v[1], s = v[2];
// Dãy 4 số t, t+d, t+2d, t+3d với d >= 0 (d = 0 khi ba số bằng nhau). Có 4 trường hợp số thiếu:
long long best = LLONG_MIN;
// 1) Thiếu số đầu: p,q,s là ba số sau, cách đều d = q-p = s-q.
if (q - p == s - q) best = max(best, p - (q - p));
// 2) Thiếu số cuối: p,q,s là ba số đầu, cách đều.
if (q - p == s - q) best = max(best, s + (s - q));
// 3) Thiếu số thứ 2: p, q, s là số 0, 2, 3 nên q - p = 2d, s - q = d.
if (q - p == 2 * (s - q)) best = max(best, p + (s - q));
// 4) Thiếu số thứ 3: p, q, s là số 0, 1, 3 nên q - p = d, s - q = 2d.
if (s - q == 2 * (q - p)) best = max(best, q + (q - p));
cout << best << "\n";
return 0;
}
Bình luận