結果
問題 | No.195 フィボナッチ数列の理解(2) |
ユーザー | 37zigen |
提出日時 | 2016-05-05 14:27:55 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 143 ms / 5,000 ms |
コード長 | 2,221 bytes |
コンパイル時間 | 2,537 ms |
コンパイル使用メモリ | 82,836 KB |
実行使用メモリ | 55,156 KB |
最終ジャッジ日時 | 2024-10-05 09:35:36 |
合計ジャッジ時間 | 6,206 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
package yukicoder;import java.util.ArrayList;import java.util.Arrays;import java.util.Comparator;import java.util.Scanner;public class Main{public static void main(String[] args)throws Exception{new Main().solve();}long[] F01;long[] F10;ArrayList<Pair> cand=new ArrayList<Pair>();void solve(){Scanner sc=new Scanner(System.in);F01=new long[100];F10=new long[100];F01[1]=1;F10[0]=1;for(int i=2;i<=60;i++){F01[i]=F01[i-1]+F01[i-2];F10[i]=F10[i-1]+F10[i-2];}int[] xs=new int[3];for(int i=0;i<3;i++)xs[i]=sc.nextInt();Arrays.sort(xs);if(xs[0]==xs[1]&&xs[1]==xs[2]){solver(1,xs[0]);cand.sort(new Comparator<Pair>(){@Overridepublic int compare(Pair o1, Pair o2) {return o1.A>o2.A?1:o1.A<o2.A?-1:o1.B>o2.B?1:o1.B<o2.B?-1:0;}});Pair p=cand.get(0);System.out.println(p.A+" "+p.B);}else if(xs[0]==xs[1]||xs[1]==xs[2]){solver(xs[0],xs[2]);cand.sort(new Comparator<Pair>(){@Overridepublic int compare(Pair o1, Pair o2) {return o1.A>o2.A?1:o1.A<o2.A?-1:o1.B>o2.B?1:o1.B<o2.B?-1:0;}});Pair p=cand.get(0);System.out.println(p.A+" "+p.B);}else{solver(xs[0],xs[1]);cand.sort(new Comparator<Pair>(){@Overridepublic int compare(Pair o1, Pair o2) {return o1.A>o2.A?1:o1.A<o2.A?-1:o1.B>o2.B?1:o1.B<o2.B?-1:0;}});for(int i=0;i<cand.size();i++){Pair p=cand.get(i);long A=p.A,B=p.B;for(int j=0;j<60;j++){if(A*F10[j]+B*F01[j]==xs[2]){System.out.println(A+" "+B);return;}}}System.out.println(-1);}}/** Fab(i)=A*F10(i)+B*F01(i)=X* Fab(j)=B*F10(j)+B*F01(j)=Y* となるようなp,qが存在する(A,B)を求める。**/void solver(int x,int y){for(int i=0;i<60;i++){for(int j=0;j<60;j++){long a=F10[i],b=F01[i],c=F10[j],d=F01[j];long det=a*d-c*b;long A=d*x-b*y;long B=-c*x+a*y;if(det==0||A%det!=0||B%det!=0)continue;if(A/det>0&&B/det>0)cand.add(new Pair(A/det,B/det));}}}class Pair{long A;long B;Pair(long A,long B){this.A=A;this.B=B;}}void tr(Object...o){System.out.println(Arrays.deepToString(o));}}