Untitled

mail@pastecode.io avatar
unknown
plain_text
3 days ago
2.3 kB
4
Indexable
Never
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define AboTaha_on_da_code ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define X first
#define Y second

const int dx[8]={0, 0, 1, -1, 1, -1, -1, 1};
const int dy[8]={1, -1, 0, 0, 1, -1, 1, -1};
const double EPS = 1e-8;
const int mod = 1e9+7; // 1e9+7, 998244353
const int phi = 1e9+6; // 1e9+6, 998244352
// BEFORE coding are you sure you understood the statement correctly?
// PLEASE do not forget to read the sample explanation carefully.
// WATCH out for overflows & RTs in general.
// TEST your idea or code on the corner cases.
// ANALYZE each idea you have thoroughly.

void burn(int tc) {
    int a, b, k; cin >> a >> b >> k;
    priority_queue <pair<double, int>, vector <pair<double, int>>, greater<>> pq;
    pq.push({0, a});
    vector <int> par(max(a, b)*5, -1);
    vector <double> cost(max(a, b)*5, -EPS);
    cost[a] = 0;
    while(!pq.empty()) {
        auto [lg, cur] = pq.top(); pq.pop();
        if (cur == b) break;
        if (cost[cur] < lg) continue;
        int id = 0;
        for (auto ncur : {cur-1, cur+1, cur*k}) {
            if (ncur < 1) continue;
            if (id == 2 && (2*b+cur)/cur < k) break;
            id++;
            if (cost[ncur] == -EPS || cost[ncur] > lg+log(ncur)) {
                cost[ncur] = lg+log(ncur);
                pq.push({cost[ncur], ncur});
                par[ncur] = cur;
            }
        }
    }
    vector <int> ans;
    int cur = b;
    while(cur != a) {
        ans.push_back(cur);
        cur = par[cur];
    }
    reverse(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for (auto &i : ans) cout << i << '\n';
}

int main()
{
    AboTaha_on_da_code

//    freopen("cheat.in", "r", stdin);
//    freopen("output.txt", "w", stdout);

    int T = 1; cin >> T;

    for (int i = 1; i <= T; i++) {
//        cout << "Case " << i << ": ";
        burn(i);
        cout << '\n';
    }
    return (0-0);
}
Leave a Comment