Hướng dẫn giải của [VT Thiếu nhi] BÀI 26: ODDEVE
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 d = b - a. Nếu d = 0 thì không cần bước nào. Nếu d > 0 và d lẻ thì cộng một số lẻ d là xong (1 bước); nếu d > 0 và d chẵn thì cần 2 bước. Nếu d < 0, đặt e = -d: e chẵn thì trừ một số chẵn e là xong (1 bước); e lẻ thì cần 2 bước.
Sub 1: Xét tính chẵn lẻ của hiệu (chỉ một lời giải) — ~O(1)~
Bài này chỉ cần xét tính chẵn lẻ của hiệu b - a nên chỉ viết một sub. Lý do: các cách vét cạn (BFS trên các giá trị, hoặc thử mọi giá trị trung gian) đều phải duyệt tới ~10^9 giá trị cho mỗi testcase nên không có sub chậm nào đạt đúng ít nhất một test. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("ODDEVE.INP", "r")) { freopen("ODDEVE.INP", "r", stdin); freopen("ODDEVE.OUT", "w", stdout); }
int t;
cin >> t;
while (t--) {
long long a, b;
cin >> a >> b;
long long d = b - a;
if (d == 0) {
cout << 0 << "\n"; // đã bằng nhau
} else if (d > 0) {
// Cộng một số lẻ d được ngay nếu d lẻ; nếu d chẵn thì cộng 1 rồi cộng d-1 (hai bước)
cout << (d % 2 == 1 ? 1 : 2) << "\n";
} else {
long long e = -d;
// Trừ một số chẵn e được ngay nếu e chẵn; nếu e lẻ thì cộng 1 rồi trừ e+1 (hai bước)
cout << (e % 2 == 0 ? 1 : 2) << "\n";
}
}
return 0;
}
Bình luận