10013 - Super long sums

[Adrian Kuegel]

First I think you wanted to write a mod instead of last div 10.
And then here is a counterexample:
4
4 4
4 5
4 5
5 5
I think your algorithm will calculate the sum as 8900.

But what you can do is to store a+b, that means you need only one array. Then you go from back to front and calculate carry.

[deddy one]

thx Adrian

your test case proof my algorithm failed, I've fixed it and got AC.

[anupam]

please help me ....
i can't find any alg..
i can't find how to get rid from rte..

#include<stdio.h>
#define N 1000000
main()
{
freopen("c:\\in.txt","r",stdin);
long long cases,z,i,m,a[N],b[N],c[N+10],d;
scanf("%lld",&cases);
for(z=0;z<cases;z++)
{
if(z) printf("\n");
scanf("%lld",&m);
for(i=0;i<m;i++)
scanf("%lld%lld",&a,&b);
for(i=0;i<m+3;i++) c=0;
for(i=(m-1);i>=0;i--)
{
d=a+b;
c[i+1]+=d%10;
c+=d/10;
}
for(i=0;i<m;i++) if(c) break;
for(;i<m+1;i++) printf("%lld",c);
printf("\n");
}
return 0;
}

[Noim]

Sorry,
you are right hazz...
The answer is : 59822

[sohel]

Can any one tell me why this program gets a runtime error.
I have not considered any negetive index and the array size is
also large enough.

here is my code:
[cpp]

#include<stdio.h>

#define max 1000001

int main()
{
int a[max],b[max];
int n,carry=0,final=0,sum;
char ans[max]="";
char t;
unsigned long test,i,j,k=0;
scanf("%d",&n);
for(;n>0;n--)
{
scanf("%lu",&test);
for(i=0;i<test;i++)
scanf("%d %d",&a[i],&b[i]);
for(j=i-1;;j--)
{ if(j==0) final=1;
sum=a[j]+b[j]+carry;
if(sum<=9) {ans[k]=sum+'0';carry=0;}
else{
sum=sum%10;
ans[k]=sum+'0';
carry=1;
}
k++;
if(final==1) break;


}
if(carry==1) {ans[k]=1+'0';k++;}



carry=0;
for(i=0;i<k/2;i++)
{t=ans[i];
ans[i]=ans[k-i-1];
ans[k-i-1]=t;
}
ans[k]=0;
k=0;
final=0;
printf("%s\n",ans);
if(n!=1) printf("\n");
}
return 0;
}

// Thanx[/cpp]

[turuthok]

Ah, this is the same mistake again ... You tried to allocate a[] and b[] whose size can be 4,000,000 each in the stack. That is most likely what your problem is ... try to declare a[] and b[] as static and see what happens.

You can also try to move a[] and b[] out of your main() function.

-turuthok-

[sohel]

I have changed my code according to your suggestions and got AC.

Thanks.

[anupam]

i have tried many times nd got mle(memory..)..
i can't understand what your sugg is?
would u please explain in a easier mode..
--anupam

[Nick]

Hi, i need some help here. My code generates the right output, but the judge gives WA...can anyone tell me why?
[c]
#include <stdio.h>
#include <string.h>


long int res[200000],fres[200000];

void main(void)
{
long int i,j,N,M;
int a,b,c;

#ifndef ONLINE_JUDGE
freopen("10013.in","r",stdin);
freopen("10013.out","w",stdout);
#endif


scanf("%ld",&N);
for (;N;N--)
{
scanf("%ld",&M);
memset(res,0,sizeof(res)); /*initialize both array to 0 */
memset(fres,0,sizeof(fres));
for (i=0,j=-1;i<M;i++)
{
if (i%7==0) j++; /* only 7 digits'll be stored in an element of array*/
scanf("%d %d",&a,&b);
c=a+b;
res[j]=(res[j]*10)+c;
if (i%7==0 && res[j]>10 &&i) {res[j-1]+=1; res[j]%=10;}
/* carry is added every first digit */
}
for (i=0 ; j>=0;j--,i++)
{
if (res[j]>9999999) { fres[i+1]+=res[j]/10000000; }
fres+=res[j]%10000000;
}
while(fres==0) i--;
printf("%ld",fres);
for (i--;i>=0;i--)
{
printf("%ld",fres); /*there are no leading zeros in any element*/
}
printf("\n\n");

}
}


[/c]
Here's what my code does....
1. add two integers and store 7 digits in each element of long int array.
if theres a carry...it'll normalize and sum the carry to the previous one
2. after that... check the whole array for carry again....
3. print the result in reverse order (since the array was reversed in 2nd phase)

Sample input&output

6

18
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9
9 9

3
3 0
7 9
2 8


5
5 0
8 1
8 0
1 1
1 1

4
8 0
6 3
6 3
2 8

3
1 5
1 5
3 6
2 0

4
0 9
0 9
0 9
1 9


OUTPUT :
1999999999999999998
470
59822
9000
692
10000

Thanks for any help,
Nick

[Red Scorpion]

I think Try to bigger your array size.

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)

[Nick]

Thx Red Scorpion,
but larger array wouldn't change anything....unless your problem is SIGSEGV.
I've change my code and got P.E. , i don't know whats the problem...i've tried to change the output format a few times and still haven't changed

[Eric]

Finally solved.
It is similar to 729

[rumel_new]

here is my code:
[cpp]#include<stdio.h>
#include<stdlib.h>
void main ()
{
long int loop,m,i,n,carry,k,ff;
char *x,*y,*z;
scanf("%ld",&loop);
for(m=0;m<loop;m++)
{
scanf("%ld",&n);
x=( char*)malloc(n*sizeof(char));
y=( char *)malloc(n*sizeof(char));
z=( char*)malloc((n+1)*sizeof(char));
for(i=0;i<n;i++){
scanf("%s %s",x+i,y+i);
}
carry=0;
k=1;
for(i=n-1;i>=0;i--)
{
ff=(carry + (*(x+i)-48) + (*(y+i)-48));
*(z+k)= ((carry + (*(x+i)-48) + (*(y+i)-48))%10)+48;
carry=ff/10;
k++;
}
i=0;
*(z+i)=carry +48;
if(*(z+0)>48)
printf("%c",*(z+0));
for(k=n;k>0;k--)
printf("%c",*(z+k));
printf("\n\n");
}
}
[/cpp]

Why it show PE??

[Eric]

Actually, I don't know much about C++
But I think you have put an extra blank line after the last test case.
You shouldn't put it and will soon get accepted without presentation error.
Other mutiple input questions will have this similar problem of P.E.

[25487AH]

Hi, im having troubles whit my code to, can some one help me please?

PD: if i have:
2
9 9
9 9

the output is:
98
(because its M digits, isnt?)

thats my code:

[java]
/* @BEGIN_OF_SOURCE_CODE */
// @JUDGE_ID: 25487AH 10013 Java

import java.io.*;
import java.util.StringTokenizer;
import java.lang.StringBuffer;

class Main{

static String ReadLn (int maxLg){ // utility function to read from stdin
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;

try{
while (lg < maxLg){
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e){
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}

static String ReadLn2(int maxLg){ // utility function to read from stdin
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;

try{
System.in.read(lin);
}
catch (IOException e){
return (null);
}
return (new String (lin, 0, maxLg));
}

public static void main (String args[]) // entry point from OS
{
Main myWork = new Main(); // create a dinamic instance
myWork.Begin(); // the true entry point

}

void Begin(){
StringTokenizer idata;
int s,l=0;
int m,i,n;//,k=0;
StringBuffer tmp;
n = Integer.parseInt(Main.ReadLn(50).trim());
while (--n>=0){
Main.ReadLn(1);
m = Integer.parseInt(Main.ReadLn(15).trim());
idata = new StringTokenizer((new StringBuffer(Main.ReadLn2(m*4)).reverse().toString()));
tmp=new StringBuffer(m+1);

l=0;
for(i=0; i<m; i++){
if((s=(Integer.parseInt((idata.nextToken()).trim()))+(Integer.parseInt((idata.nextToken()).trim()))+l)>9){
s-=10;
l=1;
}else
l=0;
tmp.append(s);
}

System.out.println(tmp.reverse().toString());

if(n!=0)
System.out.println();
}
}
}

/* @END_OF_SOURCE_CODE */
[/java]