## 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

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm
here is my program:
[pascal]
var
a, b : array[0..1000000]of integer;
cases, p, q, i, n : longint;
begin
while cases > 0 do
begin
dec(Cases);

for i := 1 to n do readln(a, b);

p := 0;
for i := n downto 1 do
begin
q := a + b + p;
a := q mod 10;
p := q div 10;
end;
if p > 0 then
begin
write(p);
for i := 1 to n do
write(a);
end
else
begin
write(a[1]);
for i := 2 to n do
write(a);
end;
writeln;
writeln;
end;
end.
[/pascal]

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:
change ur pascal code into c/c++ code
that's ok
good luck!

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong
I still get time limit exceeded.
Can anyone help me?
Last edited by Eric on Thu Mar 27, 2003 2:53 pm, edited 1 time in total.

Astrakan
New poster
Posts: 24
Joined: Sun Nov 03, 2002 12:18 pm
Location: Sweden
When I run your program, it doesn't even produce the correct answer for the sample input/output in the specification. Hint: At one place you are accessing the wrong position in the Number array. You probably get TLE because you write past the beginning of the Number array and overwrite some loop variable or something like that.

Astrakan
New poster
Posts: 24
Joined: Sun Nov 03, 2002 12:18 pm
Location: Sweden
Simple: You use too much memory. The c array consumes 4*10*1000000 = 40 MB of memory. To that is added the memory used by the a and b arrays (which are unnecessary, add the digits immediately instead).

You don't need to read all input before you start producing output. Read one case, calculate it and print the result. Then do the next case and so on. This way you only need a c array with 1000000 positions = 4MB of memory.

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong
I have corrected the error for answer.
However, Time Limit Exceeded is still the problem.
How can I solve for this?

Taslim
New poster
Posts: 9
Joined: Sun Dec 08, 2002 11:47 am
Contact:

### 10013 WA!

Output for all given data its ok...

and also...

For input:-
1
5
5 0
8 1
8 0
1 1
1 1

1
4
0 9
0 9
0 9
1 9

Oput put is :--
59822

99100

And i am geting WA Do u know whats the problem ?Help me

Astrakan
New poster
Posts: 24
Joined: Sun Nov 03, 2002 12:18 pm
Location: Sweden
Your second output, 99100, doesn't look correct. Actually, your program doesn't need to handle 0001+9999 if the specification is correct, the input should be so that the output newer is longer than the input numbers, but it looks totally wrong.

Try this test data:

Code: Select all

``````2
4
8 0
6 3
6 3
2 8

3
1 5
3 6
2 0``````
The output should be:

Code: Select all

``````9000

692``````
On problems like this you can easily create your own test data. Just take two numbers and calculate their sum in your head (or with a calculator), and see if your program produces the same result.

Taslim
New poster
Posts: 9
Joined: Sun Dec 08, 2002 11:47 am
Contact:

### Thanks a lot

HI Astrakan
Thanks for riplay.. i got accept....but PA i use

int main()
{
const long int x=1000000;
int *a,*b,n,m,l,temp;
a=new int[x];
b=new int[x];

Code......
...........

delete a,b;
return 0;
}
So at the end of output file my program write a extra line "Null pointer assignment"

Do u can help! me whats the prob here?

szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland
You don't have to read all digits at the beginning of the program. You can read only two pairs of digits an then write one digit that you can calculate. For example first you read digits a1, b1 and then, in a loop, you read a2, b2 and calculate answer, as follows:
[cpp]
cin >> a2 >> b2;
cout << ((a1 + b1 + (a2 + b2) div 10) div 10);
a1 = a2;
b1 = b2;
[/cpp]

Astrakan
New poster
Posts: 24
Joined: Sun Nov 03, 2002 12:18 pm
Location: Sweden
I think you must write

Code: Select all

``````  delete[] a;
delete[] b;
``````
to delete an array in C++.

It is also possible that you write past the end of one array, try increasing x to 1000001.

Hope this helps

alun
New poster
Posts: 3
Joined: Sun Oct 14, 2001 2:00 am
the length of their sum does not exceed M
so this case is better:
1

4
0 8
0 9
0 9
1 9

Taslim
New poster
Posts: 9
Joined: Sun Dec 08, 2002 11:47 am
Contact:

### Try

See preveas post about this problem u will get AC like me
Test for given input ...... in preveas post about this problem

Good luck

chinhoyin
New poster
Posts: 1
Joined: Thu Dec 19, 2002 9:56 am

### 10013 Time Limit Exceeded

I find that most accepted programs are in C or C++, few in PASCAL![pascal]var cnt,e,f,a,b,c,d,n,l,h,nine:integer;
begin
for cnt:=1 to n do begin
nine:=0;
for h:=2 to l do begin
if c+d=9 then begin
inc(nine);
if nine=1 then begin
e:=a;f:=b
end
end else if nine=0 then
write(output,(a+b+(c+d)div 10)mod 10:0)
else if c+d>9 then begin
write(output,(e+f+1)mod 10:0);
for a:=1 to nine do
write(output,0:0);
nine:=0
end else begin
write(output,(e+f)mod 10:0);
for a:=1 to nine do
write(output,9:0);
nine:=0
end;
a:=c;b:=d
end;
if nine>0 then begin
write(output,(e+f)mod 10:0);
for a:=1 to nine do
write(output,9:0);
writeln(output);
end else writeln(output,(c+d)mod 10:0);
writeln(output)
end
end.[/pascal]

haaaz
New poster
Posts: 29
Joined: Sun Sep 08, 2002 8:02 am
Sorry your algorithm doesn't work.