10013 - Super long sums

[Qba]

Hello !
What's wrong in this source ?
My program Accepted on acm.timus.ru but on uva.es not ?

This my source code:
[c]
#include <stdio.h>

int main() {
long l9;
int mem;
long N, M;
long i,j, k;
int S;
int l1, l2;

scanf("%ld", &M);
for(k=0; k<M; k++) {
scanf("%ld", &N);
for(i=0, l9=0, mem=-1, S=0; i<N; i++) {
scanf("%d%d", &l1, &l2);
if ((S = l1 + l2) == 9) {
if(mem == -1) printf("9");
else l9++;
}
else {
if (mem != -1) {
printf("%d", mem + S/10);
mem = S%10;
}
else mem = S;
for (j=0; j<l9; j++) printf("0");
l9 = 0;
}
}
if (mem != -1)
printf("%d", mem);
for(j=0; j<l9; j++) printf("9");
printf("\n\n");
}
return 0;
}
[/c]

[tenshi]

check this case:

1

4
0 9
0 9
0 9
1 9

[koola]

the code:

#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>

void add(int x[],int y[],int m)
{
int dig,tag,z[10000],i;
tag=0;
for(i=0;i<m;i++)
{
dig=(x+y+tag)%10;
tag=(x+y+tag)/10;
z=dig;
}
for(i=m-1;i>=0;i--)
{if((tag>0)&&(i==m-1)) cout<<tag;
cout<<z;
}
cout<<endl;
cout<<endl;
}

void main()
{
int x[10000,y[10000];
int n,m,i,j;
char ch;
cin>>n;
for(i=1;i<=n;i++)
{
cin.get(ch);
cin>>m;
for(j=m-1;j>=0;j--)
cin>>x[j]>>y[j];
add(x,y,m);

}
}

[turuthok]

Looks like the digit could be 1,000,000 long ...

-turuthok-

[wangnoon]

Please. help me.
I solved this problem. but I recive Memory Limit Exceeded

the source:

[cpp]
#include <iostream.h>
int a[1000001];
int b[1000001];
int c[10][1000001];
unsigned long mc[10];
unsigned long n;
unsigned long m;
int temp=0;
void main()
{
cin>>n;
unsigned long i,j;
for(i=0;i<n;i=i+1)
{
cin>>m;
for(j=0;j<m;j=j+1)
{
cin>>b[j+1];
cin>>a[j+1];
}

int flag=0;
for(j=m;flag==0;j--)
{
if(j==0)flag=1;
c[j] = a[j]+b[j]+temp;
temp=0;
if(c[j]>=10)
{
c[j]=c[j]-10;
temp=1;
}
}
mc=m;
}
for(i=0;i<n;i++)
{
int flag=0;
for(j=0;j<=mc;j=j+1)
{
if((c[j]==0 && flag ==0)!=1)
{
cout<<c[j];
flag=1;
}
}
cout<<endl<<endl;
}
}

[/cpp]

How can I solve this problem ?
Pls tell me the answer .

[Noim]

1 (total case)
5 (maximum digit)
5 0
8 1
8 0
1 1
1 1


Your program give the solution: 50822
But The answer of this input is 59522...

Over all your coding is very advance type.
Wish you good luck..

[Noim]

1 (total case)
5 (maximum digit)
5 0
8 1
8 0
1 1
1 1


Your program give the solution: 50822
But The answer of this input is 59522...

Over all your coding is very advance type.
Wish you good luck..

[Eric]

I think this should be fast enough.
However, this still exceeds time limit!!
How can I improve this?

[haaaz]

First of all do you really produce correct answer?

e.g.

4
0 9
0 9
0 9
1 9

[haaaz]

1 (total case)
5 (maximum digit)
5 0
8 1
8 0
1 1
1 1


Your program give the solution: 50822
But The answer of this input is 59522...

Over all your coding is very advance type.
Wish you good luck..

Why not 59822?

[haaaz]

I am getting WA.
how is the formmating?

[cpp]#include <iostream.h>
#include <iomanip.h>

int main() {
int total,length,a,b,sum[111113],i,k,temp; // sum base 1000000000

cin >> total;
for (int count=0; count<total; count++) {
if (count != 0)
cout << "\n\n";

cin >> length; // no of digits
sum[0] = 0;

// input digits
k = length%9;
if (k==0)
k=9;
// 9 digits group
for (i=1; i<=((length-1)/9)+1; ++i) { // sum[0] is reserved in case of carry, start form sum[1]
temp=0;
while (k--) {
cin >> a >> b;
temp = temp*10 + a+b;
}
sum = temp;
if (sum > 1000000000) {
sum -= 1000000000;
++sum[i-1];
}
k=9;
}

// calculate carry
for (--i;i>=0; --i)
if (sum > 1000000000) {
sum -= 1000000000;
++sum[i-1];
}

// output
for (k=0;k<=((length-1)/9)+1;++k) {
if (sum[k]) {
cout << sum[k];
break;
}
if (k==((length-1)/9)+1) // in case the answer is zero
cout << 0;
}
for(++k; k<=((length-1)/9)+1; ++k)
cout << setw(9) << setfill('0') << sum[k];

}

return 0;
}[/cpp]

[lowai]

I got TLE after rejuging (I got AC before).
I did not use large arrays.
Do I need to use large arrays to store the number?

[pascal]
var i, n, p, q : longint;
a, b, aa, bb, last, oldest : byte;
cases : integer;
begin
readln(cases);
readln;

repeat

readln(n);
readln(a, b);
if a + b >= 10 then write(1);
last := (a + b) mod 10;
oldest := last;
if a + b = 9 then p := 1; q := p;
for i := 2 to n + 1 do
begin
if i < n + 1 then read(a, b) else begin a := 0; b := 0; end;
if (a + b < 9) and (last < 9) then
begin
write(last);
last := a + b;
end
else
if (a + b >= 10) and (last < 9) then
begin
write(last + 1);
last := a + b - 10;
end
else
if (a + b = 9) and (last = 9) then
begin
end
else
if (a + b = 9) and (last <> 9) then
begin
oldest := last;
last := 9;
p := i; {q := p; }
end
else
if (a + b < 9) and (last = 9) then
begin
if oldest <> 9 then write(oldest);
for q := p to i - 1 do write(9);
last := a + b;
end
else
if (a + b >= 10) and (last = 9) then
begin
if oldest + 1 >= 10 then write(1);
write((oldest + 1) mod 10);
for q := p to i - 1 do write(0);
last := a + b - 10;
end;
end;

writeln; writeln;
dec(cases);
until cases = 0;
end.
[/pascal]

[Adrian Kuegel]

Yes, I think you need large arrays here, because you can't calculate the carry before you haven't read all the numbers.
Therefore you can first read all values and store the added value, after reading normalize the numbers and calculate carry.

[lowai]

I write a new programming using large array. Then I perform the big-num addition. Still TLE.
Any good method?

[junjieliang]

I used a 1000000 array and got AC in 5+ seconds (not exactly the most efficient ). So how do you add? Try to make your loops as tight as possible, and it should pass the time limit.