Editorial for Bedao Mini Contest 09 - WALK


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

Đầu tiên ta khởi tạo mảng ~pre[i]~ là tổng khoảng cách đi được khi thực hiện lần đi tìm thứ i ta có quy luật như sau :

  • Ta đến đi tìm lần thứ i thì sẽ đến điểm ~X + (-1)^i \times 2^{i-1}~ .
  • Ta chỉ cần tính khoảng cách giữa điểm đến lần tìm thứ ~i~ và lần thứ ~i - 1~ và cộng cho ~pre[i - 1]~.

Việc còn lại ta cần làm là chia thành 3 trường hợp:

  • Nếu ~Y < X~ đồng nghĩa với việc ta đến ~Y~ tại một lần đi tìm thứ ~i~ với ~i~ là một số lẻ.
  • Nếu ~Y > X~ đồng nghĩa với việc ta đến ~Y~ tại một lần đi tìm thứ ~i~ với ~i~ là một số chẵn.
  • Nếu ~Y = X~ ta không cần đi tìm lần nào.

Sau đó ta chỉ cần tìm ~i~ phù hợp với điều kiện trên ,bé nhất thỏa mãn khoảng cách giữa điểm đích lần đi tìm thứ ~i~ với ~X~ lớn hơn hoặc bằng khoảng cách từ ~Y~ đến ~X~.Nhưng nếu lớn hơn thì ta sẽ dừng ở ~Y~ trước khi đi đến điểm đích của lần đi tìm thứ ~i~ nên sẽ dư ra 1 đoạn nếu tính kết quả ở ~pre[i]~ , ta có thể lấy ~pre[i]~ trừ cho khoảng cách từ ~Y~ đến điểm đích đó . Khi đó nó là kết quả cuối cùng .

Code mẫu

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/

#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
*/

const long double PI = 3.1415926535897932384626433832795;
const int INF = 1000000000000000000;
const int MOD = 1000000007;
const int MOD2 = 1000000009;
const long double 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 x, y;
    cin >> x >> y;

    if (x == y) {
        cout << "0 0";
        return 0;
    }

    int cur = 1, sum = 0, p = 0, cnt = 0, lst = x;
    while (1) {
        cnt++;
        if (p) {
            if (lst <= y && x + cur >= y) {
                sum += (y - lst);
                cout << cnt << " " << sum;
                return 0;
            }
            sum += (x + cur) - lst;
            lst = x + cur;
        }
        else {
            if (lst >= y && x - cur <= y) {
                sum += (lst - y);
                cout << cnt << " " << sum;
                return 0;
            }
            sum += lst - (x - cur);
            lst = x - cur;
        }
        // cout << cur << " " << sum << "\n";
        p ^= 1;
        cur <<= 1;
    }

}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.