ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1209. 1, 10, 100, 1000...

This QuickSolution get ACCEPTED !!!!
Posted by Dream Team ETU 22 Mar 2003 18:31
{$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 !!!!
Posted by xxxx01 26 Jul 2004 07:53
I can't understand
Re: This QuickSolution get ACCEPTED !!!!
Posted by Gheorghe Stefan 27 Jul 2004 17:24
that's the obvious solution...
Re: This QuickSolution get ACCEPTED !!!!
Posted by Votjakov_Roman 17 Oct 2005 13:48
What the f**k is this?
Re: This QuickSolution get ACCEPTED !!!!
Posted by wangyin 3 Nov 2005 14:23
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 !!!!
Posted by Alexander Sokolov [MAI] 23 Sep 2006 17:32
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.
no message
Posted by SuperLight 24 Sep 2006 21:37
I have a question
Posted by ilovesky 14 Jul 2007 17:24
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 !!!!
Posted by Maksim Bolonkin (MSU TB) 15 Feb 2008 17:10
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 !!!!
Posted by Neolisk 1 Mar 2008 01:22
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 !!!!
Posted by Novikov Michael 11 Jul 2011 19:08
Hooray!
It's work for me too :)