CodeForces - 305B Continued Frac
2017-01-18 本文已影响0人
Cyril1317
1、题目大意
给一个高度n, 给一个分数, 给一组数据,看数据按照题目给出的规则能不能推成题目所给的分数
a1 = 1/(a2 + 1/(a3+1/..)))
2、输入输出数据分析
9 4 //第一行依次为分子p , 与分母q(1 ≤ q ≤ p ≤ 10^18)
2 //深度n
2 4//推导过程中的数据,其实就是从第二数据开始,把其作为分母分子恒为1
YES //(2 + 1/4) = 9/4
9 4
3
2 3 1
YES//(2+ 1/(3+1/1)) = (2 + (1/4))= 9/4
9 4
3
1 2 4
NO// (1 + 1/(2+(1/4))) = (1 + 4/9) = 13/9 ≠ 9/4
4、代码分析
我的思路是用题目所给的目的分数一次减去处理好个数的输入的数据,看最终结果是否为0,如果是输出YES,否则输出NO
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include<bits/stdc++.h>
using namespace std;
long long d[111];
long long flag, x, t, n, i, mol, den, dep, flag1, temp;
int main()
{
while(scanf("%I64d%I64d", &mol, &den)!=EOF && mol>=1 && den>=1)//mol分子, den分母
{
flag = 0;//判断标记
scanf("%I64d", &dep);//dep深度
for(i = 1; i <= dep; i++)
scanf("%I64d", &d[i]);
for(i = 1; i <= dep; i++)
{
if(den == 0 || (mol/den) < d[i])//如果分母为0或者分数比输入的小,不符合,排除
{
flag = 1;
break;
}
mol -= den * d[i];//同分相减
temp = mol;//倒转分子分母互换
mol = den;
den = temp;
}
if(den == 0 && flag==0) printf("YES\n");//输出
else printf("NO\n");
}
return 0;
}
PS.
这题数据大,要用long long