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

Post by lowai » Mon Nov 04, 2002 7:18 am

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
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Post by sjn » Tue Nov 05, 2002 9:54 am

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

Post by Eric » Sun Dec 01, 2002 1:04 pm

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

Post by Astrakan » Mon Dec 02, 2002 11:29 am

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

Post by Astrakan » Mon Dec 02, 2002 12:07 pm

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

Post by Eric » Thu Dec 05, 2002 12:58 pm

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!

Post by Taslim » Sun Dec 08, 2002 6:38 pm

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

Post by Astrakan » Sun Dec 08, 2002 8:13 pm

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

Post by Taslim » Mon Dec 09, 2002 8:44 am

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?

User avatar
szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland

Post by szymcio2001 » Mon Dec 09, 2002 4:13 pm

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

Post by Astrakan » Mon Dec 09, 2002 5:43 pm

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

Post by alun » Mon Dec 09, 2002 6:36 pm

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

Post by Taslim » Tue Dec 10, 2002 6:35 pm

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

Good luck

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

10013 Time Limit Exceeded

Post by chinhoyin » Thu Dec 19, 2002 10:01 am

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
New poster
Posts: 29
Joined: Sun Sep 08, 2002 8:02 am

Post by haaaz » Fri Dec 20, 2002 3:21 pm

Sorry your algorithm doesn't work.

Post Reply

Return to “Volume 100 (10000-10099)”