結果
問題 | No.195 フィボナッチ数列の理解(2) |
ユーザー |
|
提出日時 | 2016-08-26 10:08:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,816 bytes |
コンパイル時間 | 1,938 ms |
コンパイル使用メモリ | 177,504 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-08 04:01:38 |
合計ジャッジ時間 | 2,716 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i)) #define rep(i,j) FOR(i,0,j) #define each(x,y) for(auto &(x):(y)) #define mp make_pair #define all(x) (x).begin(),(x).end() #define debug(x) cout<<#x<<": "<<(x)<<endl #define smax(x,y) (x)=max((x),(y)) #define smin(x,y) (x)=min((x),(y)) #define MEM(x,y) memset((x),(y),sizeof (x)) #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vll; int main(){ const int R = 44, INF = INT_MAX; vi a(R), b(R), xyz; set<int> st; int x, y, z = -1, d, s, t, u, A, B; rep(i, 3)cin >> x, st.insert(x); xyz = vi(all(st)); a[1] = b[2] = 1; FOR(i, 3, R){ a[i] = a[i - 1] + a[i - 2]; b[i] = b[i - 1] + b[i - 2]; } if(sz(xyz) == 1){ if(xyz[0] == 1){ puts("1 1"); return 0; } else{ xyz = vi{1,xyz[0]}; } } x = xyz[0], y = xyz[1]; if(sz(xyz) == 3)z = xyz[2]; pii ans(INF, INF); FOR(i, 1, R)FOR(j, 1, R)if(i!=j){ d = a[i] * b[j] - b[i] * a[j]; assert(d); s = b[j] * x - b[i] * y; t = -a[j] * x + a[i] * y; if(s%d || t%d)continue; A = s / d; B = t / d; if(A <= 0 || B <= 0)continue; if(sz(xyz) == 2){ smin(ans, mp(A, B)); } else{ s = A, t = B; if(s == z || t == z){ smin(ans, mp(A, B)); continue; } while(s + t <= z){ u = s + t; if(u == z) smin(ans, mp(A, B)); s = t; t = u; } } } tie(A, B) = ans; if(A == INF)puts("-1"); else printf("%d %d\n", A, B); }