10487  Closest Sums
Moderator: Board moderators
10487  Closest Sums
hi this is my algorithm
1.scan the input
2.store each two distinct closest sum in array
3.scan the query
4.search the answer from the array sequentially
but it's slow to get accepted.
can anyone give me a better approach in this problem???
1.scan the input
2.store each two distinct closest sum in array
3.scan the query
4.search the answer from the array sequentially
but it's slow to get accepted.
can anyone give me a better approach in this problem???

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
I got Acc in the same way, but ....
after creating all possible pairs I sort them and use bsearch to search query values ...
I don't know how we could get better time in this problem ...
DM
after creating all possible pairs I sort them and use bsearch to search query values ...
I don't know how we could get better time in this problem ...
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
shell sort has time complexity O(N^2) I think, try to use qsort
this table should have N*N size ... maybe this cause error ...
Best regards
DM
this table should have N*N size ... maybe this cause error ...
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
You have right  I always try to declare only such big tables as is necessary ...
Try to search net for QSORT or QUICK SORT and you take a lot of sources I think
DM
Try to search net for QSORT or QUICK SORT and you take a lot of sources I think
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
 Pier
 New poster
 Posts: 38
 Joined: Thu Mar 27, 2003 9:12 pm
 Location: Aguascalientes, Mexico
 Contact:
10487, 10489 and 10490
I have problems with this three programs. Any help is appreciated!
Problem 10487:
[pascal]Var
c,i,j,k,m,n,s,t: integer;
a: array [1..1000] of integer;
Begin
readln(input,n); c:= 0;
While (n<>0) do
begin
Inc(c); writeln(output,'Case ',c,':');
for i:= 1 to n do
readln(input, a);
readln(input,m);
for i:= 1 to m do
begin
readln(input,s); t:= maxint;
for j:= 1 to n do
for k:= j+1 to n do
if abs(a[j]+a[k]s) < abs(ts) then t:= a[j] + a[k];
writeln(output,'Closest sum to ',s,' is ',t,'.');
end;
readln(input,n);
end;
End.[/pascal]
Problem 10489:
[pascal]Var
a,n,p,s: longint;
b,i,j,k,m,t: byte;
Begin
readln(input,t);
for i:= 1 to t do
begin
readln(input,n,b); s:= 0;
for j:= 1 to b do
begin
read(input,m); p:= 1;
for k:= 1 to m do
begin
read(input, a);
p:= p*a;
end;
Inc(s,p);
end;
writeln(output,s mod n);
end;
End.[/pascal]
Problem 10490:
[pascal]{$N+}
Var
n: longint;
r: extended;
Function Primo(n: Longint): boolean;
var
i: Longint;
res: boolean;
begin
res:= true; i:= 3;
if (n mod 2= 0) then res:= false;
Repeat
if (n mod i= 0) then
begin
res:= false;
break;
end;
Inc(i,2);
until (i>trunc(sqrt(n)));
if (n=2) or (n=3) then res:= true;
primo:= res;
end;
Begin
readln(input,n);
While (n<>0) do
begin
r:= exp(n*ln(2)) 1;
if primo(trunc(r)) then writeln(output,'Perfect: ',r*exp((n1)*ln(2)):0:0,'!')
else if primo(n) then writeln(output,'Given number is prime. But, NO perfect number is available.')
else writeln('Given number is NOT prime! NO perfect number is available.');
readln(input,n);
end;
End.[/pascal]
Problem 10487:
[pascal]Var
c,i,j,k,m,n,s,t: integer;
a: array [1..1000] of integer;
Begin
readln(input,n); c:= 0;
While (n<>0) do
begin
Inc(c); writeln(output,'Case ',c,':');
for i:= 1 to n do
readln(input, a);
readln(input,m);
for i:= 1 to m do
begin
readln(input,s); t:= maxint;
for j:= 1 to n do
for k:= j+1 to n do
if abs(a[j]+a[k]s) < abs(ts) then t:= a[j] + a[k];
writeln(output,'Closest sum to ',s,' is ',t,'.');
end;
readln(input,n);
end;
End.[/pascal]
Problem 10489:
[pascal]Var
a,n,p,s: longint;
b,i,j,k,m,t: byte;
Begin
readln(input,t);
for i:= 1 to t do
begin
readln(input,n,b); s:= 0;
for j:= 1 to b do
begin
read(input,m); p:= 1;
for k:= 1 to m do
begin
read(input, a);
p:= p*a;
end;
Inc(s,p);
end;
writeln(output,s mod n);
end;
End.[/pascal]
Problem 10490:
[pascal]{$N+}
Var
n: longint;
r: extended;
Function Primo(n: Longint): boolean;
var
i: Longint;
res: boolean;
begin
res:= true; i:= 3;
if (n mod 2= 0) then res:= false;
Repeat
if (n mod i= 0) then
begin
res:= false;
break;
end;
Inc(i,2);
until (i>trunc(sqrt(n)));
if (n=2) or (n=3) then res:= true;
primo:= res;
end;
Begin
readln(input,n);
While (n<>0) do
begin
r:= exp(n*ln(2)) 1;
if primo(trunc(r)) then writeln(output,'Perfect: ',r*exp((n1)*ln(2)):0:0,'!')
else if primo(n) then writeln(output,'Given number is prime. But, NO perfect number is available.')
else writeln('Given number is NOT prime! NO perfect number is available.');
readln(input,n);
end;
End.[/pascal]
There are 10 kind of people on this world: those who understand binary and those who don't!