Hướng dẫn giải của [200 đề thầy Đức] Bài 76: Xếp đẳng thức bằng que diêm
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
Cần xếp đẳng thức $a + b = c$ với $a, b, c \ge 1$ bằng đúng $n$ que (kể cả que mua thêm), tìm số que ít nhất phải mua thêm. Dấu $+$ và dấu $=$ không tính vào số que, và phải dùng hết các que đang có.
Sub 1: Vét cạn số que mua thêm — ~O(n)~
Với mỗi $m = 0, 1, 2, \dots$, xét tổng $t = n + m$. Một đẳng thức $a + b = c$ có $a + b + c = 2c$ que nên thử mọi $c$ từ $2$ đến $t/2$: nếu $2c = t$ thì xếp được (ví dụ $a = 1$, $b = c - 1$), và $m$ là đáp án. Cách này đúng nhưng chậm khi $n$ lớn (đạt 11/21 test, 10 test quá giờ, không sai test nào).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
long long n;
cin >> n;
// Đẳng thức a + b = c dùng a + b + c = 2c que. Vét cạn: thử m = 0, 1, 2, ...
// và với mỗi m, thử mọi c (c >= 2) xem có 2c = n + m không.
long long ans = -1;
for (long long m = 0; ans == -1; m++) {
long long t = n + m;
for (long long c = 2; c <= t / 2 && ans == -1; c++) {
if (2 * c == t) ans = m; // a = 1, b = c - 1 là một cách xếp
}
}
cout << ans << "\n";
}
return 0;
}
Sub 2: Quy luật số chẵn — ~O(1)~
Tổng số que $a + b + c = 2c$ luôn là số chẵn, và nhỏ nhất là $4$ (với $1 + 1 = 2$). Từ đó:
- $n$ chẵn và $n \ge 4$: không cần mua thêm, đáp án $0$. Ví dụ $n = 8$: $1 + 3 = 4$.
- $n = 2$: phải mua thêm 2 que để thành 4, đáp án $2$. Đây là trường hợp đặc biệt vì $2$ không đủ để xếp đẳng thức.
- $n$ lẻ: mua thêm 1 que để thành số chẵn (vì $n \ge 3$ nên $n + 1 \ge 4$), đáp án $1$. Ví dụ $n = 5$ và $n = 11$.
Bẫy cần chú ý: trường hợp $n = 2$ dễ bị quên, vì $2$ là số chẵn nhưng không xếp được đẳng thức.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
long long n;
cin >> n;
// Đẳng thức a + b = c có tổng số que a + b + c = 2c, luôn là số chẵn và ít nhất là 4 (1 + 1 = 2).
// - n chẵn và n >= 4: không cần mua thêm.
// - n = 2: cần mua thêm 2 que (thành 4).
// - n lẻ: mua thêm 1 que để thành số chẵn (n >= 3 nên n + 1 >= 4).
long long m;
if (n == 2) m = 2;
else if (n % 2 == 0) m = 0;
else m = 1;
cout << m << "\n";
}
return 0;
}
Bình luận