10013 - Super long sums

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Qba
New poster
Posts: 4
Joined: Mon Jul 29, 2002 7:44 pm
Location: POLAND

10013 - Super long sums

Post by Qba » Thu Aug 08, 2002 4:29 pm

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]
|Q|

tenshi
New poster
Posts: 14
Joined: Tue Jun 25, 2002 8:50 am

Post by tenshi » Tue Sep 17, 2002 1:10 pm

check this case:

1

4
0 9
0 9
0 9
1 9
http://www.ioiforum.org/en/

A problem discussing forum.
Welcome to discuss problems in it!

koola
New poster
Posts: 2
Joined: Wed Sep 25, 2002 10:41 am

10013 why runtime error?

Post by koola » Wed Sep 25, 2002 10:44 am

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
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Fri Sep 27, 2002 2:25 am

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

-turuthok-

User avatar
wangnoon
New poster
Posts: 7
Joined: Wed Jul 31, 2002 3:20 pm
Location: korea
Contact:

10013

Post by wangnoon » Sun Oct 06, 2002 2:41 pm

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
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » Fri Oct 18, 2002 5:26 pm

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..
__nOi.m....

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » Fri Oct 18, 2002 5:28 pm

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..
__nOi.m....

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong

10013 time limit exceeded!

Post by Eric » Thu Oct 24, 2002 3:45 pm

I think this should be fast enough.
However, this still exceeds time limit!!
How can I improve this?
Last edited by Eric on Thu Mar 27, 2003 2:53 pm, edited 1 time in total.

haaaz
New poster
Posts: 29
Joined: Sun Sep 08, 2002 8:02 am

Post by haaaz » Thu Oct 24, 2002 4:32 pm

First of all do you really produce correct answer?

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

haaaz
New poster
Posts: 29
Joined: Sun Sep 08, 2002 8:02 am

Post by haaaz » Sat Oct 26, 2002 5:23 am

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?

haaaz
New poster
Posts: 29
Joined: Sun Sep 08, 2002 8:02 am

Post by haaaz » Sat Oct 26, 2002 5:38 am

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
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

10013 (super long sums) TLE

Post by lowai » Sun Nov 03, 2002 7:44 am

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Nov 03, 2002 2:40 pm

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
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

Post by lowai » Mon Nov 04, 2002 6:05 am

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

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Mon Nov 04, 2002 6:55 am

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.

Post Reply

Return to “Volume 100 (10000-10099)”