Hướng dẫn giải của [2526 KSCUM TT2] Câu 1: TANGDV
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 hai số nguyên dương a, b. Mỗi bước được thay a bằng a + b hoặc b bằng a + b. Tìm số bước ít nhất để a hoặc b lớn hơn n (T truy vấn).
Sub 1: Vét cạn BFS — ~O(n^2 · T)~
Coi mỗi trạng thái là cặp (a, b) và duyệt theo chiều rộng (BFS) từ (a, b), mỗi trạng thái sinh 2 trạng thái con. Dừng khi một trong hai số vượt n. Chỉ lưu các trạng thái có cả hai số không vượt n nên số trạng thái tối đa khoảng n^2. Đúng nhưng chậm khi n lớn.
Kết quả chấm: 5/20 (SUB ok 5/20, TLE 15, WA 0)
#include <bits/stdc++.h>
using namespace std;
// Vet can: BFS tren cap (a, b). Moi buoc co 2 lua chon: a += b hoac b += a.
// Dung khi max(a, b) > n. Chi luu cac trang thai co ca a, b <= n (vi neu co gia tri > n thi da dung).
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("TANGDV.INP", "r")) { freopen("TANGDV.INP", "r", stdin); freopen("TANGDV.OUT", "w", stdout); }
int T;
cin >> T;
while (T--) {
long long a, b, n;
cin >> a >> b >> n;
// dist[x][y] = so buoc de dat (x, y), x,y <= n
vector<vector<int>> dist(n + 1, vector<int>(n + 1, -1));
queue<pair<long long, long long>> q;
long long ans = -1;
if (max(a, b) > n) ans = 0;
else {
dist[a][b] = 0;
q.push({a, b});
while (!q.empty() && ans < 0) {
auto [x, y] = q.front(); q.pop();
// 2 phep bien doi
long long nx[2] = {x + y, x};
long long ny[2] = {y, y + x};
for (int k = 0; k < 2 && ans < 0; k++) {
long long u = nx[k], v = ny[k];
// Hai cach: (x+y, y) va (x, x+y)
if (u > n || v > n) { ans = dist[x][y] + 1; break; }
if (dist[u][v] < 0) {
dist[u][v] = dist[x][y] + 1;
q.push({u, v});
}
}
}
}
cout << ans << "\n";
}
return 0;
}
Sub 2: Luôn cộng số lớn vào số nhỏ — ~O(log n · T)~
Mỗi bước nên làm số lớn hơn tăng nhanh nhất, tức cộng số lớn vào số nhỏ (kiểu dãy Fibonacci). Vì tổng hai số là giá trị lớn nhất có thể đạt được sau một bước, cách này cho số bước ít nhất. Số bước chỉ khoảng log n nên chạy rất nhanh. Lưu ý giá trị có thể lên tới khoảng 2n nên dùng long long.
Kết quả chấm: 20/20 (PASS 20/20)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("TANGDV.INP", "r")) { freopen("TANGDV.INP", "r", stdin); freopen("TANGDV.OUT", "w", stdout); }
int T;
cin >> T;
while (T--) {
long long a, b, n;
cin >> a >> b >> n;
int buoc = 0;
// Luon cong so lon vao so nho (Fibonacci-like): day la cach tang nhanh nhat.
// Moi buoc, max moi = tong hai so, nen tang gia tri lon nhat toi da.
while (max(a, b) <= n) {
if (a < b) a += b; // cong b vao a
else b += a; // cong a vao b
buoc++;
}
cout << buoc << "\n";
}
return 0;
}
Bình luận