結果

問題 No.195 フィボナッチ数列の理解(2)
ユーザー 37zigen37zigen
提出日時 2016-05-05 14:27:55
言語 Java21
(openjdk 21)
結果
AC  
実行時間 174 ms / 5,000 ms
コード長 2,221 bytes
コンパイル時間 3,111 ms
コンパイル使用メモリ 82,876 KB
実行使用メモリ 55,368 KB
最終ジャッジ日時 2024-04-15 13:11:02
合計ジャッジ時間 7,757 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 168 ms
55,156 KB
testcase_01 AC 166 ms
54,808 KB
testcase_02 AC 168 ms
55,224 KB
testcase_03 AC 166 ms
55,132 KB
testcase_04 AC 141 ms
54,308 KB
testcase_05 AC 166 ms
54,872 KB
testcase_06 AC 164 ms
54,872 KB
testcase_07 AC 174 ms
54,948 KB
testcase_08 AC 168 ms
54,992 KB
testcase_09 AC 166 ms
54,888 KB
testcase_10 AC 170 ms
55,368 KB
testcase_11 AC 167 ms
55,128 KB
testcase_12 AC 171 ms
55,004 KB
testcase_13 AC 170 ms
55,132 KB
testcase_14 AC 167 ms
55,024 KB
testcase_15 AC 166 ms
55,004 KB
testcase_16 AC 138 ms
54,088 KB
testcase_17 AC 163 ms
55,056 KB
testcase_18 AC 139 ms
54,364 KB
testcase_19 AC 165 ms
55,056 KB
testcase_20 AC 141 ms
54,216 KB
testcase_21 AC 164 ms
54,904 KB
testcase_22 AC 139 ms
54,352 KB
testcase_23 AC 165 ms
54,924 KB
testcase_24 AC 143 ms
54,332 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