加载中...

POJ 2602 - Superlong sums


0x00 POJ 原题

Description

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.

Input

The first line of an input file contains a single number N (1<=N<=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 N 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 N.

Output

Output file should contain exactly N digits in a single line representing the sum of these two integers.

Sample Input

4
0 4
4 2
6 8
3 7

Sample Output

4750

Hint

Huge input,scanf is recommended.

Source

Ural State University collegiate programming contest 2000

0x10 解题思路

非常恶心的大数相加

首先输入就够恶心了…哪有人逐位还要间断输入两个数的…

注意:

  • 如果用 char[] 保存加数和被加数,要用 getchar() 输入,
  • 如果用 int[] 保存加数和被加数,要用 scanf() 输入。
  • 用 cin 会超时,cin 是重载函数,没有指定格式,输入时比较浪费时间
  • 100W 的空间不能局部静态申请,单可以全局静态申请,也可以局部动态申请(用 new)

最恶心得是,我把结果开头的 0(如果有的话)删去,竟然 WA…!

Output file should contain exactly N digits in a single line representing the sum of these two integers.

这是输出要求的格式,竟然要求 被加数、加数、和 的位数一致!!

按这样理解,这题是不允许最高位出现进位的…!!

0x20 AC 源码

0x21 解题方法一:使用 char[] 存储数字

//Memory  Time 
//11972K 1594MS 

#include<iostream>
#include<string>
using namespace std;

const int size=1000000;  //大数位数上限
int n;  //大数位数

int a[size+1];
int b[size+1];

void add(char* A,char* B,char* ans)
{
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    int pa=0,pb=0;

    int lena=strlen(A);
    int lenb=strlen(B);

    /*倒序*/

    for(int i=lena-1;i>=0;i--)
        a[pa++]=A[i]-'0';
    for(int j=lenb-1;j>=0;j--)
        b[pb++]=B[j]-'0';

    int len=lena>lenb?lena:lenb;
    char* c=new char[len+1];  //倒序的ans

    int w=0;  //低位到高位的进位
    for(int k=0;k<len;k++)
    {
        int temp=a[k]+b[k]+w;
        c[k]=temp%10+'0';
        w=temp/10;
    }
    len--;

    for(w=0;len>=0;len--)  //w和len均作指针使用,已无意义
        ans[w++]=c[len];
    ans[w]='\0';

    delete c;
    return;
}

char A[size+1];
char B[size+1];
char ans[size+1];

int main(int i)
{
    while(cin>>n)
    {
        getchar();
        for(i=0;i<n;i++)
        {
            A[i]=getchar();
            getchar();  //空格
            B[i]=getchar();
            getchar();  //回车
        }
        A[i]=B[i]='\0';

        add(A,B,ans);
        cout<<ans<<endl;
    }
    return 0;
}

0x22 解题方法二:使用 int[] 存储数字

//Memory  Time 
//17868K 1625MS

#include<iostream>
using namespace std;

int n;  //大数位数

void add(int* a,int* b,char* ans)
{
    char* c=new char[n+1];  //倒序的ans

    int w=0;  //低位到高位的进位
    for(int k=0;k<n;k++)
    {
        int temp=a[k]+b[k]+w;
        c[k]=temp%10+'0';
        w=temp/10;
    }

    n--;
    for(w=0;n>=0;n--)  //w和n均作指针使用,已无意义
        ans[w++]=c[n];
    ans[w]='\0';

    delete c;
    return;
}

int main(int i)
{
    while(cin>>n)
    {
        int* a=new int[n+1];
        int* b=new int[n+1];
        int* ta=new int[n+1];
        int* tb=new int[n+1];
        char* ans=new char[n+1];

        for(i=0;i<n;i++)
            scanf("%d %d",&ta[i],&tb[i]);

        /*倒序*/

        int pa=0,pb=0;
        for(i=n-1;i>=0;i--)
        {
            a[pa++]=ta[i];
            b[pb++]=tb[i];
        }

        add(a,b,ans);
        cout<<ans<<endl;

        delete a;
        delete b;
        delete ta;
        delete tb;
        delete ans;
    }
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
赏
  目录