Hướng dẫn giải của Bedao Regular Contest 01 - EXP
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.
Tác giả:
Dễ thấy vì ~X~ và ~Y~ đều là các số thuộc đoạn ~[0,10^{18}]~ nên ta có thể dùng hàm pow của C++ để tính nhưng làm như vậy thì độ phức tạp rất lớn. Ta có thể giảm độ phức tạp bằng cách so sánh các số mũ của ~10~ ( lấy các B của X và Y so sánh )
- Nếu ~Bx > By~ thì ta có ~Bx = Bx - By~ và ~By = 0~.
- Nếu ~Bx < By~ thì ta có ~Bx = 0~ và ~By = By - Bx~.
- Nếu ~Bx = By~ thì ta có ~Bx = 0~ và ~By = 0~ thì ta chỉ cần so sánh Ax * pow(10,Bx) và Ay * pow(10,By) vì ~Bx~ và ~By~ đều được giảm nên độ phức tạp không còn quá lớn.
Lưu ý: Ta phải xử lý trường hợp số ~A~ của ~X~ hoặc ~Y = 0~ vì khi ta nhân cho ~0~ thì số đó luôn là số bé nhất
Code mẫu
/*#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,fma")*/ // only when really needed /* GNU G++17 7.3.0: No long long for faster code GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */ #include <bits/stdc++.h> #define for1(i,a,b) for (int i = a; i <= b; i++) #define for2(i,a,b) for (int i = a; i >= b; i--) #define int long long #define sz(a) (int)a.size() #define pii pair<int,int> #define pb push_back /* __builtin_popcountll(x) : Number of 1-bit __builtin_ctzll(x) : Number of trailing 0 */ #define PI 3.1415926535897932384626433832795 #define INF 1000000000000000000 #define MOD 1000000007 #define MOD2 1000000009 #define EPS 1e-6 using namespace std; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("cf.inp", "r", stdin); // freopen("cf.out", "w", stdout); int t; cin >> t; while (t--) { int a, c; cin >> a; if (a > 0) { int b; cin >> b; while (b--) a *= 10; } else { string b; cin >> b; } cin >> c; if (c > 0) { int d; cin >> d; while (d--) c *= 10; } else { string d; cin >> d; } if (a < c) cout << "X < Y\n"; else if (a == c) cout << "X = Y\n"; else cout << "X > Y\n"; } }
Bình luận