模拟 --- hdu 12878 : Fun With Fractions

简介: Fun With Fractions Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:65536KB Total submit users: 152, Accepted users: 32 ...

 

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.
Addition of rational numbers is defined as follows. Note that the right hand side of this equality will not necessarily be in lowest terms.

A rational number for which the numerator is greater than or equal to the denominator can be displayed in mixed format, which includes a whole number part and a fractional part.
For example, 51/3 is a mixed format representation of the rational number 16/3. Your task is to write a program that reads a sequence of rational numbers and displays their sum.



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.
The n following lines each contain a single string with no embedded whitespace . Each string represents a rational number, which could be in any of the following forms and will not necessarily be in lowest terms (w, n, and d are integers: 0 <= w,n < 1000, 1 <= d < 1000).
• w,n/d: a mixed number equivalent to the rational number (w*d + n) / d.
• n/d: a rational number with a zero whole number part
• w: a whole number with a zero fractional part



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:

//Memory   Time
//  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;
}

 

目录
相关文章
|
7月前
|
存储 C++ Python
LeetCode刷题---Add Two Numbers(一)
LeetCode刷题---Add Two Numbers(一)
|
10月前
|
算法
初学算法之---pta fun with numbers
初学算法之---pta fun with numbers
每日一题---500. 键盘行[力扣][Go]
每日一题---500. 键盘行[力扣][Go]
每日一题---500. 键盘行[力扣][Go]
每日一题---1005. K 次取反后最大化的数组和[力扣][Go]
每日一题---1005. K 次取反后最大化的数组和[力扣][Go]
每日一题---1005. K 次取反后最大化的数组和[力扣][Go]
|
前端开发
今日一题 - 请模拟实现一个Promise.all() 方法?
Promise.all()方法用于将多个 Promise 实例,包装成一个新的 Promise 实例。 Promise.all()方法的参数可以不是数组,但必须具有 Iterator 接口(所以数组、Map、Set都可以),并且只返回一个Promise实例,输入的所有promise的resolve回调的结果会按传入的按顺序作为一个数组的其中一项返回。 当然也支持非promise对象的传入,会作为数组中的一项返回。
135 0
今日一题 - 请模拟实现一个Promise.all() 方法?
【1023】Have Fun with Numbers (20 分)
【1023】Have Fun with Numbers (20 分) 【1023】Have Fun with Numbers (20 分)
77 0
|
机器学习/深度学习
【HDU 4452 Running Rabbits】简单模拟
两只兔子Tom和Jerry在一个n*n的格子区域跑,分别起始于(1,1)和(n,n),有各自的速度speed(格/小时)、初始方向dir(E、N、W、S)和左转周期turn(小时/次)。 各自每小时往E、N、W、S中一个方向跑speed格,每隔turn小时左转一次(即逆时针的下一个方向)。
785 0