結果

問題 No.195 フィボナッチ数列の理解(2)
ユーザー 37zigen37zigen
提出日時 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));}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0