結果

問題 No.3162 Five Two Three
ユーザー Rubikun
提出日時 2025-05-23 20:36:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 50 ms / 1,523 ms
コード長 5,162 bytes
コンパイル時間 2,243 ms
コンパイル使用メモリ 207,424 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-23 20:37:28
合計ジャッジ時間 13,077 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 187
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef __int128_t ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005;
const ll INF=15LL<<55;

//int128

//https://kopricky.github.io/code/Misc/int128.html

// __int128の入出力

using LL = __int128;
istream& operator>>(istream& is, LL& v)
{
    string s;
    is >> s;
    v = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (isdigit(s[i])) { v = v * 10 + s[i] - '0'; }
    }
    if (s[0] == '-') { v *= -1; }
    return is;
}

ostream& operator<<(ostream& os, const LL& v)
{
    if (v == 0) { return (os << "0"); }
    LL num = v;
    if (v < 0) {
        os << '-';
        num = -num;
    }
    string s;
    for (; num > 0; num /= 10) { s.push_back((char)(num % 10) + '0'); }
    reverse(s.begin(), s.end());
    return (os << s);
}


LL abss(LL x){
    return max(x,-x);
}

void check4(vl S){
    for(int i=1;i<=2;i++){
        if(abss(S[i-1]-S[i+1])!=S[i]) return;
    }
    cout<<4<<endl;
    for(ll x:S) cout<<x<<" ";
    cout<<endl;
    exit(0);
}

void check5(vl S){
    for(int i=1;i<=3;i++){
        if(abss(S[i-1]-S[i+1])!=S[i]) return;
    }
    cout<<5<<endl;
    for(ll x:S) cout<<x<<" ";
    cout<<endl;
    exit(0);
}

ll dpa[MAX],dpb[MAX];

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    dpa[1]=1;
    dpa[2]=1;
    
    dpb[1]=1;
    dpb[2]=2;
    for(int i=3;i<=70;i++){
        dpa[i]=dpa[i-1]+dpa[i-2];
        dpb[i]=dpb[i-1]+dpb[i-2];
        //cout<<i<<" "<<dpa[i]<<" "<<dpb[i]<<endl;
    }
    
    ll X,Y,Z;cin>>X>>Y>>Z;
    
    if(abss(X-Y)==Z){
        cout<<3<<endl;
        cout<<X<<" "<<Z<<" "<<Y<<endl;
        return 0;
    }
    check4({X,Z,abss(X+Z),Y});
    check4({X,Z,abss(X-Z),Y});
    check4({X,abss(Y+Z),Z,Y});
    check4({X,abss(Y-Z),Z,Y});
    
    if(X==0&&Y&&Z==0){
        cout<<5<<endl;
        cout<<0<<" "<<Y<<" "<<Y<<" "<<0<<" "<<Y<<endl;
        return 0;
    }
    if(X&&Y==0&&Z==0){
        cout<<5<<endl;
        cout<<X<<" "<<0<<" "<<X<<" "<<X<<" "<<0<<endl;
        return 0;
    }
    
    vl ans(300);
    
    for(int q=0;q<2;q++){
        for(ll pos=1;pos<=70;pos++){
            for(ll alen=pos+1;alen<=70;alen++){
                for(ll blen=1;blen<=70;blen++){
                    if(pos==1&&blen==1) continue;
                    //if(alen==2) continue;
                    
                    ll x=dpa[pos],y=dpb[pos];
                    ll u=dpa[alen],v=dpb[alen];
                    
                    LL di=(LL)(Z)*u-(LL)(X)*x;
                    LL ke=(LL)(y)*u-(LL)(v)*x;
                    if(ke==0) continue;
                    if(ke<0){
                        di*=-1;
                        ke*=-1;
                    }
                    if(di%ke) continue;
                    LL b=di/ke;
                    LL a=((LL)(Z)-y*b)/x;
                    if(a*x!=Z-y*b) continue;
                    
                    ll U=a+b;
                    
                    vl S;
                    for(int i=2;i<=alen;i++) S.pb(a*dpa[i]+b*dpb[i]);
                    reverse(all(S));
                    
                    
                    
                    x=dpa[1];y=dpb[1];
                    u=dpa[blen];v=dpb[blen];
                    
                    di=(LL)(U)*u-(LL)(Y)*x;
                    ke=(LL)(y)*u-(LL)(v)*x;
                    if(ke==0) continue;
                    if(ke<0){
                        di*=-1;
                        ke*=-1;
                    }
                    if(di%ke) continue;
                    b=di/ke;
                    a=((LL)(U)-y*b)/x;
                    if(a*x!=U-y*b) continue;
                    
                    for(int i=1;i<=blen;i++) S.pb(a*dpa[i]+b*dpb[i]);
                    
                    if(q) reverse(all(S));
                    
                    bool ok=true;
                    for(int i=1;i<si(S)-1;i++){
                        ok&=(abss(S[i-1]-S[i+1])==S[i]);
                    }
                    
                    if(!ok) continue;
                    
                    if(si(ans)>si(S)){
                        ans=S;
                    }
                }
            }
        }
        
        swap(X,Y);
    }
    
    
    if(si(ans)!=300){
        cout<<si(ans)<<"\n";
        for(ll x:ans) cout<<x<<" ";
        cout<<"\n";
    }else{
        cout<<-1<<"\n";
    }
}
0