結果

問題 No.195 フィボナッチ数列の理解(2)
ユーザー 37zigen37zigen
提出日時 2016-05-05 14:27:55
言語 Java21
(openjdk 21)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 125 ms
54,656 KB
testcase_01 AC 132 ms
54,572 KB
testcase_02 AC 134 ms
54,868 KB
testcase_03 AC 135 ms
54,788 KB
testcase_04 AC 101 ms
52,356 KB
testcase_05 AC 138 ms
54,904 KB
testcase_06 AC 137 ms
54,780 KB
testcase_07 AC 135 ms
54,624 KB
testcase_08 AC 135 ms
54,776 KB
testcase_09 AC 141 ms
54,564 KB
testcase_10 AC 119 ms
54,928 KB
testcase_11 AC 139 ms
55,136 KB
testcase_12 AC 139 ms
54,792 KB
testcase_13 AC 138 ms
54,932 KB
testcase_14 AC 139 ms
54,748 KB
testcase_15 AC 139 ms
54,812 KB
testcase_16 AC 119 ms
54,012 KB
testcase_17 AC 142 ms
54,760 KB
testcase_18 AC 121 ms
54,180 KB
testcase_19 AC 140 ms
54,760 KB
testcase_20 AC 124 ms
54,364 KB
testcase_21 AC 141 ms
55,156 KB
testcase_22 AC 108 ms
52,876 KB
testcase_23 AC 143 ms
54,720 KB
testcase_24 AC 122 ms
54,172 KB
権限があれば一括ダウンロードができます

ソースコード

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