#include using namespace std; using int64 = long long; using i128 = __int128_t; const int64 LIM = 1'000'000'000'000LL; const int MAX_DEPTH = 35; // 単純 BFS で現実的に耐えられる限界付近 /* キー圧縮 ───────────── */ static inline i128 pack(int64 a, int64 b){ return (i128(a)<<64) | (uint64_t)b; } /* 探索ノード ─────────── */ struct Node{ int64 pre, cur; i128 par; // 親のキー(root は -1) uint8_t depth; // root からの深さ bool hasZ; // ここまでに Z を見たか }; /* 片側フロンティアを 1 層広げる */ void expand_layer(queue& q, unordered_map& mp, int64 Z) { size_t layer_sz = q.size(); while(layer_sz--){ i128 k = q.front(); q.pop(); Node nd = mp[k]; int64 a = nd.pre, b = nd.cur; int64 nxt[2] = {a + b, llabs(a - b)}; for(int t=0;t<2;++t){ int64 c = nxt[t]; if(c<0 || c>LIM) continue; i128 nk = pack(b,c); if(mp.count(nk)) continue; mp.emplace(nk, Node{b,c,k, uint8_t(nd.depth+1), nd.hasZ || (c==Z)}); q.push(nk); } } } /* 復元して出力 */ void output_path(i128 meetL, i128 meetR, const unordered_map& L, const unordered_map& R) { vector left, right; /* 左列:cur を取りながら root へ */ for(i128 k=meetL; k!=-1; k=L.at(k).par) left.push_back(L.at(k).cur); reverse(left.begin(), left.end()); /* 右列:cur を取りながら root へ。ただし重複する q を除く */ bool first = true; for(i128 k=meetR; k!=-1; k=R.at(k).par){ if(first){ // (q,r) の r だけ right.push_back(R.at(k).cur); first=false; }else{ // 以降は pre を採用 right.push_back(R.at(k).pre); } } /* 結合して表示 */ left.insert(left.end(), right.begin(), right.end()); cout<>X>>Y>>Z)) return 0; /* 長さ3で終了? */ if(llabs(X-Y)==Z){ cout<<3<<"\n"< L, R; queue qL, qR; int64 dL = (X==0?1:0); int64 dR = (Y==0?1:0); i128 kL = pack(dL,X); i128 kR = pack(Y,dR); L.emplace(kL, Node{dL,X,-1,0,(dL==Z)||(X==Z)}); R.emplace(kR, Node{Y,dR,-1,0,(Y==Z)||(dR==Z)}); qL.push(kL); qR.push(kR); /* 双方向 BFS ---------------------------------------------------- */ for(int depth=1; depth<=MAX_DEPTH; ++depth){ /* 小さい方のフロンティアを拡張 */ if(qL.size() <= qR.size()){ expand_layer(qL,L,Z); }else{ expand_layer(qR,R,Z); } /* 衝突検査:小さい map から大きい map へ */ const auto &S = (L.size() < R.size()) ? L : R; const auto &T = (L.size() < R.size()) ? R : L; for(const auto &kv : S){ const Node &nd = kv.second; // (p,q) int64 p = nd.pre, q = nd.cur; /* r は p±q の 2 通りだけ */ int64 cand[2] = { llabs(p-q), p+q }; for(int t=0;t<2;++t){ int64 r = cand[t]; if(r<0 || r>LIM) continue; auto it = T.find(pack(q,r)); if(it==T.end()) continue; const Node &nd2 = it->second; // (q,r) if(!(nd.hasZ || nd2.hasZ || q==Z || r==Z)) continue; /* 左右どちらが S/T かで meetL/meetR を決める */ i128 meetL, meetR; if(&S==&L){ meetL = kv.first; meetR = it->first; } else { meetL = it->first; meetR = kv.first; } output_path(meetL, meetR, L, R); return 0; } } } cout<<-1<<"\n"; return 0; }