| Fun With Fractions |
| Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:65536KB |
| Total submit users: 152, Accepted users: 32 |
| Problem 12878 : No special judgement |
| Problem description |
|
A rational number can be represented as the ratio of two integers, referred to as the numerator (n) and the denominator (d) and written n/d. A rational number's representation is not unique. For example the rational numbers 1/2 and 2/4 are equivalent. A rational number representation is described as "in lowest terms" if the numerator and denominator have no common factors. Thus 1/2 is in lowest terms but 2/4 is not. A rational number can be reduced to lowest terms by dividing by the greatest common divisor of n and d. |
| Input |
|
Input will consist of specifications for a series of tests. Information for
each test begins with a line containing a single integer 1 <= n < 1000
indicating how many values follow. A count of zero terminates the input. |
| Output |
|
Output should consist of one line for each test comprising the test number (formatted as shown) followed by a single space and the sum of the input number sequence. The sum should be displayed in lowest terms using mixed number format. If either the whole number part or the fractional part is zero, that part should be omitted. As a special case, if both parts are zero, the value should be displayed as a single 0. |
| Sample Input |
2 1/2 1/3 3 1/3 2/6 3/9 3 1 2/3 4,5/6 0 |
| Sample Output |
Test 1: 5/6 Test 2: 1 Test 3: 6,1/2 |
| Problem Source |
| HNU Contest |
Mean:
给你n个数，其中包含分数、整数，对这n个数求和。
analyse:
按照题目意思模拟即可，主要考察coding能力.
Time complexity：O(n)
Source code：
// K MS
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<iomanip>
#include<string>
#include<climits>
#include<cmath>
#define MAX 1005
#define LL long long
using namespace std;
int n,kase=1;
int flag[MAX];
char str[MAX][20];
void read()
{
memset(flag,0,sizeof(flag));
for(int i=1;i<=n;i++)
{
scanf("%s",str[i]);
int len=strlen(str[i]);
for(int j=0;j<len;j++)
{
if(str[i][j]==',')
{
flag[i]=1;
break;
}
else if(str[i][j]=='/')
{
flag[i]=2;
break;
}
}
}
}
int gcd(int a,int b)
{
if(b==0)
return a;
else return gcd(b,a%b);
}
int lcm(int a,int b)
{
int x=gcd(a,b);
return a*b/x;
}
void solve()
{
int num;
int zi=1,mu=1;
for(int i=1;i<=n;i++)
{
int a,b;
if(flag[i]==0) // 6
{
sscanf(str[i],"%d",&num);
zi+=mu*num;
continue;
}
else if(flag[i]==1) // 6,5/3
{
sscanf(str[i],"%d,%d/%d",&num,&a,&b);
zi+=mu*num;
}
else // 5/3
{
sscanf(str[i],"%d/%d",&a,&b);
}
int newmu=lcm(mu,b);
int newa=(newmu/b)*a;
int newzi=(newmu/mu)*zi;
zi=newzi+newa;
mu=newmu;
if(zi%mu==0)
{
zi=zi/mu;
mu=1;
continue;
}
}
zi-=mu;
if(gcd(zi,mu)!=1)
{
int tmp=gcd(zi,mu);
zi/=tmp;
mu/=tmp;
}
if(zi==0||mu==0)
{
puts("0");
return ;
}
if(zi>=mu)
{
if(zi%mu==0)
{
printf("%d\n",zi/mu);
return ;
}
else
{
int integer=0;
while(zi>mu)
{
zi-=mu,integer++;
}
printf("%d,%d/%d\n",integer,zi,mu);
return ;
}
}
else
printf("%d/%d\n",zi,mu);
}
int main()
{
// freopen("cin.txt","r",stdin);
// freopen("cout.txt","w",stdout);
while(~scanf("%d",&n),n)
{
read();
printf("Test %d: ",kase++);
solve();
}
return 0;
}