Hướng dẫn giải của Điền dấu (KS THCS 05)
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
Cho t test, mỗi test có n số 1 và m số 2 (n, m ≤ 10^5). Cần đặt dấu + hoặc - trước mỗi số sao cho tổng bằng 0.
Sub 1: Vét cạn, thử số lượng dấu + — ~O(n \cdot m)~
Nếu tổng n + 2m lẻ thì không thể bằng 0. Ngược lại, cần chọn a số 1 và b số 2 mang dấu + sao cho a + 2b bằng nửa tổng. Thử mọi cặp (a, b).
Kết quả chấm: 3/20 (SUB ok 3/20, TLE 17, WA 0)
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("EXP.INP", "r", stdin);
freopen("EXP.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
long long n, m;
cin >> n >> m;
long long tong = n + 2 * m;
bool ok = false;
// Vet can: tong cac so mang dau + phai bang nua tong. Thu moi so a (so 1 mang dau +) va b (so 2 mang dau +)
if (tong % 2 == 0) {
long long can = tong / 2;
for (long long a = 0; a <= n && !ok; a++)
for (long long b = 0; b <= m; b++)
if (a + 2 * b == can) { ok = true; break; }
}
cout << (ok ? "YES" : "NO") << "\n";
}
return 0;
}
Sub 2: Công thức kiểm tra — ~O(1)
Tổng n + 2m chẵn khi và chỉ khi n chẵn. Nếu m chẵn thì ghép các cặp +2, -2 và +1, -1. Nếu m lẻ thì cần ít nhất hai số 1 để tạo 1 + 1 - 2 = 0. Vậy đáp án YES khi n chẵn và (m chẵn hoặc n ≥ 2).
Kết quả chấm: 20/20
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("EXP.INP", "r", stdin);
freopen("EXP.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
long long n, m;
cin >> n >> m;
// Tong n + 2m phai chan nen n chan. Neu m chan thi ghep cac cap +2, -2 va +1, -1.
// Neu m le thi can it nhat hai so 1 de tao 1 + 1 - 2 = 0.
bool ok = (n % 2 == 0) && (m % 2 == 0 || n >= 2);
cout << (ok ? "YES" : "NO") << "\n";
}
return 0;
}
Bình luận