結果
問題 | No.195 フィボナッチ数列の理解(2) |
ユーザー | bonntanname0316 |
提出日時 | 2020-06-04 18:37:25 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,920 bytes |
コンパイル時間 | 1,795 ms |
コンパイル使用メモリ | 179,800 KB |
実行使用メモリ | 14,016 KB |
最終ジャッジ日時 | 2024-05-07 05:25:38 |
合計ジャッジ時間 | 8,716 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 1 ms
6,940 KB |
testcase_03 | AC | 1 ms
6,944 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 42 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,944 KB |
testcase_13 | AC | 190 ms
6,940 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | TLE | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
ソースコード
#include <bits/stdc++.h> #include <stdlib.h> using namespace std; typedef long long ll; typedef vector<ll> vec; typedef vector<vec> mat; typedef vector<double> Vec; typedef vector<Vec> Mat; typedef pair<ll,ll> P; typedef pair<double,ll> Pd; typedef priority_queue<P,vector<P>,greater<P>> P_queue; typedef priority_queue<Pd,vector<Pd>,greater<Pd>> Pd_queue; const ll MOD=998244353; const ll mod=1000000007; const ll INF=1e15; const double DEL=1e-3; vec dx={1,0,-1,0}; vec dy={0,1,0,-1}; #define REP(i,a,b) for(int i=(int)a;i<(int)b;i++) #define rep(i,n) REP(i,0,n) #define pb push_back #define mp make_pair #define ALL(a) a.begin(),a.end() #define SORT(a) sort(ALL(a)) #define U_ERASE(V) V.erase(unique(ALL(V)), V.end()); #define ADD(a,b) a=(a+b)%mod #define CHECK cout<<"arrived"<<endl vec A={1,0},B={0,1}; mat K={{1,1},{1,0}}; ll X,Y,Z,N; ll Solving(ll a, ll x, ll n){ if(n<=0) return -1; ll P=x-(a*A[n]); if(P<B[n]) return -1; if(P%B[n]) return -1; //cout<<a<<' '<<P/B[n]<<endl; return P/B[n]; } bool hantei(ll a, ll b, ll x, ll y){ if(x>y) return hantei(a,b,y,x); rep(i,N) { if(a*A[i]+b*B[i]==x){ REP(j,i,N){ if(a*A[j]+b*B[j]==y) return true; if(a*A[j]+b*B[j]>y) return false; } } if(a*A[i]+b*B[i]>x) return false; } return false; } P Solve(){ REP(j,1,Y+1){ for(int i=N-1;i>=0;i--) { ll A=Solving(j,Z,i); if(A>=0){ if(hantei(j,A,X,Y)) return mp(j,A); } } } return mp(-1,-1); } int main(){ REP(i,2,120){ A.pb(A[i-1]+A[i-2]); B.pb(B[i-1]+B[i-2]); if(B[i]>1e9+10) break; } N=B.size(); vec I(3); rep(i,3) cin>>I[i]; sort(ALL(I)); X=I[0]; Y=I[1]; Z=I[2]; P ans=Solve(); if(ans.first<0) cout<<-1<<endl; else cout<<ans.first<<' '<<ans.second<<endl; }