結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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>(){
				@Override
				public 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>(){
				@Override
				public 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>(){
				@Override
				public 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));}
}
0