PAT-A 1081 Rational Sum (20)

Given N rational numbers in the form numerator/denominator, you are supposed to calculate their sum.

Problem: PAT-A 1081 Rational Sum

Input Specification

Each input file contains one test case. Each case starts with a positive integer N (≤100), followed in the next line N rational numbers a1/b1 a2/b2 … where all the numerators and denominators are in the range of long int. If there is a negative number, then the sign must appear in front of the numerator.

Output Specification

For each test case, output the sum in the simplest form integer numerator/denominator where integer is the integer part of the sum, numerator < denominator, and the numerator and the denominator have no common factor. You must output only the fractional part if the integer part is 0.

Sample Input 1

1
2

5
2/5 4/15 1/30 -2/60 8/3

Sample Output 1

1

3 1/3

Sample Input 2

1
2

2
4/3 2/3

Sample Output 2

1

2

Sample Input 3

1
2

3
1/3 -1/6 1/8

Sample Output 3

1

7/24

Analysis

  简单的分数加法运算，需要对分数进行化简，即计算最大公约数。测试点只有5个，虽然没有涉及分母为0的情况，但对输出格式抠得还是很死的。输出格式有以下几种。

• 整数部分为0，分子部分不为0，输出分数
• 整数部分不为0，分子部分为0，输出整数
• 整数部分不为0，分子部分不为0，输出整数 + 分数
• 整数部分和分子部分均为0，输出一个0

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int N, num, numS = 0, den, denS = 1;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d/%d", &num, &den);
        numS = numS * den + denS * num;
        denS = denS * den;
        int t = gcd(abs(numS), abs(denS));
        numS /= t;
        denS /= t;
    }
    int itg = numS / denS;   // 获得整数部分
    numS %= denS;
    if (itg != 0) {
        printf("%d", itg);    // 输出非 0 整数部分
        if (numS == 0) return 0;    // 分子为 0, 结束
        printf(" ");
    }
    if (numS == 0) {    // 整数, 分子均为 0
        printf("0");
    } else {    // 分子不为零
        printf("%d/%d", numS, denS);
    }
}

Tsukkomi

  一开始写的时候没有划清4种输出格式，代码写得很乱，拆东墙补西墙，就完全自己挖坑往里跳。后来受不了了直接重写了输出部分，重新理一遍写出来交上去，始终就有一个测试点过不了。

  起初我的循环部分是下面这么写的，一直有一个测试点通过不能，核对了半天输出格式，编了各种测试用例都没问题，每次交上去就是有一个不过。网上搜别人的核对后确认输出都是正确的，然后才想到是不是溢出了。给第一个输入的分数添加了化简操作，就过了……

1
2
3
4
5
6
7
8
9
10

ll num, numS, den, denS;
scanf("%d %lld/%lld", &N, &numS, &denS);
for (int i = 1; i < N; i++) {
    scanf("%lld/%lld", &num, &den);
    numS = numS * den + denS * num;
    denS *= den;
    t = gcd(abs(numS), abs(denS));
    numS /= t;
    denS /= t;
}