Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <iterator>
- #include <unordered_map>
- #include <functional>
- #include <unordered_set>
- #include <string>
- #include <set>
- #include <utility>
- #include <stack>
- void p(std::vector<int> v) {
- for (auto i : v) {
- std::cout << i << " ";
- }
- std::cout << '\n';
- }
- int main() {
- int N;
- std::cin >> N;
- std::vector<long long> result(N, 100000000);
- result[0] = 1;
- std::vector<long long> ways(N, 0);
- for (long long i = 1; i < N; i++) {
- if (result[i] >= result[i - 1] + 1) {
- result[i] = result[i - 1] + 1;
- ways[i] = i;
- }
- if ((i + 1) % 3 == 0 && (result[i] >= result[(i + 1) / 3 - 1] + 1)) {
- result[i] = result[(i + 1) / 3 - 1];
- ways[i] = (i + 1) / 3;
- }
- if ((i + 1) % 2 == 0 && (result[i] >= result[(i + 1) / 2 - 1] + 1)) {
- result[i] = result[(i + 1) / 2 - 1];
- ways[i] = (i + 1) / 2;
- }
- }
- std::vector<long long> res;
- int M = ways[N - 1];
- int D = N - 1;
- while (D + 1 != 1) {
- res.push_back(D + 1);
- D = ways[D] - 1;
- }
- std::cout << res.size() << '\n';
- std::cout << 1;
- for (int i = res.size() - 1; i > -1; i--) {
- std::cout << " " << res[i];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement