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.

Tác giả: 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";
    }

}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.