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 ... ![:)](./images/smilies/icon_smile.gif)
Try to search net for QSORT or QUICK SORT and you take a lot of sources I think
DM
![:)](./images/smilies/icon_smile.gif)
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)
-
- 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(t-s) 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((n-1)*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(t-s) 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((n-1)*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!