Friday, April 29, 2011

UVa_10013_Super_long_sums.cpp

Problem Links:

uva10013,

Problem:


Super long sums 

The Problem

The creators of a new programming language D++ have found out that whatever limit for SuperLongInt type they make, sometimes programmers need to operate even larger numbers. A limit of 1000 digits is so small... You have to find the sum of two numbers with maximal size of 1.000.000 digits.

The Input

The first line of a input file is an integer N, then a blank line followed by N input blocks. The first line of an each input block contains a single number M (1<=M<=1000000) — the length of the integers (in order to make their lengths equal, some leading zeroes can be added). It is followed by these integers written in columns. That is, the next M lines contain two digits each, divided by a space. Each of the two given integers is not less than 1, and the length of their sum does not exceed M.
There is a blank line between input blocks.

The Output

There is a blank line between output blocks.

Sample Input

2

4
0 4
4 2
6 8
3 7

3
3 0
7 9
2 8

Sample Output

4750

470

Solution:
Ad-hoc;

Source Code:

//Fri Apr 29 03:18:34 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

string add(string a, string b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    int N = a.size();
    int flag = 0;
    for (int i = 0; i < N; i++) {
        int sum = (a[i] - '0') + (b[i] - '0') + flag;
        if (sum > 9)
            flag = 1;
        else
            flag = 0;
        a[i] = sum % 10 + '0';
    }
    if (flag)
        a += '0' + flag;
    reverse(a.begin(), a.end());
    while (a[0] == '0' && a.size() > 1)
        a = a.substr(1);
    return a;
}

int main(int argc, char* argv[]) {
//  freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        if (t > 0)
            cout << endl;
        int N;
        cin >> N;
        string a = "";
        string b = "";
        int num1, num2;
        for (int i = 0; i < N; i++) {
            cin >> num1 >> num2;
            a += ('0' + num1);
            b += ('0' + num2);
        }
        //      cout << a << endl;
        //      cout << b << endl;
        cout << add(a, b) << endl;
    }
//  fclose(stdin);
    //fclose(stdout);
    return 0;
}

No comments :