結果

問題 No.3162 Five Two Three
ユーザー TKTYI
提出日時 2025-05-06 20:43:05
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 30 ms / 1,523 ms
コード長 3,206 bytes
コンパイル時間 3,609 ms
コンパイル使用メモリ 289,040 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-05-06 20:43:21
合計ジャッジ時間 14,659 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 187
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 

int main(){
    ll X, Y, Z;
    cin >> X >> Y >> Z;
    swap(Y, Z);
    if(X + Y + Z == 0){
        cout << "3\n0 0 0" << endl;
        return 0;
    }
    
    vector<ll> fib = {0, 1};
    while(fib.back() < 1'000'000'000'000) fib.emplace_back(fib.back() + fib[fib.size() - 2]);
    int L = fib.size(); // 61

    vector<__int128> exfib;
    for(int i = L - 1; i >= 0; i--) exfib.emplace_back(fib[i]);
    for(int i = 1; i < L; i++) exfib.emplace_back(fib[i]);

    vector<ll> ans(200); 
    for(int i = 0; i < 2 * L - 2; i++){
        for(int j = i + 1; j < 2 * L - 2; j++){
            for(int k = j + 1; k < 2 * L - 2; k++){
                __int128 a, b;
                if(exfib[i] * exfib[j + 1] == exfib[j] * exfib[i + 1]){
                    __int128 det = exfib[i] * exfib[k + 1] - exfib[k] * exfib[i + 1];
                    a = X * exfib[k + 1] - Z * exfib[i + 1];
                    b = Z * exfib[i] - X * exfib[k];
                    if(a % det || b % det) continue;
                    a /= det;
                    b /= det;
                }
                else{
                    __int128 det = exfib[i] * exfib[j + 1] - exfib[j] * exfib[i + 1];
                    a = X * exfib[j + 1] - Y * exfib[i + 1];
                    b = Y * exfib[i] - X * exfib[j];
                    if(a % det || b % det) continue;
                    a /= det;
                    b /= det;
                }
                if(a * exfib[i] + b * exfib[i+1] != X) continue;
                if(a * exfib[j] + b * exfib[j+1] != Y) continue;
                if(a * exfib[k] + b * exfib[k+1] != Z) continue;
                if(ans.size() > k - i + 1){
                    vector<ll> s;
                    for(int l = i; l <= k; l++) s.emplace_back(a * exfib[l] + b * exfib[l + 1]);
                    if(*min_element(s.begin(), s.end()) >= 0) ans = s;
                }
            }
        }
    }

    for(int _ = 0; _ < 2; _++){
        exfib.insert(exfib.begin() + L, 0);
        exfib.insert(exfib.begin() + L, 1);
        exfib.insert(exfib.begin() + L, 1);
        for(int i = 0; i < exfib.size(); i++){
            for(int j = i + 1; j < exfib.size(); j++){
                for(int k = j + 1; k < exfib.size(); k++){
                    if(!exfib[i] && X) continue;
                    if(!exfib[j] && Y) continue;
                    if(!exfib[k] && Z) continue;
                    ll a;
                    if(X) a = X / exfib[i];
                    else if(Y) a = Y / exfib[j];
                    else a = Z / exfib[k];
                    if(X != a * exfib[i]) continue;
                    if(Y != a * exfib[j]) continue;
                    if(Z != a * exfib[k]) continue;
                    if(ans.size() > k - i + 1){
                        ans = {};
                        for(int l = i; l <= k; l++) ans.emplace_back(a * exfib[l]);
                    }
                }
            }
        }
    }

    if(ans.size() == 200) cout << -1 << endl;
    else{
        cout << ans.size() << endl;
        for(int i = 0; i < ans.size(); i++) cout << ans[i] << " \n"[i + 1 == ans.size()];
    }
    return 0;
}
0