Hướng dẫn giải của [200 đề thầy Đức] Bài 78: Cây gậy đũa thần của Harry Portter
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
Từ số ~x~ có hai phép: nếu ~a~ chẵn thì đổi thành ~3a/2~, nếu ~a > 1~ thì đổi thành ~a-1~. Hỏi có biến ~x~ thành ~y~ được không.
Sub 1: BFS trên các giá trị — ~O(C)~ mỗi bộ dữ liệu, dùng khi ~x, y \le 100~
Duyệt theo chiều rộng các giá trị trong đoạn ~[1, 10000]~ xuất phát từ ~x~. Gặp ~y~ thì YES. Với ~x~ và ~y~ nhỏ, giới hạn 10000 đủ rộng để không bỏ sót đường đi.
Nếu chỉ nộp sub này: đúng 2/21 test.
Sub 2: Công thức tập đạt được — ~O(1)~, dùng khi mọi trường hợp còn lại
Từ ~x~ luôn đến được mọi giá trị trong ~[1, M(x)]~. Với ~x = 1~ thì ~M = 1~; với ~x = 2~ hoặc ~3~ thì ~M = 3~; với ~x \ge 4~ thì ~M~ không giới hạn, vì từ ~a \ge 4~ phép 1 luôn cho giá trị lớn hơn ~a~ và phép 2 đi xuống được. Vậy đáp án YES khi ~x \ge 4~ hoặc ~y \le M(x)~.
Nếu chỉ nộp sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
Chương trình đọc ~T~ rồi từng cặp ~x, y~. Nếu ~x, y \le 100~ thì gọi sub1, ngược lại gọi sub2. Đề có bảng ví dụ bị lệch hàng, nhưng đáp án được đối chiếu theo đúng thứ tự từng bộ dữ liệu.
#include <bits/stdc++.h>
using namespace std;
long long X, Y; // so ban dau x va so can dat y
// Sub 1: vet can. BFS tren cac gia tri trong [1, 10000], bat dau tu X.
// Tu v co the sang 3v/2 (neu v chan) hoac v-1 (neu v > 1). Dung khi X, Y <= 100.
void sub1() {
const int CAP = 10000;
vector<char> vis(CAP + 1, 0);
queue<long long> q;
q.push(X);
vis[X] = 1;
while (!q.empty()) {
long long v = q.front();
q.pop();
vector<long long> nxt;
if (v % 2 == 0) nxt.push_back(3 * v / 2);
if (v > 1) nxt.push_back(v - 1);
for (long long w : nxt)
if (w >= 1 && w <= CAP && !vis[w]) {
vis[w] = 1;
q.push(w);
}
}
cout << (vis[Y] ? "YES" : "NO") << "\n";
}
// Sub 2: cong thuc. Tu x chi dat duoc cac gia tri trong [1, M(x)]:
// x = 1: M = 1 (khong lam gi duoc); x = 2 hoac 3: M = 3;
// x >= 4: M khong gioi han, vi 3a/2 luon lon hon a voi moi a >= 4.
void sub2() {
bool ok;
if (X >= 4) ok = true;
else if (X == 1) ok = (Y == 1);
else ok = (Y <= 3);
cout << (ok ? "YES" : "NO") << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> X >> Y;
if (X <= 100 && Y <= 100) sub1();
else sub2();
}
return 0;
}
Bình luận