This QuickSolution get ACCEPTED !!!!
{$N+}
{ Q = n*(n+1)/2+1 => n^2 + n + 2(1-Q)=0 n must be integer }
var n, i : longint;
q, nr : extended;
begin
read(n);
for i:=1 to n do begin
read(q);
nr := (-1 + sqrt(-7+8*q)) / 2;
if frac(nr) < 1e-8 then write('1 ') else write('0 ');
end;
end.
Re: This QuickSolution get ACCEPTED !!!!
Послано
xxxx01 26 июл 2004 07:53
I can't understand
Re: This QuickSolution get ACCEPTED !!!!
that's the obvious solution...
Re: This QuickSolution get ACCEPTED !!!!
What the f**k is this?
Re: This QuickSolution get ACCEPTED !!!!
I think you don't need extended,just cardinal.
Here's my program:
var
n,i,ans:integer;
k,temp:cardinal;
begin
readln(n);
for i:=1 to n do
begin
readln(k);
dec(k);
if k=0 then ans:=1
else
begin
k:=k*2;
temp:=trunc(sqrt(k));
if temp*(temp+1)=k then ans:=1
else ans:=0;
end;
if i=1 then write(ans) else write(' ',ans);
end;
writeln;
end.
Re: This QuickSolution get ACCEPTED !!!!
Its easy.
all 1 digits stand on places of sums of arithmetical progression + 1.
The eq. of sum of the progression is n*(n+1)/2.
adding 1 you get Q = n*(n+1)/2+1.
Solving this eq. you get (-1 + sqrt(-7+8*q)) / 2.
if nr is integer, you have the position of 1 else the position of 0.
I have a question
Why nr=(-1 + sqrt(-7+8*q))/2
For (q=3) this nr becomes a floating-point number.
I think, nr should be (sqrt(9+8*q)/2-1.5) for (q>2).
Re: This QuickSolution get ACCEPTED !!!!
If 8*q-7 is square there's no need to test is (-1 + sqrt(-7+8*q)) / 2 integer; because discriminant is odd then and this expression is even, so it divides by 2;
Re: This QuickSolution get ACCEPTED !!!!
I have a similar logic, yet I got WA on test #3.
EDIT: I should've put an explicit conversion from long to double, did it - got AC. Hooray! :)
Edited by author 01.03.2008 01:33
Re: This QuickSolution get ACCEPTED !!!!
Hooray!
It's work for me too :)