結果
問題 | No.195 フィボナッチ数列の理解(2) |
ユーザー | bonntanname0316 |
提出日時 | 2020-06-05 19:16:11 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 2,421 bytes |
コンパイル時間 | 2,267 ms |
コンパイル使用メモリ | 183,764 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-05-09 16:23:48 |
合計ジャッジ時間 | 2,520 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 1 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 1 ms
5,376 KB |
testcase_18 | AC | 1 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 2 ms
5,376 KB |
testcase_24 | AC | 1 ms
5,376 KB |
ソースコード
#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; P NG=mp(-1,-1); P renritsu(ll x, ll y, ll n, ll m){ if(n==0){ ll a=x; ll K3=y-A[m]*a; if(K3<B[m]) return NG; if(K3%B[m]) return NG; return mp(a,K3/B[m]); } if(n==1){ ll b=x; ll K3=y-B[m]*b; if(K3<A[m]) return NG; if(K3%A[m]) return NG; return mp(K3/A[m],b); } ll K=B[n]*A[m]-B[m]*A[n]; ll K1=A[m]*x-A[n]*y; if(K1<0) {K1*=(-1); K*=(-1);} if(K<=0) return NG; if(K1<K) return NG; if(K1%K) return NG; ll b=K1/K; ll K2=x-B[n]*b; if(K2<0) return NG; if(K2%A[n]) return NG; ll a=K2/A[n]; return mp(a,b); } vector<P> REN(ll x, ll y){ if(x>y) return REN(y,x); vector<P> ret; if(x==y) return ret; rep(i,N-1) REP(j,i+1,N){ P kari=renritsu(x,y,i,j); if(kari.first>0) ret.pb(kari); } sort(ALL(ret)); return ret; } P Solve(){ if(X==Z) { if(X==1) return mp(1,1); vector<P> d=REN(1,X); return d[0]; } vector<P> d=REN(X,Z); rep(i,d.size()){ rep(j,N){ ll AA=d[i].first, BB=d[i].second; if(AA*A[j]+BB*B[j]==Y) return d[i]; if(AA*A[j]+BB*B[j]>Y) break; } } return NG; } int main(){ REP(i,2,120){ A.pb(A[i-1]+A[i-2]); B.pb(B[i-1]+B[i-2]); if(A[i]+B[i]>1e9) 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; }