Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- using namespace __gnu_pbds;
- using namespace std;
- #define int long long
- using ll = long long;
- using ld = long double;
- const int N = 1000;
- const int N2 = 3e5 * 33;
- const int C = 10000;
- const ld inf_ld = 1e17;
- const int inf = 1e9;
- void solve() {
- int n;
- cin >> n;
- vector<int> dp (n + 1, inf);
- vector<int> pr(n + 1, -1);
- dp[1] = 0;
- for (int i = 2; i <= n; ++i) {
- dp[i] = dp[i - 1] + 1;
- pr[i] = i - 1;
- if (i % 2 == 0 && dp[i] > dp[i / 2] + 1) {
- dp[i] = min(dp[i], dp[i / 2] + 1);
- pr[i] = i / 2;
- }
- if (i % 3 == 0 && dp[i] > dp[i / 3] + 1) {
- dp[i] = min(dp[i], dp[i / 3] + 1);
- pr[i] = i / 3;
- }
- }
- cout << dp[n] << '\n';
- vector<int> res;
- while (n != -1) {
- res.push_back(n);
- n = pr[n];
- }
- reverse(res.begin(), res.end());
- for (auto &x : res) cout << x << ' ';
- }
- signed main(){
- ios_base ::sync_with_stdio(false);
- cin.tie(nullptr);
- int test = 1;
- //cin >> test;
- while (test--) {
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
