Page 1 of 15

10013 - Super long sums

Posted: Thu Aug 08, 2002 4:29 pm
by 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]

Posted: Tue Sep 17, 2002 1:10 pm
by tenshi
check this case:

1

4
0 9
0 9
0 9
1 9

10013 why runtime error?

Posted: Wed Sep 25, 2002 10:44 am
by 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);

}
}





Posted: Fri Sep 27, 2002 2:25 am
by turuthok
Looks like the digit could be 1,000,000 long ...

-turuthok-

10013

Posted: Sun Oct 06, 2002 2:41 pm
by 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 .

Posted: Fri Oct 18, 2002 5:26 pm
by 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... :wink:

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

Posted: Fri Oct 18, 2002 5:28 pm
by 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... :wink:

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

10013 time limit exceeded!

Posted: Thu Oct 24, 2002 3:45 pm
by Eric
I think this should be fast enough.
However, this still exceeds time limit!!
How can I improve this?

Posted: Thu Oct 24, 2002 4:32 pm
by haaaz
First of all do you really produce correct answer?

e.g.
4
0 9
0 9
0 9
1 9

Posted: Sat Oct 26, 2002 5:23 am
by haaaz
Noim wrote: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... :wink:

Over all your coding is very advance type.
Wish you good luck..
Why not 59822?

Posted: Sat Oct 26, 2002 5:38 am
by 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]

10013 (super long sums) TLE

Posted: Sun Nov 03, 2002 7:44 am
by 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]

Posted: Sun Nov 03, 2002 2:40 pm
by 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.

Posted: Mon Nov 04, 2002 6:05 am
by lowai
I write a new programming using large array. Then I perform the big-num addition. Still TLE.
Any good method?

Posted: Mon Nov 04, 2002 6:55 am
by junjieliang
I used a 1000000 array and got AC in 5+ seconds (not exactly the most efficient :D). So how do you add? Try to make your loops as tight as possible, and it should pass the time limit.