Editorial for Bedao Regular Contest 01 - EXP
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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"; } }
Comments