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.

Author: bedao

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

Please read the guidelines before commenting.


There are no comments at the moment.