10013 - Super long sums

[lowai]

here is my program:
[pascal]
var
a, b : array[0..1000000]of integer;
cases, p, q, i, n : longint;
begin
readln(cases);
while cases > 0 do
begin
dec(Cases);

readln(n);
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]

change ur pascal code into c/c++ code
that's ok
good luck!

[Eric]

I still get time limit exceeded.
Can anyone help me?

[Astrakan]

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]

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]

I have corrected the error for answer.
However, Time Limit Exceeded is still the problem.
How can I solve for this?

[Taslim]

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]

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]

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]

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]

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]

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]

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]

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
readln(input,n);
for cnt:=1 to n do begin
nine:=0;
readln(input);
readln(input,l);
readln(input,a,b);
for h:=2 to l do begin
readln(input,c,d);
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]

Sorry your algorithm doesn't work.