oj.uz

Submission #4993

# Submission time Handle Problem Language Result Execution time Memory
4993 2014-01-24T12:53:09 Z lingxiang 분수 (KPI13_fractions) C++
0 / 1
 0 ms 1088 KB 
/*
construct with farey sequence
*/

#include<stdio.h>
#include<string.h>

long long int a,b,c,d;
long long int fn1=0,fd1=1,fn2=1,fd2=1;
long long int numeric;
int T;

void input(){
	scanf("%d",&T);
}

void solve(){
	for(int i=0;i<T;i++){
		fn1=0,fn2=1,fd1=1,fd2=1;
		scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
		if(a/b==c/d){
			numeric=a/b;
			a=a-b*numeric;
			c=c-d*numeric;
		}
		else{
			printf("%lld 1\n",a/b+1);
			continue;
		}
		while(1){
			//puts("*");
			long long int next_fn=fn1+fn2;
			long long int next_fd=fd1+fd2;
			if(next_fn*b<=next_fd*a){
				fn1=next_fn;
				fd1=next_fd;
			}
			else if(next_fd*c<=next_fn*d){
				fn2=next_fn;
				fd2=next_fd;
			}
			else{
				printf("%lld %lld\n",next_fn+next_fd*numeric,next_fd);
				break;
			}
		}
	}
}

void output(){

}

int main(){
	input();
	solve();
	output();
	return 0;
}

Subtask #1
0.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1088 KB Output is correct
2 Correct 0 ms 1088 KB Output is correct
3 Incorrect 0 ms 1088 KB Output isn't correct
4 Halted 0 ms 0 KB -