Hướng dẫn giải của Chia đều
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Editorial for ptit046: Chia đều
Hiểu bài toán
Cho hai số nguyên dương m, n (1 ≤ m, n ≤ 10^9) representing volumes of two bottles. Jarvan có thể thực hiện thao tác chia một chai cho 2, 3, hoặc 5. Cụ thể, nếu chia cho 2 thì Jarvis uống 1/2, để lại 1/2; nếu chia cho 3 thì để lại 2/3; nếu chia cho 5 thì để lại 4/5. Mục tiêu là làm cho hai chai có thể tích bằng nhau. Tìm số thao tác ít nhất cần thực hiện, hoặc in ra -1 nếu không thể.
Các cách tiếp cận
Cách Phân tích thừa số nguyên tố (Prime Factorization)
#include <bits/stdc++.h>
using namespace std;
tuple<long long, int, int, int> factorize(long long x) {
int c2 = 0, c3 = 0, c5 = 0;
while (x % 2 == 0) { x /= 2; c2++; }
while (x % 3 == 0) { x /= 3; c3++; }
while (x % 5 == 0) { x /= 5; c5++; }
return {x, c2, c3, c5};
}
int main() {
long long a, b;
cin >> a >> b;
auto [coreA, c2A, c3A, c5A] = factorize(a);
auto [coreB, c2B, c3B, c5B] = factorize(b);
if (coreA != coreB) {
cout << -1 << endl;
} else {
long long ans = abs(c2A - c2B) + abs(c3A - c3B) + abs(c5A - c5B);
cout << ans << endl;
}
return 0;
}
- Time Complexity: O(log(max(m, n)))
- Space Complexity: O(1)
Bài toán yêu cầu làm hai số bằng nhau bằng cách chia cho 2, 3, 5. Các phép chia này tương ứng với việc bớt đi các thừa số nguyên tố 2, 3, 5 trong phân tích thừa số nguyên tố của số đó. Để hai số m và n bằng nhau, phần 'lõi' (sau khi loại bỏ hết các thừa số 2, 3, 5) của chúng phải giống nhau. Nếu phần lõi khác nhau, không thể thực hiện được (trả về -1). Nếu phần lõi giống nhau, số thao tác tối thiểu chính là tổng số lần chia cần thiết để đưa số có nhiều thừa số hơn về bằng số có ít thừa số hơn. Do ta có thể chia bất cứ lúc nào, số thao tác chính là tổng khoảng cách tuyệt đối giữa số lượng thừa số 2, thừa số 3, và thừa số 5 của hai số.
Cách Giải thuật quy hoạch động (Dynamic Programming)
// Giải pháp này chỉ mang tính lý thuyết do độ phức tạp cao
#include <iostream>
#include <queue>
#include <set>
#include <utility>
using namespace std;
int solve(long long m, long long n) {
if (m == n) return 0;
// Sử dụng BFS để tìm đường đi ngắn nhất
// Lưu ý: Có thể dùng map để lưu visited state
// Code dưới đây là pseudocode chỉnh sửa cho ngắn gọn
queue<pair<long long, long long>> q;
set<pair<long long, long long>> visited;
q.push({m, n});
visited.insert({m, n});
int steps = 0;
while (!q.empty()) {
int size = q.size();
while (size--) {
auto [u, v] = q.front(); q.pop();
if (u == v) return steps;
// Thử chia chai u
if (u % 2 == 0) {
long long next_u = u / 2;
if (!visited.count({next_u, v})) {
visited.insert({next_u, v});
q.push({next_u, v});
}
}
if (u % 3 == 0) {
long long next_u = u / 3 * 2;
if (!visited.count({next_u, v})) {
visited.insert({next_u, v});
q.push({next_u, v});
}
}
if (u % 5 == 0) {
long long next_u = u / 5 * 4;
if (!visited.count({next_u, v})) {
visited.insert({next_u, v});
q.push({next_u, v});
}
}
// Thử chia chai v (tương tự)
// ... (code lặp lại cho v)
}
}
return -1;
}
int main() {
long long m, n;
cin >> m >> n;
cout << solve(m, n) << endl;
return 0;
}
- Time Complexity: Thường là ~O(2^k) hoặc ~O(V+E) ~O(10^9) -> Quá chậm
- Space Complexity: O(V) -> Quá lớn
Đây là cách tiếp cận mô phỏng bài toán như một bài đồ thị ngắn nhất. Mỗi trạng thái là một cặp (thể tích chai 1, thể tích chai 2). Các cạnh nối giữa các trạng thái là các phép chia được phép. Ta dùng BFS để tìm số bước ít nhất. Tuy nhiên, do thể tích lên tới 10^9, số lượng trạng thái là rất lớn, giải thuật này không khả thi về mặt thời gian và bộ nhớ.
Cách Giải thuật tham lam (Greedy)
#include <iostream>
#include <cmath>
using namespace std;
int main() {
long long m, n;
cin >> m >> n;
if (m == n) {
cout << 0 << endl;
return 0;
}
auto count_factors = [](long long x, int &c2, int &c3, int &c5) {
c2 = c3 = c5 = 0;
while (x % 2 == 0) { x /= 2; c2++; }
while (x % 3 == 0) { x /= 3; c3++; }
while (x % 5 == 0) { x /= 5; c5++; }
return x;
};
int c2_m, c3_m, c5_m;
int c2_n, c3_n, c5_n;
long long core_m = count_factors(m, c2_m, c3_m, c5_m);
long long core_n = count_factors(n, c2_n, c3_n, c5_n);
if (core_m != core_n) {
cout << -1 << endl;
} else {
cout << abs(c2_m - c2_n) + abs(c3_m - c3_n) + abs(c5_m - c5_n) << endl;
}
return 0;
}
- Time Complexity: O(log(max(m, n)))
- Space Complexity: O(1)
Giống như Approach 1, đây là cách tiếp cận hiệu quả nhất. Ta lần lượt loại bỏ các thừa số 2, 3, 5 khỏi cả hai số. Nếu phần còn lại (rest) của hai số bằng nhau, số thao tác cần thiết là tổng số lượng thừa số bị loại bỏ khác nhau. Ví dụ: m=20 (2^2 * rest=5), n=30 (23rest=5). m có 2 số 2, n có 1 số 2 và 1 số 3. Để bằng nhau: m cần chia 1 lần cho 2 (còn 10), n cần chia 1 lần cho 3 (còn 20). Sau đó m=10, n=20. M chia 1 lần cho 2 (còn 5), N chia 1 lần cho 2 (còn 10). ... Tuy nhiên, phép tính chính xác là abs(c2m - c2n) + abs(c3m - c3n) + abs(c5m - c5n).
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(log(max(m, n))) | O(1) | Phân tích thừa số nguyên tố (Prime Factorization) |
| 2 | Thường là ~O(2^k) hoặc ~O(V+E) ~O(10^9) -> Quá chậm | O(V) -> Quá lớn | Giải thuật quy hoạch động (Dynamic Programming) |
| 3 | O(log(max(m, n))) | O(1) | Giải thuật tham lam (Greedy) |
Bài học kinh nghiệm
- Bài toán quy về phân tích thừa số nguyên tố. Các phép chia 2, 3, 5 tương ứng với việc bớt đi các thừa số 2, 3, 5.
- Điều kiện tiên quyết để hai số có thể trở nên bằng nhau là phần 'lõi' (số sau khi loại bỏ hết các thừa số 2, 3, 5) của chúng phải giống nhau.
- Số thao tác tối thiểu là tổng khoảng cách tuyệt đối giữa số lượng các thừa số 2, 3, 5 của hai số.
Lỗi thường gặp
- Quên kiểm tra điều kiện hai số đã bằng nhau ngay từ đầu (đầu ra là 0).
- Thử các giải thuật mô phỏng BFS/DFS会导致Timeout do dải giá trị đầu vào quá lớn (10^9).
- Lỗi type: Sử dụng
intthay vìlong longcho các biến thể tích, dẫn đến tràn số.
Bình luận